Appearance
括号匹配
为什么需要括号匹配
括号匹配是编译器语法检查中最基础的任务之一。无论是数学表达式 ((a+b)*c) 还是程序代码中的 {}、[]，括号必须成对出现、正确嵌套，否则表达式非法。
括号匹配问题是栈的经典应用场景。408 考研中，它既是理解栈的 LIFO 特性的最佳切入点，也是算法设计题的常考内容。
核心思想
栈的**后进先出（LIFO）**特性天然适合处理括号的嵌套结构：
- 括号的嵌套规则要求最后出现的左括号最先被匹配，这与栈的弹出顺序完全一致
- 遇到左括号就入栈"记住"，遇到右括号就弹栈"配对"，流程简洁直观
基本原则：
- 左括号：压入栈中，等待后续匹配
- 右括号：弹出栈顶元素，检查是否与当前右括号配对
- 扫描结束：栈为空则匹配成功，栈非空则存在未匹配的左括号
交互可视化
通过下方的交互动画，你可以逐步观察括号匹配的执行过程：
操作详解
算法思路
- 初始化一个空栈
- 从左到右依次扫描表达式中的每个字符
- 遇到左括号
(、[、{：将其压入栈 - 遇到右括号
)、]、}：- 若栈为空，说明右括号多余，匹配失败
- 若栈非空，弹出栈顶元素，检查是否与当前右括号配对
- 若不配对，匹配失败
- 扫描结束后，若栈为空则匹配成功，否则说明左括号多余，匹配失败
匹配过程详解
以表达式 {[()]} 为例，匹配过程如下：
| 步骤 | 当前字符 | 动作 | 栈内容（栈底→栈顶） |
|---|---|---|---|
| 1 | { | 左括号，入栈 | { |
| 2 | [ | 左括号，入栈 | { [ |
| 3 | ( | 左括号，入栈 | { [ ( |
| 4 | ) | 右括号，弹出 ( 配对成功 | { [ |
| 5 | ] | 右括号，弹出 [ 配对成功 | { |
| 6 | } | 右括号，弹出 { 配对成功 | 空 |
扫描结束，栈为空，匹配成功。
失败情况分析
括号匹配失败共有三种情况：
| 失败类型 | 示例 | 检测时机 | 原因 |
|---|---|---|---|
| 括号不匹配 | {[)} | 弹栈比较时 | 栈顶左括号与当前右括号类型不对应 |
| 右括号多余 | ()) | 遇到右括号时 | 栈已空但仍有右括号待匹配 |
| 左括号多余 | (() | 扫描结束时 | 表达式结束但栈中仍有左括号 |
代码实现（C 语言风格）：
c
bool bracketMatch(const char* str) {
char stack[MAX_SIZE];
int top = -1;
for (int i = 0; str[i] != '\0'; i++) {
char ch = str[i];
// 左括号入栈
if (ch == '(' || ch == '[' || ch == '{') {
stack[++top] = ch;
}
// 右括号：弹栈并比较
else if (ch == ')' || ch == ']' || ch == '}') {
if (top == -1) // 失败情况 2：右括号多余
return false;
char topChar = stack[top--];
// 失败情况 1：括号不匹配
if (!isPaired(topChar, ch))
return false;
}
}
return top == -1; // 失败情况 3：栈非空则左括号多余
}
bool isPaired(char left, char right) {
return (left == '(' && right == ')')
|| (left == '[' && right == ']')
|| (left == '{' && right == '}');
}复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n) | 每个字符仅扫描一次，入栈/出栈均为 O(1) |
| 空间复杂度 | O(n) | 最坏情况下全部为左括号，栈深度为 n |
考研高频考点
- ⭐ 括号匹配为什么用栈（LIFO 与嵌套结构的对应关系，选择题/简答题）
- ⭐ 三种匹配失败情况的判断（选择题高频，需区分检测时机）
- ⭐ 手动模拟匹配过程（给定表达式，画出栈的变化，填空题/大题）
- 算法的时间与空间复杂度分析（选择题）
- 括号匹配算法的代码实现（算法设计题）