Appearance
括号匹配
为什么是栈，而不是计数器
括号的嵌套结构要求"最后出现的左括号最先被匹配"，这与栈的弹出顺序完全一致。
严蔚敏教材给了一个很好的直觉解释：把每个未匹配的左括号看成一份"期待"。读入第一个左括号后，程序期待着与它匹配的右括号；但如果等来的是第二个左括号，说明"第二份期待的急迫性高于第一份"，第一份只能暂时靠边；第三个左括号来了，第二份又要让位……每读入一个左括号，栈中所有未消解的期待急迫性都降一级；每读入一个右括号，栈顶那份最急迫的期待或者被消解，或者说明输入不合法。
"急迫性最高的最先被处理"就是 LIFO，所以承载它的只能是栈。
🔴 只有一种括号时，栈可以退化成一个计数器（遇
(加一、遇)减一，中途为负是右多、结束不为零是左多）；但两种以上的括号必须用栈。原因很具体：计数器只记得住"还欠几个右括号"，记不住"当前最内层欠的是哪一种"，所以判不出{[)}这类类型交叉。栈比计数器多记住的，是嵌套的"类型序列"，不只是"个数"。
三种失败，检测时机各不相同
| 失败类型 | 示例 | 检测时机 | 触发的判断语句 |
|---|---|---|---|
| 类型不匹配 | {[)} | 弹栈比较时（扫描中途） | !isPaired(topChar, ch) |
| 右括号多余 | ()) | 遇到右括号时（扫描中途） | top == -1 |
| 左括号多余 | (() | 扫描结束后 | return top == -1 |
前两种在扫描过程中就能立刻返回失败，第三种必须等到扫描结束——读完最后一个字符之前，你无法确定后面还会不会来右括号。所以"匹配成功"的判据是两条同时成立：扫描结束，且栈空。过程中一路无错但结束时栈非空，仍然是失败。
先看一眼
拿一个嵌套深的表达式和一个"平铺"的表达式（比如 ((((x)))) 和 ()()()()）各跑一遍，比较栈的最高水位。两者左括号一样多，栈深却差得远——下面那一节就是讲这件事。
算法与代码
从左到右扫描：遇左括号压栈；遇右括号先判栈空（空则右括号多余），再弹栈比类型（不配对则失败）；其他字符一律跳过。扫描结束后栈空则成功。
c
#include <stdbool.h>
#define MAX_SIZE 100
// 判断一对括号是否配对；必须定义在 bracketMatch 之前（或先给出函数声明）
bool isPaired(char left, char right) {
return (left == '(' && right == ')')
|| (left == '[' && right == ']')
|| (left == '{' && right == '}');
}
bool bracketMatch(const char *str) {
char stack[MAX_SIZE];
int top = -1; // 顺序栈，top 指向栈顶元素
for (int i = 0; str[i] != '\0'; i++) {
char ch = str[i];
if (ch == '(' || ch == '[' || ch == '{') {
if (top == MAX_SIZE - 1) // 栈满：嵌套层数超出容量
return false; // 顺序栈实现绕不开这一步
stack[++top] = ch; // 左括号入栈（前缀 ++，先移后写）
}
else if (ch == ')' || ch == ']' || ch == '}') {
if (top == -1) // 失败 2：右括号多余（栈空还要 pop）
return false;
char topChar = stack[top--]; // 弹栈（后缀 --，先取后移）
if (!isPaired(topChar, ch)) // 失败 1：类型不匹配
return false;
}
// 其他字符直接跳过
}
return top == -1; // 失败 3：栈非空说明左括号多余
}🔴
if (top == -1) return false;必须在弹栈之前。 先写stack[top--]再判断，空栈时会读stack[-1]——越界读，而且top还被改成了。这是"空栈时 Pop违反前置条件"这一条在代码上的落实。
三种失败与两个表达式的逐步跟踪（第一次学、或想手动模拟时展开）
{[()]} 的逐步跟踪：
| 步骤 | 当前字符 | 动作 | 栈内容（栈底→栈顶） |
|---|---|---|---|
| 1 | { | 左括号，入栈 | { |
| 2 | [ | 左括号，入栈 | { [ |
| 3 | ( | 左括号，入栈 | { [ ( |
| 4 | ) | 右括号，弹出 (，类型配对 ✓ | { [ |
| 5 | ] | 右括号，弹出 [，类型配对 ✓ | { |
| 6 | } | 右括号，弹出 {，类型配对 ✓ | 空 |
扫描结束，栈为空 → 匹配成功。栈的最大深度是 3，等于表达式的最大嵌套层数。
三种失败的逐步执行：
{[)}（类型不匹配）：{入栈 →[入栈（栈{ [）→ 读到)，栈非空， 弹出[，而[与)不配对 → 在第 3 个字符处失败。())（右括号多余）：(入栈 → 读到)，弹出(配对 ✓，栈空 → 再读到)，栈已空 → 在第 3 个字符处失败。(()（左括号多余）：(入栈 →(入栈（栈( (）→ 读到)，弹出配对 ✓（栈(）→ 扫描结束，栈非空 → 在扫描结束后才发现失败。
含其他字符的完整跟踪。真实表达式里还有操作数与运算符，它们一律跳过。 以 a * (b + [c - d]) / e 为例：
| 步 | 字符 | 类别 | 动作 | 栈（底→顶） |
|---|---|---|---|---|
| 1 | a | 其他 | 跳过 | 空 |
| 2 | * | 其他 | 跳过 | 空 |
| 3 | ( | 左括号 | 入栈 | ( |
| 4 | b | 其他 | 跳过 | ( |
| 5 | + | 其他 | 跳过 | ( |
| 6 | [ | 左括号 | 入栈 | ( [ |
| 7 | c | 其他 | 跳过 | ( [ |
| 8 | - | 其他 | 跳过 | ( [ |
| 9 | d | 其他 | 跳过 | ( [ |
| 10 | ] | 右括号 | 弹出 [，配对 ✓ | ( |
| 11 | ) | 右括号 | 弹出 (，配对 ✓ | 空 |
| 12 | / e | 其他 | 跳过 | 空 |
扫描结束、栈空 → 匹配成功。栈的最大深度是 2，出现在第 6
栈的最大深度 = 最大嵌套层数
这是本篇最有考点价值的一条，而且很容易记错：
🔴 栈的最大深度等于表达式的最大括号嵌套层数，不是左括号的总数。
()()()有 3 个左括号，栈深却始终只有 1；而((()))只有 3 个左括号，栈深就是 3。
原因在上面的跟踪表里一目了然：左括号入栈、右括号出栈，栈里任何时刻装的是"当前还没闭合的括号"，也就是当前所在的嵌套层数。平铺的括号开一个关一个，水位压根涨不起来。
由此直接得到空间复杂度：(((...(）时栈深达到 ()()()...() 这种同样长为
时间复杂度则是干净的
换成链栈实现，以及两处代码细节（写代码题时展开）
栈满检查是顺序栈实现必须带的：嵌套层数超过 MAX_SIZE 时若不检查就会越界写。 isPaired 要先定义或先声明：C99 之后不允许隐式声明函数，把它写在 bracketMatch 后面而又不给原型，编译不通过。
把数组换成《链栈》后，唯一消失的是栈满检查：
c
typedef struct SNode {
char data;
struct SNode *next;
} SNode;
bool bracketMatch_Link(const char *str) {
SNode *top = NULL; // 不带头结点，NULL 即空栈
bool ok = true;
for (int i = 0; str[i] != '\0' && ok; i++) {
char ch = str[i];
if (ch == '(' || ch == '[' || ch == '{') {
SNode *s = (SNode *)malloc(sizeof(SNode));
if (s == NULL) { ok = false; break; } // 取代"栈满"的失败来源
s->data = ch; s->next = top; top = s; // 头插入栈
} else if (ch == ')' || ch == ']' || ch == '}') {
if (top == NULL) { ok = false; break; } // 失败 2：右括号多余
SNode *p = top;
char topChar = p->data;
top = p->next;
free(p);
if (!isPaired(topChar, ch)) { ok = false; break; } // 失败 1
}
}
if (ok && top != NULL) ok = false; // 失败 3：左括号多余
while (top != NULL) { // 提前退出时也要清干净，避免泄漏
SNode *p = top; top = p->next; free(p);
}
return ok;
}多出来的那个 while 清栈循环值得注意：数组版直接 return false 就完事， 链栈版中途失败时栈里还挂着若干结点，不释放就泄漏。 这是链式实现相对顺序实现多出来的一项责任，代码题里容易漏。
同一套机制换个对象就是别的问题：只有一种括号时退化成计数器；把括号换成 XML/HTML 标签，配对判断从"字符配对"变成"字符串相等"，栈里存标签名；编译器的语法分析则是它的完整版，括号匹配是最简化的模型。
和表达式求值的联系：中缀转后缀时"遇到
)就不断弹出并输出，直到遇见("，本质上就是在做一次括号匹配——只不过弹出的东西还要输出。两篇的栈操作可以互相印证。
考点速记
三条会被反复调用的结论：
- 栈记住的是"类型序列"，计数器只记"个数"——这是"必须用栈"的准确理由。
- 三种失败的检测时机不同，左括号多余只能在扫描结束时发现。
- 栈的最大深度等于最大嵌套层数，不是左括号总数。
这一节在真题里被考过的形式（下方「真题练习」逐题对应）：
- 给定符号栈的容量，问哪个表达式处理不了。题面会说"符号栈初始为空、容量为 3"，然后给四个带括号的表达式。这类题问的不是括号配不配对（四个通常都是配对的），而是最大嵌套层数有没有超过容量——数一数每个表达式里"同时还没闭合"的括号最多有几层，超过容量的那个就是答案。
- 判断某段括号串是否合法，以及失败发生在第几个字符——按三种失败的检测时机逐字符走。
易错：把左括号总数当成栈的最大深度。
(a+b)*(c+d)*(e+f)有 3 个左括号，容量为 1 的栈就够用了。
易错：先弹栈再判空。 空栈时会读到
stack[-1]，且top变成。判空必须在弹栈之前。
易错：扫描过程无错就判成功。 还要看结束时栈空不空——左括号多余这一种失败，只有扫描结束后才暴露。
教材出处
- 括号匹配的"期待急迫性"分析（每读入一个左括号，栈中所有未消解的期待急迫性都降一级； 读入右括号时，或使栈顶最急迫的期待得以消解，或是不合法情况）： 严蔚敏《数据结构（C 语言版）》（第 2 版）p56「案例 3.2 括号匹配的检验」
- 顺序栈的入栈、出栈算法（本篇代码使用的栈操作）：同书 p58–p59
相关知识
顺序栈（top 约定与入栈出栈写法都来自那里）｜ 链栈（换成链栈就不需要判栈满）｜ 栈和队列的基本概念（Pop 的前置条件是"栈非空"）｜ 表达式求值（"遇 ) 弹到 ( 为止"就是一次括号匹配）｜ 栈在递归中的应用（语法分析也可用递归下降，隐式用系统栈）