题解：【YACS 2022年 1 月月赛丙组】平衡括号

归档56

题解34 未分类7 游寄6 “你需要知道的一切”系列4 博客指南3 网络前端1 闲话1

537 字

3 分钟

题解：【YACS 2022年 1 月月赛丙组】平衡括号

2024-06-27

2026-10-03

浏览量加载中...

前情提要：这个题是栈的经典入门题。

关于栈的详细内容可以看 OI-Wiki，这里简单说一下。

其实栈（stack）就相当于一个桶，有两种操作：从顶上（top）往里边扔东西（push）和拿东西（pop），底部不允许操作（不然就漏了）。

这里就有 $3$ 种操作了：

top：用来获取最上方的东西
push：扔东西进去
pop：拿东西出来

所以这个题就可以用栈解决了，具体步骤如下：

遍历字符串
如果栈是空的（empty），那么直接放东西（学名：入栈）
如果这个字符和栈顶（上一个待匹配的字符）匹配，那么栈顶出去（学名：出栈）
如果不匹配，那么就加进去
对每个字符进行操作 2~4（显然只会执行一个），此时匹配的已经不在栈中，栈里只有不匹配的。如果栈里没东西，那么说明都匹配了，是平衡的；如果有，那就是不平衡的。

这里，这个栈就是用来存储不匹配的括号的。

正确性证明：题目的意思是“就近匹配”，即括号优先分配给最近的且匹配的。那么栈先进后出的结构正好符合该项原则。

ACCode：

1
/*Code by Block_fish*/
2
#include <bits/stdc++.h>
3

4
#define log printf
5
#define EPS 1e-8
6
#define INF 0x3f3f3f3f
7
#define FOR(i, l, r) for (int(i) = (l); (i) <= (r); ++(i))
8
#define IOS                      \
9
  ios::sync_with_stdio(false); \
10
  cin.tie(nullptr);            \
11
  cout.tie(nullptr);
12

13
using namespace std;
14

15
typedef __int128 i128;
16
typedef long long ll;
17
typedef pair<int, int> PII;
18

19
int len;
20
stack<char> stk;
21
string s;
22

23
template <typename T>
24

25
inline T read() {
26
  T sum = 0, fl = 1;
27
  char ch = getchar();
28
  for (; !isdigit(ch); ch = getchar())
29
    if (ch == '-') fl = -1;
30
  for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
31
  return sum * fl;
32
}
33

34
template <typename T>
35

36
inline void write(T x) {
37
  if (x < 0) {
38
    putchar('-'), write<T>(-x);
39
    return;
40
  }
41
  static T sta[35];
42
  int top = 0;
43
  do { sta[top++] = x % 10, x /= 10; } while (x);
44
  while (top) putchar(sta[--top] + 48);
45
}
46

47
int main() {
48
  IOS;
49
  cin >> s;
50
  len = s.size();
51
  for (int i = 0; i < len; ++i) {
52
    if (stk.empty()) stk.push(s[i]);
53
    else if ((stk.top() == '[' && s[i] == ']') || (stk.top() == '(' && s[i] == ')')) stk.pop();
54
    else stk.push(s[i]);
55
  }
56
  if (stk.size()) cout << "Unbalanced";
57
  else cout << "Balanced";
58
  return 0;
59
}