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
试了些讨论区提到的易错测试点都没问题,有点懵