AT_abc394_d 题解

getchar_unlocked · 2025-02-23 22:49:43 · 题解

题目传送门

思路

在最基础的括号匹配问题上，变成了 3 种字符。同样可以用栈进行模拟，将所有左括号压入栈内。若当前右括号与栈顶左括号不匹配或栈为空，输出 No。最后再判断最后的栈是否为空（是否有多余的左括号）即可。

时间复杂度 \mathcal{O}(N)。

AC CODE

#include<bits/stdc++.h>
using namespace std;
char to[128];
signed main(){
    string s;cin>>s;
    to[')']='(',to[']']='[',to['>']='<';
    stack<char>st;
    for(auto ch:s){
        if(ch=='('||ch=='['||ch=='<')
            st.push(ch);
        else if(ch==')'||ch==']'||ch=='>'){
            if(st.empty()||st.top()!=to[ch])
                return cout<<"No\n",0;
            st.pop();
        }
        else return cout<<"No\n",0;
    }
    if(st.empty())
        cout<<"Yes\n";
    else cout<<"No\n";
    return 0;
}