A104748 题解

题干分析

有一个只有 ( 和 ) 的字符串，要删除任意多个字符，使其变成合法括号串。

思路

用 stack 模拟配对过程，如果当前的 $s_i$ 是等于 ( 的，就将 $s_i$ 放入栈中，等待匹配。否则就检查是否还有没被匹配的 (，如果有就出栈，否则计数器 $+1$。当 $s$ 被遍历完后，剩下的 ( 也无法被匹配（如果有的话），因此答案为计数器 $+$ 栈内剩余的元素个数。

代码

#include<bits/stdc++.h>
using namespace std;
int check(string st){
    stack<char> cz;
    int cnt=0;
    for(int i=0;i<st.length();i++){
        if(st[i]=='('){
            cz.push(st[i]);
        }
        if(st[i]==')'){
            if(!cz.empty()){
                cz.pop();
            }
            else{
                cnt++;
            }
        }
    }
    return cnt+cz.size();
}
int n;
string s;
int main(){
    cin>>n>>s;
    cout<<check(s);
}