是string的问题吗?

P1241 括号序列

天马行空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() == -1f[x.top()] 必越界。


by 天马行空mz @ 2023-01-30 12:04:12

@ud2_ 感谢,前置之后过了,找了半天第一个循环的问题,没想到是在第二循环。


by wsbSB @ 2023-08-03 09:59:07

@天马行空mz 是O2的问题


|