Colorful Bracket Sequence

_shine_ · 2025-02-24 16:35:29 · 题解

一个括号匹配的升级版。

维护一个栈，同时扫一遍字符串，如果当前扫到的位置为左括号就加入栈中，如果是右括号且与栈顶匹配就弹出栈顶，反之显然不成立（因为一个可以被删干净的序列必定是层层匹配的，即存在位置满足匹配的括号中间没有遮挡，在删去该匹配后仍然如此），最后输出即可。

注意在最后要查看是否栈为空。

#include<bits/stdc++.h>
using namespace std;
stack<char>st;
string s;
int check(char ch){
    if(ch=='<' || ch=='>')return 1;
    if(ch=='(' || ch==')')return 2;
    if(ch=='[' || ch==']')return 3;
}
signed main(){
    cin >> s;
    for(int i=0;i<s.size();++i){
//      cout << i;
        if(s[i]=='<' || s[i]=='(' || s[i]=='[')st.push(s[i]);
        else if(s[i]=='>' || s[i]==')' || s[i]==']'){
            if(st.size()==0 || check(s[i])!=check(st.top())){puts("No");return 0;}
            st.pop();
        }else {puts("No");return 0;}
    }
//  cout << st.siz
    if(st.size()!=0)puts("No");
    else puts("Yes");
    return 0;
}