栈+st数组
删完后栈顶是左括号,要么是残缺,要么是嵌套
当存在嵌套行为时,st数组记录有嵌套的位置
#include<bits/stdc++.h>
using namespace std;
map<char,int> pri{{'{',4},{'[',3},{'(',2},{'<',1}}; //优先级
map<char,char> match{{'(',')'},{'{','}'},{'<','>'},{'[',']'}};
const int N=110;
int st[N];
int main()
{
int n;
cin>>n;
while(n--)
{
string a;
cin>>a;
memset(st,0,sizeof st);
stack<int> s; //栈存储的是"下标"
for(int i=0;i<a.size();i++)
{
if(s.empty())s.push(i);
else
{
if(match[a[s.top()]]==a[i])s.pop();
else
{
st[i]=s.top()+1; //有嵌套行为,存下外层下标,防止下标为0造成下面的判断错误,直接加1
s.push(i);
}
}
}
if(s.size())puts("NO"); //残缺的
else
{
bool flag=0;
for(int i=0;i<a.size();i++)
{
if(st[i])
{
if(pri[a[i]]>pri[a[st[i]-1]])//记得减1 //[(){}] 输出NO
{
puts("NO");
flag=1;
break;
}
}
}
if(!flag)puts("YES");
}
}
return 0;
}