Lesson 34: 括号匹配

练习任务

难度：易-中【重点】

用栈（Stack）判断字符串中的括号 ()[]{} 是否全部正确配对。

is_match(open, close) — 判断一对左右括号是否匹配（支持 ()、[]、{} 三种）。
check_brackets(s) — 遍历字符串，用数组栈检测括号是否全部正确配对。匹配返回 1，不匹配返回 0。

栈的基本操作（is_empty、push、pop）已由模板提供，你只需实现 is_match 和 check_brackets 的遍历逻辑。

本课共有 4 组测试用例：

输入 "()"       → 输出 "yes"   （基本配对）
输入 "()[]{}"   → 输出 "yes"   （多种括号）
输入 "([)]"     → 输出 "no"    （交叉嵌套错误）
输入 "("        → 输出 "no"    （左括号多余）

提示：括号匹配的核心规则是"就近配对"——每个右括号必须与最近未配对的左括号配对。这正是栈的 LIFO（后进先出）语义！遇到左括号入栈，遇到右括号与栈顶匹配——如果栈顶不是对应的左括号，或者栈已空，就是匹配失败。

核心知识点

栈的 LIFO 特性 — 后进先出，与括号"就近配对"特性天然对应
三种失败模式 — 右括号多余（遍历中栈空）、类型不匹配（栈顶与右括号不对应）、左括号多余（遍历结束后栈非空）
数组栈实现 — top = -1 哨兵表示空栈，push 用 ++top，pop 用 top--
O(n) 时空复杂度 — 每个字符入栈/出栈最多一次 → O(n) 时间复杂度；最坏情况全部左括号入栈 → O(n) 空间复杂度
为何队列/数组遍历不行 — 嵌套匹配需要"记住最近未配对的左括号"，队列的 FIFO 和数组的单向遍历无法处理嵌套层级
HTML/XML 标签匹配 — 本质上是同一个算法，只是栈中存储标签名字符串而非单字符
空字符串的数学直觉 — 空字符串应视为完美匹配，类似于"空集是集合论的基础"
is_match 的可扩展性 — 显式判断优于 ASCII 差值技巧，扩展新括号类型只需增加判断条件

代码框架

34_bracket_match.c

#include <stdio.h>
#include <string.h>
#define MAX 1024

int is_empty(int top) { return top == -1; }
void push(char *stack, int *top, char c) { stack[++(*top)] = c; }
char pop(char *stack, int *top) { return stack[(*top)--]; }

/* 判断 open 和 close 是否是一对匹配的括号
 * 支持 () [] {} 三种 */
int is_match(char open, char close)
{
    // 逐一检查三种配对：
    //   open == '(' && close == ')' → return 1
    //   open == '[' && close == ']' → return 1
    //   open == '{' && close == '}' → return 1
    // 都不匹配 → return 0
    // 在这里实现 is_match
}

/* 用栈检测括号是否全部正确配对 */
int check_brackets(const char *s)
{
    // 创建栈（char 数组 + top 索引）
    // char stack[MAX];
    // int top = -1;

    // 遍历字符串 s 的每个字符 *s：
    //   如果是左括号 ( [ { → push(stack, &top, *s)
    //   如果是右括号 ) ] } →
    //     若 is_empty(top) → return 0（右括号多余）
    //     若 !is_match(pop(stack, &top), *s) → return 0（类型不匹配）
    //   s++

    // 遍历结束后：
    //   return is_empty(top);  // 栈空=成功，栈非空=左括号多余
    // 在这里实现 check_brackets
}

int main(void)
{
    char s[MAX];
    fgets(s, sizeof(s), stdin);
    int i = 0;
    while (s[i] && s[i] != '\n') i++;
    s[i] = '\0';
    printf("%s\n", check_brackets(s) ? "yes" : "no");
    return 0;
}

阅读骨架后，尝试自己填充 // 在这里... 标记的部分。核心挑战在于：遍历中遇到右括号时，需要依次检查"栈是否为空"和"栈顶是否匹配"两个条件——漏掉任何一个都会出错。

TIP

先不要往下翻看参考解答。思考一下括号匹配问题的核心——"最近未配对的左括号"就是栈顶。如果不用栈，你能想出其他方案吗？那个方案能处理 "([)]" 这样的交叉嵌套吗？想清楚这个，你就理解了为什么这道题必须用栈。

深度讲解

1. 栈：LIFO 的数据结构

1.1 什么是栈——一摞盘子的直觉

栈（Stack）是一种后进先出（LIFO, Last In First Out）的数据结构。想象一摞盘子——最后放上去的盘子，最先被取下来。

操作序列: push(A) → push(B) → push(C) → pop() → pop()

栈状态变化:
  [ ]      [A]      [A]      [A]      [A]      [ ]
                      [B]      [B]      [B]
                               [C]
  
pop() 总是返回栈顶元素——即最后 push 的那个

栈有两个基本操作：

push（压栈）：把元素放到栈顶
pop（弹栈）：从栈顶取出元素

1.2 数组实现——top 哨兵与 ++/-- 操作

本题使用数组实现栈，top 索引指向栈顶元素的位置：

array_stack.c

#define MAX 1024
char stack[MAX];
int top = -1;               // -1 表示空栈

int  is_empty(int top)      { return top == -1; }
void push(char *stack, int *top, char c) { stack[++(*top)] = c; }
char pop(char *stack, int *top)          { return stack[(*top)--]; }

top 指针的三种状态:

  top = -1:    栈空     [ _ ][ _ ][ _ ]          is_empty → true
                          ↑
                        (无元素)
  
  top = 0:     1个元素   [ '(' ][ _ ][ _ ]       is_empty → false
                           ↑
                          top
  
  top = 2:     3个元素   [ '(' ]['['][ '{' ]     is_empty → false
                                    ↑
                                   top

为什么 push 用 ++top 而非 top++？

stack[++top] = c 等价于 top = top + 1; stack[top] = c——先让 top 向上移动到新位置，再放入元素。如果用 stack[top++] = c（后置自增），top 会在赋值后移动，导致元素被放入旧位置，指针留在不该留的地方。

++top (前置自增):            top++ (后置自增):
  top = -1                     top = -1
  stack[++top] = '('           stack[top++] = '('
  → top=0, stack[0]='(' ✓     → stack[-1]='(', top=0 ✗ 越界写入！

WARNING

数组栈的索引操作极易出错——越界（top 超出数组范围或退到 -1 以下）是未定义行为。本课练习不检查栈满，生产代码中必须加入 if (top >= MAX - 1) 的保护。

2. 为什么括号匹配天然适合栈

2.1 "就近配对" = LIFO

括号匹配有一个核心特性——每个右括号必须与"最近未配对的左括号"配对。这不是偶然的约定，而是任何嵌套结构的数学属性。

字符串: "{[()]}"

'{' → push  → stack = ['{']                         (遇到左括号，入栈)
'[' → push  → stack = ['{','[']                     (遇到左括号，入栈)
'(' → push  → stack = ['{','[','(']                 (遇到左括号，入栈)
')' → pop   → '(' → is_match('(',')')=1 → 配对! ✓
    stack = ['{','[']                               (栈顶被弹出)
']' → pop   → '[' → is_match('[',']')=1 → 配对! ✓
    stack = ['{']
'}' → pop   → '{' → is_match('{','}')=1 → 配对! ✓
    stack = []

遍历结束，栈空 → 全部匹配！→ yes ✓

核心洞察：最后遇到的左括号就是最先需要被右括号匹配的那个。如果你尝试用队列（FIFO）——第一个入队的左括号最先与到来的右括号配对——完全违背了嵌套层级。

2.2 三种失败模式的完整分析

所有括号匹配失败的情况都逃不出以下三类：

#	失败类型	检测时机	示例	含义
1	右括号多余	遍历中，pop 前栈已空	`"())"`	右括号比左括号多
2	类型不匹配	遍历中，pop 后类型不对	`"([)]"`	右括号与最近左括号不配对
3	左括号多余	遍历结束后栈非空	`"(()"`	左括号比右括号多

失败类型 1: "())"
  '(' → push, stack=['(']
  ')' → pop='(' → is_match ✓, stack=[]
  ')' → is_empty=1 → 栈空但有右括号 → no ✗

失败类型 2: "([)]"
  '(' → push, stack=['(']
  '[' → push, stack=['(','[']
  ')' → pop='[' → is_match('[',')')=0 → no ✗
  栈顶是 '[' 但遇到 ')'——正确嵌套应该是先关 ']' 再关 ')'

失败类型 3: "(()"
  '(' → push, stack=['(']
  '(' → push, stack=['(','(']
  ')' → pop='(' → is_match ， stack=['(']
  遍历结束，top=0 → 非空 → no ✗

IMPORTANT

三类失败缺一不可——漏掉任何一种都会导致算法在某些输入上给出错误结果。这是本课第一个需要彻底掌握的完整性检查。

3. 逐步跟踪：四个测试用例的完整推演

测试 1: `"()"` → yes（基本配对）

        ┌────┬────────────────────┬──────────────────┐
        │ 字符│ 操作                │ 栈状态 (top)      │
        ├────┼────────────────────┼──────────────────┤
        │    │                     │ [] (top=-1)      │
        │ '('│ push('(')              ['('] (top=0)    │
        │ ')'│ open=pop()='('      │ [] (top=-1)      │
        │    │ is_match('(',')')=1 │                  │
        └────┴────────────────────┴──────────────────┘
遍历结束，top=-1 → is_empty → yes ✓

测试 2: `"()[]{}"` → yes（多种括号混合）

        ┌────┬────────────────────┬──────────────────┐
        │ '('│ push('(')           │ ['('] (top=0)    │
        │ ')'│ pop='(' match()/[]  │ [] (top=-1)      │
        │ '['│ push('[')           │ ['['] (top=0)    │
        │ ']'│ pop='[' match[]/]   │ [] (top=-1)      │
        │ '{'│ push('{')              ['{'] (top=0)    │
        │ '}'│ pop='{' match{}/}   │ [] (top=-1)      │
        └───┴──────────────────────┴──────────────────┘
遍历结束，top=-1 → yes ✓

测试 3: `"([)]"` → no（交叉嵌套）

        ┌────┬────────────────────┬──────────────────┐
        │ '('│ push('(')           │ ['('] (top=0)    │
        │ '['│ push('[')           │ ['(','['] (top=1)│
        │ ')'│ open=pop()='['      │                  │
        │    │ is_match('[',')')=0 │ → return 0 no ✗  │
        └────┴────────────────────┴──────────────────┘

栈顶是 '['，但遇到的是 ')'！
这说明嵌套顺序错误——'(' 应该配对更后面的 ')'，而 '[' 应该先被 ']' 关闭。

测试 4: `"("` → no（左括号多余）

        ┌────┬────────────────────┬──────────────────┐
        │ '('│ push('(')              ['('] (top=0)    │
        └────┴────────────────────┴──────────────────┘
遍历结束，top=0 → 非空 → no ✗

栈中剩一个 '(' 等待配对，但字符串已经结束了。

4. 算法流程图解

check_brackets(s):
        ┌──────────────┐
        │ 初始化栈 []   │
        │ top = -1     │
        └──────┬───────┘
               │
        ┌──────▼───────┐
        │ 遍历 s 每个字符│ ← ═══ (循环) ═══
        └──────┬───────┘
               │
        ┌──────▼───────┐
        │ ch 是 '(' '[' │──(是)──→ push(ch) ──────┐
        │ 还是 '{'？    │                         │
        └──────┬───────┘                          │
               │ (不是)                            │
        ┌──────▼───────┐                          │
        │ ch 是 ')' ']'│                          │
        │ 还是 '}'？   │                          │
        └──────┬───────┘                          │
               │ (是)     (不是)                   │
        ┌──────▼───────┐  ┌───────────────┐        │
        │ is_empty(top) │  │ 非括号字符，  │        │
        │ 栈空？       │  │ 忽略，s++     │        │
        └──┬────────┬──┘  └───────┬───────┘        │
           │(是)    │(否)          │                │
    ┌──────▼──┐ ┌──▼──────────┐   │                │
    │ return 0│ │open = pop() │   │                │
    │ 右括多  │ │is_match?    │   │                │
    └─────────┘ └─────────┬──┘   │                │
                   │(否)   │(是)   │                │
            ┌──────▼──┐   └──┬──┘ │                │
            │ return 0│      │    │                │
            │ 型不配  │      │    │                │
            └─────────┘      │    │                │
                             │    │                │
                    ┌────────┴────┴──┐             │
                    │  s++ 继续遍历    │ ← ───────┘
                    └────────┬───────┘
                             │ (遍历结束)
                    ┌────────▼───────┐
                    │ is_empty(top)? │
                    └──┬──────────┬──┘
                       │(是)      │(否)
                ┌──────▼──┐ ┌─────▼──────┐
                │ return 1│ │ return 0   │
                │ 全部配对 │ │ 左括号多余 │
                └─────────┘ └────────────┘

5. 为什么不用队列或数组？（扩展思考）

初学者有时会问：能不能用更简单的数据结构？比如数组直接计数、或者队列？

5.1 数组直接计数——无法处理嵌套

counting_fails.c

// ❌ 尝试：用三个计数器分别统计 () [] {} 的数量
int round_open = 0, round_close = 0;
int square_open = 0, square_close = 0;
int curly_open = 0, curly_close = 0;

// 遍历字符串，分别累加
// 最后比较每种括号的开闭是否相等
// 
// 问题：对 "([)]" 这种情况，三组括号数量都相等：
//   ( 1个 ) 1个 → round_open==round_close ✓
//   [ 1个 ] 1个 → square_open==square_close ✓
//   但结果是 no! 因为出现了交叉嵌套。
//
// 计数器法丢失了「位置」信息——无法区分 "( ) [ ]" vs "([)+)]":
//   前者是合法嵌套，后者是非法交叉——计数器无法区分

5.2 队列（FIFO）——破坏了嵌套的层次感

队列处理 "{[()]}":

'{' 入队 → queue=['{']
'[' 入队 → queue=['{','[']
'(' 入队 → queue=['{','[','(']
')'? → 从队头取 → '{' → is_match('{',')')=0 → no ✗

这显然错了！'}' 应该与 '{' 配对，但必须是所有内部括号都关闭之后，
'{' 才是"最近待配对的左括号"。队列让最早进入的 '{' 与 ')' 配对，
完全违背了嵌套的层次结构。

数据结构	取出的元素	能处理嵌套吗	原因
栈	最后放入的（LIFO）	✓ 完全正确	"就近配对" = LIFO
队列	最先放入的（FIFO）	✗ 完全错误	最早入队的不是"最近"的
数组计数	不保留位置信息	✗ 无法区分	丢失了嵌套层级信息
递归	隐式栈（调用栈）	✓ 可以	递归本质是系统栈，等价方案

结论：嵌套结构的匹配问题，本质上是"后进先出"——任何 LIFO 结构都可以解决（栈、递归调用的调用栈），任何非 LIFO 结构都无法正确处理嵌套层级。

6. 扩展应用：HTML/XML 标签匹配

HTML/XML 的标签（如 <div>...</div>）匹配本质上是同一个算法——只是栈中存储的是标签名而不是单字符：

html_tag_match.c

// 概念代码（非本课要求实现）
#include <string.h>
#define MAX_TAGS 256

char *stack[MAX_TAGS];  // 栈中存储字符串指针（标签名）
int top = -1;

int check_html_tags(const char **tokens, int n)
{
    for (int i = 0; i < n; i++) {
        const char *tag = tokens[i];

        if (tag[0] != '/') {          // 开始标签: <div>, <p>, ...
            stack[++top] = tag;        // 入栈
        } else {                      // 结束标签: </div>, </p>, ...
            if (top == -1) return 0;   // 标签多余

            const char *open = stack[top--];
            if (strcmp(open, tag + 1) != 0)  // 去除 '/' 后比较
                return 0;              // 标签不匹配
        }
    }
    return top == -1;                  // 栈空 = 全部匹配
}

HTML 匹配示例: <div><p>hello</p></div>

<div> → push, stack=['div']
<p>   → push, stack=['div','p']
</p>  → pop='p' → strcmp('p','p')=0 ✓, stack=['div']
</div>→ pop='div' → strcmp('div','div')=0 ✓, stack=[]
栈空 → 标签全部正确配对 ✓

同一套算法，同类的问题——标签匹配比括号匹配多了一个变量大小的匹配键（标签名 vs 单字符），但核心逻辑完全不变。这正是数据结构课程中"用合适的抽象数据类型映射实际问题"的最佳范例。

7. 边界细节与常见误区

7.1 空字符串是匹配的吗？

是。空字符串不含任何括号，遍历循环不执行，栈保持为空（top == -1），算法返回 is_empty(top) → 1（yes）。

这与数学中的"空集类比"一致——空集是任何集合的子集，空括号序列也是任何合法嵌套的"基础情况"。类似地，只有左括号（没有右括号）不是匹配，因为栈非空意味着还有"未闭合的括号在等待"。

7.2 `is_match` 的两种实现风格

is_match_styles.c

// 风格 A: 显式逐对判断（推荐——清晰、易扩展）
int is_match(char open, char close)
{
    return (open == '(' && close == ')')
        || (open == '[' && close == ']')
        || (open == '{' && close == '}');
}

// 风格 B: ASCII 差值取巧（存在，但不推荐）
// () → ASCII 40/41 → 差 1
// [] → ASCII 91/93 → 差 2
// {} → ASCII 123/125 → 差 2
int is_match_tricky(char open, char close)
{
    return close - open == 1 || close - open == 2;
    // 问题1: 差值为1或2的字符不止括号（如 'P'(80) 与 'Q'(81)）
    // 问题2: 无法扩展 <>（ASCII 60/62 差 2 但含义是大于小于）
    // 本课输入仅含括号，所以差值法也能 pass——但不优雅
}

三种括号的 ASCII 码:

  括号  左 右  ASCII (左, 右)  差值
  ()    (  )  (40, 41)         1
  []    [  ]  (91, 93)         2
  {}    {  }  (123, 125)       2

NOTE

生产代码中用显式判断，不要依赖 ASCII 差值。当需求扩展为支持 <> 和 «» 等符号时，显式判断只需加一行，差值法则需要分析所有可能的冲突。

7.3 常见错误

错误	后果	正确做法
遇右括号不判栈空就直接 pop	访问 `stack[-1]` 越界	先 `if (is_empty(top)) return 0;`
遍历结束后不检查栈是否为空	多余左括号被漏掉	`return is_empty(top);`
`is_match` 只检查 `()` 一种括号	`[]{}` 永远返回 no	必须检查全部三种括号对
在 `check_brackets` 中修改了 `s`	破坏调用者的字符串	用 `const char *p = s` 的副本遍历
忘记处理非括号字符	可能错误地入栈/出栈	忽略非括号字符（本题保证只有括号和换行）

8. 复杂度分析

括号匹配算法的时间复杂度和空间复杂度都是 O(n)，其中 n 是字符串长度。

时间复杂度 O(n)：每个字符最多入栈一次、出栈一次——左括号入栈，右括号触发一次出栈。遍历字符串一次完成，所有操作（push/pop/判空/匹配）都是 O(1)。无论匹配成功还是中途失败（提前 return），总操作次数都不超过 2n。

时间复杂度分析:
  最优情况: 不匹配发生在第一个字符（如 ")"）→ O(1) 提前返回
  最坏情况: 全部匹配或全部左括号（如 "(((...") → 遍历全部 n 个字符 → O(n)
  平均情况: O(n) — 每个字符仍被处理一次

空间复杂度 O(n)：栈的大小取决于未配对的左括号数量。

最优 O(1) — 括号立刻匹配（如 "()()()"），每一步 push 后立即 pop，栈深度始终 ≤ 1。
最坏 O(n) — 输入全是左括号（如 "((((..."），所有字符入栈，栈增长到 n。
一般情况 — 栈的最大深度 = 字符串中最大嵌套层数（如 "{[()]}" 嵌套 3 层，栈深 3）。

这与 LIFO 的本质一致：栈"记住"了未配对的左括号，所需空间正好等于当前打开的括号嵌套深度。

参考解答

练习: is_match 和 check_brackets 完整实现

solution_34_bracket_match.c

#include <stdio.h>
#include <string.h>
#define MAX 1024

int is_empty(int top) { return top == -1; }
void push(char *stack, int *top, char c) { stack[++(*top)] = c; }
char pop(char *stack, int *top) { return stack[(*top)--]; }

/* 判断 open 和 close 是否是一对匹配的括号 */
int is_match(char open, char close)
{
    return (open == '(' && close == ')')
        || (open == '[' && close == ']')
        || (open == '{' && close == '}');
}

/* 用栈检测括号是否全部正确配对 */
int check_brackets(const char *s)
{
    char stack[MAX];
    int top = -1;

    while (*s) {
        if (*s == '(' || *s == '[' || *s == '{') {
            /* 左括号：入栈 */
            push(stack, &top, *s);
        } else if (*s == ')' || *s == ']' || *s == '}') {
            /* 右括号：先判栈空（失败类型1），再判匹配（失败类型2） */
            if (is_empty(top))
                return 0;                        /* 右括号多余 */
            char open = pop(stack, &top);
            if (!is_match(open, *s))
                return 0;                        /* 类型不匹配 */
        }
        /* 非括号字符忽略 */
        s++;
    }

    return is_empty(top);  /* 栈空=成功，非空=左括号多余（失败类型3） */
}

int main(void)
{
    char s[MAX];
    fgets(s, sizeof(s), stdin);
    int i = 0;
    while (s[i] && s[i] != '\n') i++;
    s[i] = '\0';
    printf("%s\n", check_brackets(s) ? "yes" : "no");
    return 0;
}

核心逻辑解析：

is_match 显式逐对判断：清晰、安全、易扩展。三种括号对一目了然。
check_brackets 的三重检查：遇到右括号时需依次验证"栈非空"和"类型匹配"两个条件；遍历结束后验证"栈为空"。
三类失败全覆盖：右括号多余在遍历中检出（is_empty(top) 为真），左括号多余在遍历后检出（is_empty(top) 为假），类型不匹配在比较时检出。

对照检查：is_match 中检查了全部三种括号对吗？check_brackets 中弹栈前判了栈空吗？遍历结束后 return is_empty(top) 了吗？

课堂讨论

如果只用一个计数器（比如 open_count 遇左括号 +1、右括号 -1）来判断匹配，为什么不行？具体的反例是什么？
当输入只有右括号（如 ")"）时，算法在第几步检测到错误？是哪种失败类型？
如何扩展本算法支持更多类型的括号（如 <>）？需要在哪些地方修改代码？
空字符串 "" 算匹配吗？为什么栈算法的结果与数学直觉一致？
如果把栈换成队列（Queue, FIFO），括号匹配的结果会怎样？以 "{[()]}" 为例逐步推演。

讨论答案

Q1: 为什么计数器不行？

计数器丢失了「嵌套顺序」信息，无法区分合法嵌套与非法交叉。

具体反例："([)]"。用一个 open_count 计数器（遇 ( 或 [ 或 { 时 +1，遇 ) 或 ] 或 } 时 -1）：

'(' → open_count = 1
'[' → open_count = 2
')' → open_count = 1
']' → open_count = 0

遍历结束，open_count == 0 → 计数器说"匹配"！
但实际上 "([)]" 是交叉嵌套，应该 no ✗

计数器的根本缺陷：它只记录了"开了多少括号"，不记得"是哪种括号、在什么位置开的"。嵌套匹配需要栈来保留了最近未配对的括号类型——这正是位置信息的关键。

Q2: 输入 ")" 在第几步检测到错误？

在第一个字符处就检测到错误，属于失败类型 1（右括号多余）。

遍历 ")":

  ch = ')': 是右括号 → 检查 is_empty(top)
            top = -1 → is_empty = true
            → return 0（失败类型 1：右括号多余）

没有进入 pop 操作——因为入队空的判断先发生，避免了访问 stack[-1]。

这也是为什么 is_empty 检查必须在 pop 之前——pop 假设栈非空，直接操作 stack[--top]，如果栈空会导致访问 stack[-1] 的未定义行为。

Q3: 如何扩展支持更多括号类型

只需在 is_match 函数中增加一个判断条件，核心算法完全不变。

int is_match(char open, char close)
{
    return (open == '(' && close == ')')
        || (open == '[' && close == ']')
        || (open == '{' && close == '}')
        || (open == '<' && close == '>');    /* 新增：尖括号 */
}

check_brackets 的遍历逻辑一行都不需要修改——这是良好抽象设计的体现：匹配逻辑被封装在 is_match 中，算法主体不关心有多少种括号类型。连 HTML 标签匹配（多字符）都只需要换一个 is_match 变成 strcmp，其他逻辑完全一样。

Q4: 空字符串算匹配吗？

算。空字符串不含任何括号，遍历循环不执行，栈保持初始状态 top == -1（空），is_empty(top) 返回 true → 匹配。

这与数学中的"空类比类"一致：

空集是任何集合的子集
空序列是任何合法嵌套的基础情况
0 是加法的单位元（0 + x = x，空序列拼上合法序列还是合法序列）

从集合论角度看，括号匹配可以看作一个函数：在任意位置上，已打开但未关闭的左括号集合为空时，序列就是"平衡"的。空字符串两端检查都通过——没有需要关注的左括号，自然平衡。

Q5: 队列（FIFO）处理括号匹配的结果

队列完全错误——它会把最早遇到的左括号与当前右括号配对，违背嵌套的层次结构。

以 "{[()]}" 为例逐步推演（队列：队尾入，队头出）：

'{' → 入队 → queue = ['{']
'[' → 入队 → queue = ['{', '[']
'(' → 入队 → queue = ['{', '[', '(']
')' → 出队 → open = '{' → is_match('{',')') = 0 → return no ✗

当然错了！')' 应该与 '(' 配对，但队列取出的是最早入队的 '{'。

核心原因：嵌套结构要求"最近的"左括号与右括号配对（LIFO），而队列提供的是"最早的"元素（FIFO）——这两个语义从根本上相悖。队列适合的场景是公平调度（如排队、BFS），括号匹配需要的是栈——数据结构的选择揭示了问题本身的结构特征。

课后练习

扩展：支持补充输出。修改 main 函数，在输出 yes 或 no 之外，当结果为 no 时额外输出失败原因（"多余右括号"、"类型不匹配"、"多余左括号"）。

知识点提示：将 check_brackets 的返回值从 int（0/1）扩展为 int（负值表示错误类型）。或者用额外的 error_type 变量记录失败原因。

参考解答

bracket_match_verbose.c

int check_brackets_verbose(const char *s, int *error_type)
{
    char stack[MAX];
    int top = -1;

    while (*s) {
        if (*s == '(' || *s == '[' || *s == '{') {
            push(stack, &top, *s);
        } else if (*s == ')' || *s == ']' || *s == '}') {
            if (is_empty(top)) {
                *error_type = 1;  /* 右括号多余 */
                return 0;
            }
            char open = pop(stack, &top);
            if (!is_match(open, *s)) {
                *error_type = 2;  /* 类型不匹配 */
                return 0;
            }
        }
        s++;
    }

    if (!is_empty(top)) {
        *error_type = 3;  /* 左括号多余 */
        return 0;
    }

    return 1;
}

int main(void)
{
    char s[MAX];
    fgets(s, sizeof(s), stdin);
    int i = 0;
    while (s[i] && s[i] != '\n') i++;
    s[i] = '\0';

    int error_type = 0;
    if (check_brackets_verbose(s, &error_type)) {
        printf("yes\n");
    } else {
        const char *msgs[] = {"", "右括号多余", "类型不匹配", "左括号多余"};
        printf("no (%s)\n", msgs[error_type]);
    }
    return 0;
}

手写栈实现。不依赖给定的 push/pop/is_empty 函数，在 check_brackets 内部直接操作 stack[++top] = c 和 stack[top--] 来管理栈。体会封装函数与直接操作的区别——什么时候封装更好？什么时候直接操作更高效？
知识点提示：直接操作省去函数调用开销，但代码可读性下降。在栈操作被频繁调用时（如编译器），内联或宏改写可以兼顾性能与可读性。
参考解答
inline_stack.c
c
```
int check_brackets_inline(const char *s)
{
    char stack[MAX];
    int top = -1;

    while (*s) {
        if (*s == '(' || *s == '[' || *s == '{') {
            stack[++top] = *s;          /* 直接 push */
        } else if (*s == ')' || *s == ']' || *s == '}') {
            if (top == -1) return 0;    /* 直接判空 */
            char open = stack[top--];   /* 直接 pop */
            if (!is_match(open, *s))
                return 0;
        }
        s++;
    }

    return top == -1;
}
```
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
直接操作的优点：省去了 push/pop/is_empty 三个函数调用（每次调用有压栈/跳转开销）。缺点：代码逻辑与数组操作耦合，如果以后想把数组栈换成链式栈，需要修改所有直接操作的位置。本课练习用函数封装是为了让初学者更清晰地理解"什么是栈操作"——而在性能敏感的实际项目中，直接操作或宏展开更常见。

括号位置追踪。修改算法，不仅判断匹配与否，还要输出第一处不匹配的位置和原因。例如输入 "a(b]c"，输出 "位置3:括号类型不匹配"。输入 "a(b"，输出 "位置2:左括号未关闭"。

知识点提示：需要额外记录"左括号在字符串中的位置"。栈中同时存储字符和位置——可以用结构体或两个并列数组。失败时取出位置信息输出。

参考解答

bracket_position.c

int check_brackets_pos(const char *s, int *pos, int *err)
{
    char stack[MAX];
    int positions[MAX];  /* 记录每个左括号在字符串中的位置 */
    int top = -1;

    for (int i = 0; s[i]; i++) {
        if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
            stack[++top] = s[i];
            positions[top] = i;          /* 记录位置 */
        } else if (s[i] == ')' || s[i] == ']' || s[i] == '}') {
            if (top == -1) {
                *pos = i;
                *err = 1;  /* 右括号多余 */
                return 0;
            }
            char open = stack[top--];
            if (!is_match(open, s[i])) {
                *pos = i;
                *err = 2;  /* 位置 i 处类型不匹配 */
                return 0;
            }
        }
    }

    if (top != -1) {
        *pos = positions[0];  /* 第一个未关闭的左括号的位置 */
        *err = 3;            /* 左括号未关闭 */
        return 0;
    }

    return 1;
}

扩展阅读：编译原理中的括号匹配。阅读编译器前端的词法分析与语法分析资料，理解括号匹配在以下场景中的应用：(a) C 语言中 { } 块的作用域划分，(b) 正则表达式中 ( ) 分组与 [ ] 字符类的嵌套规则，(c) JSON 格式中 { } 和 [ ] 的嵌套合法性检查。总结它们与本课算法的异同。
知识点提示：编译原理中括号匹配是语法分析的基础——虽然实际编译器使用上下文无关文法（CFG）和 LR/LALR 解析策略，但"左右括号配对"的直觉是所有解析算法的起点。JSON 验证器本质上就是加强版的括号匹配。

参考资料

《数据结构与算法分析 — C 语言描述》§3.3 — 栈 ADT 的定义、实现与应用，包括括号匹配的完整分析
K&R《C 程序设计语言》§4.3 — 栈的外部变量实现，包含 push/pop 的经典写法
LeetCode 20: Valid Parentheses — 括号匹配的在线练习平台，包含数百个社区解法对比
ISO C99 Standard, §6.4.1 — C 语言中括号、花括号、方括号的语法定义及其在语言设计中的角色
编译原理龙书 (Dragon Book) §2.2 — 上下文无关文法与括号嵌套的语言学基础

"Programs must be written for people to read, and only incidentally for machines to execute." — Harold Abelson and Gerald Jay Sussman

Lesson 34: 括号匹配 ​

练习任务 ​

核心知识点 ​

代码框架 ​

深度讲解 ​

1. 栈：LIFO 的数据结构 ​

1.1 什么是栈——一摞盘子的直觉 ​

1.2 数组实现——top 哨兵与 ++/-- 操作 ​

2. 为什么括号匹配天然适合栈 ​

2.1 "就近配对" = LIFO ​

2.2 三种失败模式的完整分析 ​

3. 逐步跟踪：四个测试用例的完整推演 ​

测试 1: "()" → yes（基本配对） ​

测试 2: "()[]{}" → yes（多种括号混合） ​

测试 3: "([)]" → no（交叉嵌套） ​

测试 4: "(" → no（左括号多余） ​

4. 算法流程图解 ​

5. 为什么不用队列或数组？（扩展思考） ​

5.1 数组直接计数——无法处理嵌套 ​

5.2 队列（FIFO）——破坏了嵌套的层次感 ​

6. 扩展应用：HTML/XML 标签匹配 ​

7. 边界细节与常见误区 ​

7.1 空字符串是匹配的吗？ ​

7.2 is_match 的两种实现风格 ​

7.3 常见错误 ​

8. 复杂度分析 ​

参考解答 ​

课堂讨论 ​

讨论答案 ​

课后练习 ​

参考资料 ​

Lesson 34: 括号匹配

练习任务

核心知识点

代码框架

深度讲解

1. 栈：LIFO 的数据结构

1.1 什么是栈——一摞盘子的直觉

1.2 数组实现——top 哨兵与 ++/-- 操作

2. 为什么括号匹配天然适合栈

2.1 "就近配对" = LIFO

2.2 三种失败模式的完整分析

3. 逐步跟踪：四个测试用例的完整推演

测试 1: `"()"` → yes（基本配对）

测试 2: `"()[]{}"` → yes（多种括号混合）

测试 3: `"([)]"` → no（交叉嵌套）

测试 4: `"("` → no（左括号多余）

4. 算法流程图解

5. 为什么不用队列或数组？（扩展思考）

5.1 数组直接计数——无法处理嵌套

5.2 队列（FIFO）——破坏了嵌套的层次感

6. 扩展应用：HTML/XML 标签匹配

7. 边界细节与常见误区

7.1 空字符串是匹配的吗？

7.2 `is_match` 的两种实现风格

7.3 常见错误

8. 复杂度分析

参考解答

课堂讨论

讨论答案

课后练习

参考资料