题解 | 括号的匹配

#include <bits/stdc++.h>
using namespace std;
bool isvalid(const string & );//引用传递，无需拷贝

int main() {
    int T;cin>>T;
    while(T-->0){
        string s;cin>>s;
        (isvalid(s))?cout<<"YES":cout<<"NO";
        cout<<endl;
    }
    return 0;
}

bool isvalid(string &s){
    stack<char>st;
    unordered_map<char,int>prior={
        {'{',4},{'[',3},{'(',2},{'<',1},{'}',4},{']',3},{')',2},{'>',1}
    };
    for(auto c:s){
        if(c=='{'||c=='['||c=='('||c=='<'){
            if(st.empty()) st.push(c);
            else{
                if(prior[c]<=prior[st.top()]) st.push(c);
                else return false;
            }
        }
        else{
            if(st.empty()) return false;
            else{
                if(prior[c]==prior[st.top()]) st.pop();
                else return false;
            }
        }
    }
    return st.empty();
}
// 64 位输出请用 printf("%lld")