[ABC307_D] Mismatched Parentheses

[ABC307_D] Mismatched Parentheses

题目分析

• 对于一个给定字符串删出每对括号里的所有元素。

• 可以想到用 set 维护每个左括号的位置，出现右括号就退回与之匹配的左括号前一个位置，如果没有左括号则加入答案。

代码：

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
template <typename _T>

inline void read(_T &x)
{
    x = 0; char c; _T d = 1;
    while(c > 57 || c < 48){
        c = getchar();
        if(c == '-') d = -1;
    }
    while(c >= 48 && c <= 57){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    x *= d;
}

const int N = 2e5 + 5;
int n;
char a[N], ans[N];
set<int> s;
int cnt;

signed main()
{
    read(n);
    cin >> a;

    for(int i = 0; i < n; i++){
        if(a[i] == '('){
            ans[++cnt] = a[i];
            s.insert(cnt); 
        }else if(a[i] == ')'){
            if(!s.empty()){
                cnt = *s.rbegin(); //访问最后插入的左括号的位置 
                cnt--; //删除 
                auto pos = s.end(); 
                s.erase(--pos);
            }else{
                ans[++cnt] = a[i];
            }
        }else {
            ans[++cnt] = a[i];
        }
    }

    for(int i = 1; i <= cnt; i++) cout << ans[i];

    return 0;
}