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

· · 题解

P14172 括号串 题解

题意简述

对于一个括号串 s ，可以将连续的 )( 转化为 () ，判断 s 在能否在修改后合法（或者是本身合法）。

解法

对于顺序匹配的问题，考虑用栈维护。
假设 s 为合法括号串，我们可以使用一个栈 st 维护，栈中存储一个对，记下括号在串中的位置，以及括号类型，将 ( 记为 1，) 记为 0。顺序遍历整个串，对于串中的括号 (，直接压入栈中；对于括号 ) ,检查栈顶是否有配对的 (，如果有，就一并弹出栈。
接下来考虑能将相邻两个括号 )( 改成 () 情况。我们发现如果存在能将 )( 改成 () 使括号串合法的情况，除去相邻的 )(，剩下的部分一定是合法的，而合法的部分一定在栈操作中被抵消。
所以我们可以检查栈，如果栈中只存在连续的 )( 我们便认定这个串在修改后是合法的。
出入栈操作复杂度 O(n)，检查栈复杂度 O(n)，总时间复杂度 O(n)。

AC Code:

#include<bits/stdc++.h>
#define pib pair<int,bool>
#define fi first
#define se second
#define mp make_pair
using namespace std;

int T;

void solve(){
    int N;
    string s;
    stack<pib> st;
    cin>>N>>s;
    if(N%2){
        cout<<"No\n";          //对于奇数串进行特判，以免最后检查时出错 
        return ;
    }
    for(int i=0;i<N;i++){
        if(s[i]==')'){
            if(st.empty()) st.push(mp(i,0));
            else{
                if(st.top().se) st.pop();
                else st.push(mp(i,0));
            }                 //对于反过来的括号进行配对检查 
        }
        else st.push(mp(i,1));
    }
    while(st.size()>=2){
        pib nw=st.top();
        st.pop();
        if((nw.se^st.top().se)&&(nw.fi==st.top().fi+1)) st.pop();    //检查连续的 ')(' 是否可以修改
        else{
            cout<<"No\n";
            return ;
        }   
    }                         //对于栈中剩下的括号进行检查 
    cout<<"Yes\n";            //如果全部匹配或是栈为空（本身合法），输出 "Yes" 
}

int main()
{
    cin>>T;
    while(T--) solve();
    return 0;
}

（本人的第一个题解，求轻喷，不懂可以私信问。）