60分求助

P1241 括号序列

JustBecause @ 2022-10-08 12:00:41

#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<vector>
#include<stack>
using namespace std;

inline void read(int& x) { x = 0; char c; for (c = getchar(); c < '0' || c > '9'; c = getchar()); for (; c >= '0' && c <= '9'; c = getchar()) x = (x << 3) + (x << 1) + c - '0'; }

stack<char>cs;
stack<bool>bs;

int main()
{
    string s;
    getline(cin, s);
    int len = s.length();
    for (int i = 0; i < len; i++)
    {
        if (s[i] == '(' || s[i] == '[')
        {
            cs.push(s[i]);
            bs.push(false);
        }
        else
        {
            bool find = false;
            stack<char>tcs;
            stack<bool>tbs;
            while (!cs.empty())
            {
                char c= cs.top();
                bool b = bs.top();
                if ((c == '(' || c == '[')&&!b)//找到第一个未匹配的左括号
                {
                    if (s[i] == ')' && c == '(')
                    {
                        find = true;//找到匹配的
                        bs.pop();
                        bs.push(true);
                        break;
                    }
                    else if (s[i] == ']' && c == '[')
                    {
                        find = true;//找到匹配的
                        bs.pop();
                        bs.push(true);
                        break;
                    }
                    else if (s[i] == ')' && c == '[')
                    {
                        find = false;
                        break;
                    }
                }
                cs.pop();
                bs.pop();
                tcs.push(c);
                tbs.push(b);
            }
            while (!tcs.empty())
            {
                char c = tcs.top();
                bool b = tbs.top();
                tcs.pop();
                tbs.pop();
                cs.push(c);
                bs.push(b);
            }
            if (find)
            {
                cs.push(s[i]);
                bs.push(true);
            }
            else
            {
                cs.push(s[i]);
                bs.push(false);
            }
        }
    }
    string ans="";
    while (!cs.empty())
    {
        //cout << cs.top() << " " << bs.top() << endl;
        if (bs.top())
        {
            ans = cs.top()+ans;
        }
        else if (cs.top() == '('|| cs.top() == ')')
        {
            ans = "()"+ans;
        }
        else if (cs.top() == '[' || cs.top() == ']')
        {
            ans = "[]"+ans;
        }
        cs.pop();
        bs.pop();
    }
    cout << ans << endl;
    return 0;
}

by JustBecause @ 2022-10-08 12:11:33

试了些讨论区提到的易错测试点都没问题,有点懵


|