题解 | 括号的匹配

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
int main(){
    int T;
    cin>>T;
    while(T--){
        unordered_map<char,int>mp;
        mp['{']=1;mp['[']=2;mp['(']=3;mp['<']=4;
        mp['}']=-1;mp[']']=-2;mp[')']=-3;mp['>']=-4;
        stack<char>st;
        string s;
        cin>>s;
        int len = s.length(),tmpmax = 0;
        bool res = true;
        for(int i=0;i<len;i++){
            if(mp[s[i]]<0)tmpmax = 0;
            else if(!st.empty()&&mp[st.top()]>mp[s[i]]){
                res = false;
                break;
            }
            else tmpmax = max(tmpmax,mp[s[i]]);
            if(mp[s[i]]>0)st.push(s[i]);
            else if(mp[s[i]]<0&&!st.empty()&&mp[st.top()]+mp[s[i]]==0)st.pop();
            else {
                res = false;
                break;
            }
        }
        if(res&&st.empty())cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}