表达式括号匹配(stack)

形式化题目

给定一个长度小于 255 的字符串 $s$ ，字符取自小写字母、四则运算符 + - * /、左右圆括号以及结束符 @。要求判断： $s$ 中 @ 之前的圆括号是否匹配。

只关心括号时，问题可以写成前缀和的形状。令 $s$ 中 @ 之前的这部分为 $t$ （长度 $n$ ），定义第 $i$ 个字符处的前缀值

d_i = \#\{\, j \leqslant i : t_j = \texttt{(} \,\} - \#\{\, j \leqslant i : t_j = \texttt{)} \,\}, \qquad d_0 = 0 ,

即"扫到第 $i$ 个字符时还有多少个左括号在等待配对"。匹配当且仅当两条同时成立：

d_i \geqslant 0 \quad (0 \leqslant i \leqslant n), \qquad d_n = 0 .

第一条排除"右括号比它左边的左括号多"的情况，第二条排除"左括号剩下来没人配"的情况。字母、运算符和空白都不改变 $d$ 的值，属于无关字符。题面另给两个有用约束： $n < 255$ ，且左括号少于 20 个（因此 $d_i \leqslant 19$ ）。

两个样例的括号序列与 $d$ 的变化如下表（只列出圆括号，无关字符已省略）：

样例	表达式	括号序列	$d$ 的变化	判定
1	`2*(x+y)/(1-x)@`	`( ) ( )`	$0 \to 1 \to 0 \to 1 \to 0$	处处 $\geqslant 0$ 且收尾 0 → `YES`
2	`(25+x)(a(a+b+b)@`	`( ) ( ( )`	$0 \to 1 \to 0 \to 1 \to 2 \to 1$	收尾 $d_n = 1 \neq 0$ → `NO`

正解

思路

这道题其实在问什么？ 把左括号看作"开始一件事"、右括号看作"结束一件事"，括号匹配就是"每个结束都能对应上一个尚未结束的开始，且最后没有悬空的开始"。这正是 LIFO 结构，也就是栈：遇到左括号把它压栈，遇到右括号就把栈顶的左括号弹掉配对。配不上（栈空）或者配完还剩（栈非空）都是 NO。

关键观察：栈里放的永远是同一种字符。 因为只有左括号会入栈、右括号只会让栈变浅，栈的内容从头到尾就是一串 (。既然元素都一样，"栈里还剩几个左括号"这一个整数就完整描述了栈的状态，根本不需要真的把字符存下来——这个数就是上面的 $d_i$ 。于是整个算法退化成一次线性扫描：

从左往右读字符，读到 @ 立刻停（@ 之后的内容按题面属于表达式之外）；
遇到 ( 就 d += 1；遇到 ) 就 d -= 1，若减完 d < 0 说明此刻这个右括号没有左括号可配，直接判 NO——它左边的左括号已经全部用完，后面再出现多少左括号也补不到它前面去；
扫描结束看 d 是否为 0：不为 0 说明有左括号始终没等到右括号，判 NO。

为什么不能只数括号个数，也不能“允许反向配对”？ 数量相等只是必要条件，反例是 )(：左、右括号各一个、数量相等，但第一个字符就是右括号，一上来 $d_1 = -1$ 。所以第 2 步必须边扫边判、中途退出，把判断全部留到最后是错的。反过来，还有一种 “栈空时遇到 ) 把差距也加一，最后看两者是否抵消”的写法，把多余的右括号当成了一个可以 “以后再配”的左括号，同样会错。拿下面这串输入试一下就知道它为什么错：

text

1(1000+(100+(10+1))))*(a-(b-(c-d))))@

它的括号序列是 ((())))((())))。正解遇到第 4 个 ) 时 $d$ 就掉到 $-1$ ，立刻报 NO （ $d$ 在 8 个 ) 处依次取 $2, 1, 0, -1, 1, 0, -1, -2$ ）；而“抵消式”写法会把第 7 个括号（即第 4 个 )）当成一个新的左括号，让 top 从 0 反弹回 1；剩下的 ((()))) 是三个左括号加四个右括号，净效果正好 $-1$ ，又把 top 带回 0。收尾碰巧 top == 0，于是把 NO 误判成 YES。根因在于括号的配对次序：多余的右括号必须当场报错，它后面的左括号跟它没有任何配对关系。

读入为什么按整行读？ 表达式里可能出现空格（题面没保证没有），按空白分词会把一整条表达式切成好几段，所以 C++ 用 getline、Python 用 read().partition('@') 整行取到 @ 为止。

代码

Python 版把“栈高处处非负”写成括号增量的前缀和，用 all 边算边短路：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 15:17
# update_at: 2026-10-07 15:28

import sys
from itertools import accumulate

END = '@'                  # 表达式结束标志，它之后的内容（换行、多余空白）一律不看
DELTA = {'(': 1, ')': -1}  # 圆括号对栈高的增量；字母、运算符、空格都不改变栈高


def is_matched(expr: str) -> bool:
    """括号是否匹配：栈高处处非负（没有多余的右括号），且收尾归零（没有多余的左括号）。

    栈里只放左括号，所以"还剩几个左括号"这一个数就够描述状态，不必真的把字符压进栈；
    每个位置上的栈高就是增量的前缀和，收尾栈高恰好等于全部增量之和。
    """
    deltas = [DELTA.get(ch, 0) for ch in expr]                # 每个字符对栈高的增量
    never_negative = all(h >= 0 for h in accumulate(deltas))  # all 一碰到负前缀就短路
    balanced_total = sum(deltas) == 0                         # 总增量 = 左右括号个数之差
    return never_negative and balanced_total


def solve() -> None:
    data = sys.stdin.buffer.read().decode()
    # 表达式内部可能有空格，按 token 读会被切开，所以整行读入后截到 @ 为止
    body = data.partition(END)[0]
    print('YES' if is_matched(body) else 'NO')


if __name__ == "__main__":
    solve()

C++ 版（同一算法，显式栈 + 中途提前返回）：

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 15:15
 * update_at: 2026-10-07 15:27
 */
// main.cpp：表达式括号匹配。从左往右扫到 @ 为止，左括号入栈、右括号必须配掉栈顶左括号；
// 中途栈空（右括号多余）或收尾栈非空（左括号多余）都判 NO。与 main.py 同一算法。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const char END_MARK = '@'; // 表达式结束标志，它之后的内容一律不看
const char LEFT_BRACKET = '(';  // 左圆括号：入栈
const char RIGHT_BRACKET = ')';  // 右圆括号：与栈顶左括号配对出栈
const int MAXL = 300; // 表达式长度 < 255；栈里只放左括号，栈深最多 19

char stack_buf[MAXL]; // 栈：从栈底到栈顶依次是还没等到右括号的左括号，全是 '('
ll top;               // 栈内元素个数，栈顶是 stack_buf[top - 1]；top == 0 表示栈空

// 判断 @ 之前的括号是否匹配：前缀中不能出现无左括号可配的右括号，收尾时栈必须为空。
bool is_matched(const string &expr) {
    top = 0;
    ll len = expr.size();
    for (ll i = 0; i < len; i++) {
        char ch = expr[i];
        if (ch == END_MARK) break; // @ 之后的内容一律不看
        if (ch == LEFT_BRACKET) {
            stack_buf[top++] = ch; // 左括号入栈，等一个右括号来配它
        } else if (ch == RIGHT_BRACKET) {
            if (top == 0) return false; // 栈空说明这个右括号没有左括号可配，必错
            top--;                      // 与栈顶左括号配成一对，出栈
        }
    }
    return top == 0; // 收尾栈空才算全部配完；还剩左括号就是左括号多余
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string expr;
    getline(cin, expr); // 整行读入，字母、运算符、括号和空格都原样保留

    cout << (is_matched(expr) ? "YES" : "NO") << "\n";

    return 0;
}

复杂度

时间：只扫一遍字符串，每个字符常数次操作， $O(n)$ ，其中 $n < 255$ 。 C++ 遇到多余的右括号会立即 return，Python 的 all 也会在此短路，所以实际扫描长度往往还不到 $n$ 。
空间：C++ 的栈里只有左括号，而题面限制左括号 $< 20$ 个，用 char stack_buf[300] 静态数组， $O(n)$ 且实际占用不足 300 字节；Python 的增量列表长度为 $n$ ，同样 $O(n)$ ，本题规模下不足 1 KB。实测峰值内存 C++ 约 8.4 MB、Python 约 14.6 MB（限时 128 MB）。
与 C++ 解法的关系：main.cpp 是同一算法的 C++ 版本，用显式栈代替栈高计数器，逻辑与 main.py 逐句对应（扫到 @ 停、右括号遇空栈就 false、收尾看栈是否为空），复杂度同为 $O(n)$ 。本题数据极弱（每组不到 45 字节），两种语言都不存在 TLE/MLE 风险。

总结

括号匹配 = 栈：左括号入栈、右括号弹栈配对，栈空时遇右括号或收尾栈非空都判错。这个模型是后面所有栈类题（后缀表达式求值、单调栈）的起点。
栈里只有一种字符时，栈高就是全部状态：本题的栈永远只装 (，于是"栈"退化成一个整数 $d$ ，判断条件化为"前缀处处非负 + 收尾归零"两条不等式。识别出这种退化能省掉整个数据结构。
边扫边判，别只看总数：)( 这类输入左右括号数量相等却不匹配，说明必须检查每一个前缀，而不是最后一个前缀值。
无关字符不影响状态：字母和 + - * / 既不改变栈高也不参与判定，遇到它们直接跳过即可；真正需要小心的是读入方式——表达式可能含空格，要按整行读。

表达式括号匹配(stack)

目录

形式化题目

正解

思路

代码

复杂度

总结