AtCoder ABC307D Mismatched Parentheses 题解
思路分析
First —— 配对括号序列
首先，每个右括号肯定是要与其左边最近的左括号配对。因此，我们便可以使用一个栈来进行存放左括号的下标。当有右括号时，便可以弹出栈顶元素，但是栈为空时，便无法配对。
拿样例 1 举个例子：
8
a(b(d))c
当 $ i = 1 $时（下标从 \(0\) 开始），入栈 \(1\)。
此时的栈：1。
当 $ i = 3 $时，入栈 \(3\)。
此时的栈：1 3。
当 $ i = 5 $时，弹出 \(3\)，将 \(f_3 \gets 1\)，\(f_5 \gets 2\)。
此时的 \(f\) 数组如下：
0 0 0 1 0 2 0 0
此时的栈：1。
以此类推。
最后，\(f\) 数组如下：
0 1 0 1 0 2 2 0
这时，我们已经完成了括号序列的配对。
Second —— 去除括号内容
现在，我们可以定义数组 \(l\)。
- \(l_i = 1\)，表示此项被去除。
- \(l_i = 0\)，表示此项没有被去除。
如何构造 \(l\) 呢？
我们可以定义一个 \(x\)，表示我们正在第 \(x\) 层括号中。
- \(f_i = 1\)，表示进入括号，\(x\) 需要加 \(1\)。
- \(f_i = 1\)，表示离开括号，\(x\) 需要减 \(1\)。
- \(x \ge 1\)，表示在括号中，\(l_i \gets 1\)。
最后即可构造出 \(l\)。
Third —— 输出最终字符串
枚举 \(1\) 到 \(n\)。
- \(l_i = 0\)，输出 \(s_i\)。
- \(l_i = 1\)，不输出任何内容。
代码实现
此代码中三个循环分别代表了上文中的三个步骤。
注：在第二步中的复制的 if 语句需要前后两次判断，因为经过判断后 \(x\) 可能会改变。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n;
int x;
int f[N];
int l[N];
char s[N];
stack<int> stk;
int main()
{
scanf("%d", &n);
scanf("%s", s);
for (int i = 0; i < n; i++)
{
if (s[i] == '(')
{
stk.push(i);
}
else if (s[i] == ')' && !stk.empty())
{
x = stk.top();
stk.pop();
f[x] = 1;
f[i] = 2;
}
}
x = 0;
for (int i = 0; i < n; i++)
{
if (x > 0)
{
l[i] = 1;
}
if (f[i] == 1)
{
x++;
}
else if (f[i] == 2)
{
x--;
}
if (x > 0)
{
l[i] = 1;
}
}
for (int i = 0; i < n; i++)
{
if (!l[i])
{
printf("%c", s[i]);
}
}
printf("\n");
return 0;
}