xxyQwQ
0%

【题解】ACMOJ 1216 括号匹配

发表于 分类于

题目描述

ACMOJ - 1216 - 括号匹配

模拟一个括号栈，包含()[]{}六种括号，支持如下四种操作：

  1. 向栈中压入元素
  2. 从栈中弹出元素
  3. 查询栈顶元素
  4. 判断栈中自底向上构成的括号序列是否匹配

保证操作次数 $n\leq 10^6$

问题分析

前置知识：利用栈进行括号匹配 参考链接

由于本题需要支持动态匹配，我们维护两个栈，$P$ 用于保存括号，$Q$ 用于括号匹配

  • 向 $P$ 中压入元素 $x$ 时，我们按照括号匹配的规则对 $Q$ 进行维护
  • 从 $P$ 中弹出元素 $x$ 时，我们将压入 $x$ 时对 $Q$ 的修改还原

由于压入 $x$ 时，可能会向 $Q$ 中压入元素，也可能会从 $Q$ 中弹出元素，因此我们需要记录 $x$ 对 $Q$ 的修改类型，方便后续的维护

由于每次操作的复杂度都是 $O(1)$，算法的复杂度为 $O(n)$，由于问题规模 $n\leq 10^6$，如果使用 $O(n^2)$ 的算法处理问题一定会超时

一些细节

  1. 推荐用数组模拟栈，代码会更加简洁
  2. 读入括号时，建议直接读入字符串，取其中首个元素，这样可以避免读入空字符的问题

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <cstdio>
const int NMAX = 1000005;

char s[NMAX], t[NMAX], b[5], c;
int n, x, p = 0, q = 0;
bool f[NMAX];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &x);
        if (x == 1)
        {
            scanf("%s", b), c = b[0];
            s[++p] = c;
            if (c == ')' && q && t[q] == '(')
                q--, f[p] = true;
            else if (c == ']' && q && t[q] == '[')
                q--, f[p] = true;
            else if (c == '}' && q && t[q] == '{')
                q--, f[p] = true;
            else
                t[++q] = c, f[p] = false;
        }
        else if (x == 2)
        {
            if (!p)
                continue;
            c = s[p];
            if (f[p])
            {
                if (c == ')')
                    t[++q] = '(';
                else if (c == ']')
                    t[++q] = '[';
                else if (c == '}')
                    t[++q] = '{';
            }
            else
                q--;
            p--;
        }
        else if (x == 3)
        {
            if (!p)
                continue;
            printf("%c\n", s[p]);
        }
        else if (x == 4)
        {
            printf("%s\n", q ? "NO" : "YES");
        }
    }
    return 0;
}