题解：P14172 【MX-X23-T2】括号串

· · 题解

P14172题解

思路

开两个栈，一个栈 s1 存储左括号的位置，另一个栈 s2 存储右括号的位置。

当遍历所有括号时，如果遇到左括号且 s2 栈顶的值等于该位置减一，则说明 “)(” 可以变成“()”，然后弹出 s2 栈顶，用一个变量 cnt（记录变化次数） 加一。但如果 s2 栈顶的值不等于当前位置减一或为空，则将该左括号的位置压入栈 s1 中。

当遍历所有括号时，如果遇到右括号且该位置之前有未匹配的左括号，则将 s1 栈顶弹出。但如 s1 为空，则将该右括号的位置 压入栈s2 中。

最后，如果两个栈为空，且 cnt 小于或等于一（因为最多只能变换一次），则输出 Yes 。否则输出 No 。

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    stack<int> s1,s2;//分别存储左括号和右括号的位置 
    while(t--){
        while(!s1.empty()) s1.pop();//清空 
        while(!s2.empty()) s2.pop();
        int n;
        cin>>n;
        int cnt=0;//变换次数计数器 
        for(int i=1;i<=n;i++){
            char x;
            cin>>x;
            if(x=='('){
                if(!s2.empty()&&s2.top()+1==i){//栈s2顶部的值加一等于该位置 
                    s2.pop();//弹出 
                    cnt++;//计数器加一 
                } 
                else s1.push(i);//否则，直接压入栈s1 
            } 
            else{
                if(!s1.empty()) s1.pop();//只要栈s1不为空，则可以匹配 
                else s2.push(i);//如果为空，将右括号位置压入栈s2 
            }
        }
        if(s1.size()||s2.size()||cnt>1) cout<<"No"<<endl;//只要两个栈内还有东西，就不能 
        else cout<<"Yes"<<endl;
    }
    return 0;
}