题解：AT_abc394_d [ABC394D] Colorful Bracket Sequence

NaPF6 · 2025-02-24 14:03:56 · 题解

彩色括号序列就是所有括号都能配对的序列。

我们用一个栈来维护配对情况：

• 遇到一个左括号或者栈是空的就进栈。
• 遇到一个右括号就判断栈顶能不能和它配对，如果能就弹出。

如果最后栈为空就说明配对成功。

Code

#include<bits/stdc++.h>
using namespace std;
string s;
int n;
stack<char> st;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>s;n=s.size();s=" "+s;
    for(int i=1;i<=n;i++){
        if(st.empty()||s[i]=='('||s[i]=='['||s[i]=='<')st.push(s[i]);
        else if(st.top()=='('&&s[i]==')')st.pop();
        else if(st.top()=='['&&s[i]==']')st.pop();
        else if(st.top()=='<'&&s[i]=='>')st.pop();
        else st.push(s[i]);
    }
    if(!st.empty())cout<<"No";
    else cout<<"Yes";
    return 0;
}