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

cxoi1501 · 2025-10-06 16:49:24 · 题解

思路：

用栈存储，最后判断一下剩下的括号即可。

AC code:

#include<bits/stdc++.h>
using namespace std;
long long t,n,k;
string s;
struct node
{
    char c;
    int val;
}a[100010];
bool cmp(node aa,node bb)
{
    return aa.val<bb.val;
}
int main()
{
    cin>>t;
    while(t--)
    {
    //  memset(a,{'1',0},sizeof(a));
        k=0;
        cin>>n;
        cin>>s;
        stack<int> t,p;
        string ss="";
        for(int i=0;i<n;i++)
        {
            if(s[i]=='(') 
            {       
                t.push(1);
                p.push(i);
            }
            else 
            {
                if(!t.empty())
                {
                    t.pop();
                    p.pop();
                }
                else
                {

                    a[++k]={')',i};
                } 
            }
        }
        while(!t.empty())
        {
            int e=p.top();
            p.pop();
            t.pop();
            a[++k]={'(',e};
        }
        sort(a+1,a+1+k,cmp);
        if(k==2||k==0)
        {
            if(k==0)
            {
                cout<<"Yes"<<endl;      
            }
            else if(abs(a[1].val-a[2].val)==1&&a[1].c==')'&&a[2].c=='(')
            {
                cout<<"Yes"<<endl;
            }
            else
            {
                cout<<"No"<<endl;
            }
        }   
        else
        {
            cout<<"No"<<endl;
        }
    }
}