题解 | 括号的匹配

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define quick ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int inf=0x3f3f3f3f,maxn=2e5+5,mod=998244353;
inline int read(){
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
	return s*w;
}
void solve(){
    string str;cin>>str;
    map<char,int>mp;
    mp['{']=4;mp['[']=3;mp['(']=2;mp['<']=1;
    mp['}']=-4;mp[']']=-3;mp[')']=-2;mp['>']=-1;
    int cnt=0;
    for(int i=0;i<str.size();i++){
        cnt+=mp[str[i]];
        if(cnt<0){
            cout<<"NO"<<endl;
            return;
        }
    }
    stack<char>stk;
    for(int i=0;i<str.size()-1;i++){
        if(mp[str[i]]>0){
            stk.push(str[i]);
        }
        if(mp[str[i]]<mp[str[i+1]]&&mp[stk.top()]+mp[str[i]]!=0){
            cout<<"NO"<<endl;
            return;
        }
        if(mp[stk.top()]+mp[str[i]]==0){
            stk.pop();
        }
    }
    cout<<"YES"<<endl;
}
signed main(){
	int t=1;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}
/*
栈用来检查如(<>)合法但是(<)>不合法的方式
哈希表用来检测())这种情况和)(这种情况
每个括号加上权值更好分析
*/