天马行空mz @ 2023-01-30 11:51:07
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 200000
stack<char> q;//字符
stack<int> x;//位置
string s;
int f[maxn];
int main()
{
ios::sync_with_stdio(false);
cin>>s;
q.push('-');
x.push(-1);
for(int i=0;i<s.length();i++)
{
if(s[i]=='('||s[i]=='[')//直接放入
{
q.push(s[i]);x.push(i);
}
else if(s[i]==')'&&q.top()!='(')//未匹配
{
f[i]=1;
}
else if(s[i]==']'&&q.top()!='[')//未匹配
{
f[i]=2;
}
else if(s[i]==')'&&q.top()=='(')//匹配
{
q.pop();x.pop();
}
else if(s[i]==']'&&q.top()=='[')//匹配
{
q.pop();x.pop();
}
}
while(!q.empty())
{
if(q.top()=='('||q.top()==')')
{
f[x.top()]=1;
x.pop();q.pop();
}
else
{
f[x.top()]=2;
x.pop();q.pop();
}
if(q.top()=='-') break;
}
for(int i=0;i<s.length();i++)
{
if(f[i]==1) cout<<"()";
else if(f[i]==2) cout<<"[]";
else cout<<s[i];
}
cout<<endl;
return 0;
}
跑代码,跑那种不合适的样例没有问题,但是一旦跑平衡括号序列,例如“([])”,就直接卡死在第一循环这里,拿这个代码跑只有AC和RE。
by ud2_ @ 2023-01-30 11:58:59
第 40 行 q.top() == '-'
时不满足条件,跳转到第 47 行,这时 x.top() == -1
,f[x.top()]
必越界。
by 天马行空mz @ 2023-01-30 12:04:12
@ud2_ 感谢,前置之后过了,找了半天第一个循环的问题,没想到是在第二循环。
by wsbSB @ 2023-08-03 09:59:07
@天马行空mz 是O2的问题