Lecture 9：栈在括号匹配中的应用

This note is currently available in Chinese. The original wording, formulas and diagrams are preserved to avoid an unverified technical translation.

9.1 括号匹配问题

9.1.1 基本概念

定义：#括号匹配

描述：括号匹配是判断一串括号中的左括号和右括号是否能够按类型、顺序一一对应。

常见括号类型

小括号： $$ (\quad ) $$
中括号： $$ [\quad ] $$
大括号： $$ {\quad } $$

为什么用栈

后出现的左括号要先被匹配。
这正好符合栈的后进先出规则： $$ \text{LIFO} $$
因此可以用栈保存“还没有被匹配的左括号”。

图示解读

每遇到一个左括号就入栈；每遇到一个右括号，就与最近尚未匹配的左括号比较。
栈顶保存“最内层、最晚出现”的未匹配左括号，因此嵌套括号恰好符合 LIFO。
扫描中出现栈空、括号类型不一致，或扫描结束后栈仍非空，均表示匹配失败。

9.2 括号匹配的核心规则

9.2.1 扫描左括号

当输入字符是左括号时，将其压入栈中。
左括号包括： $$ (\quad [\quad { $$

含义

当前左括号还没有遇到对应的右括号。
暂时把它存入栈，等待后续匹配。

9.2.2 扫描右括号

当输入字符是右括号时，需要让栈顶的左括号出栈。
右括号包括： $$ )\quad ]\quad } $$

匹配关系

当前右括号	栈顶必须是
`)`	`(`
`]`	`[`
`}`	`{`

原因

当前右括号只能匹配离它最近、还未匹配的左括号。
这个“最近的未匹配左括号”就在栈顶。

9.2.3 扫描结束

处理完所有输入字符后，如果栈为空，说明所有左括号都已匹配。
如果栈非空，说明仍然有左括号没有被匹配。

扫描结束后的判定： $$ \text{栈空}\Rightarrow \text{匹配成功} $$

$$ \text{栈非空}\Rightarrow \text{匹配失败} $$

9.3 三种匹配失败情况

9.3.1 右括号多余

情况

扫描到右括号时，栈已经为空。

原因

没有可用的左括号与当前右括号匹配。

例子

())

扫描到最后一个 ) 时，栈中已经没有 (。

9.3.2 左右括号类型不匹配

情况

扫描到右括号时，栈非空。
但栈顶左括号和当前右括号不是同一类。

例子

([)]

当扫描到 ) 时，栈顶是 [，但 ) 需要匹配 (。

9.3.3 左括号多余

情况

所有字符都扫描完以后，栈仍然非空。

原因

栈中剩下的左括号没有对应的右括号。

例子

(()

或者：

((()

扫描结束后仍有未匹配的左括号。

9.4 算法实现

9.4.1 栈结构

原 PDF 提醒：考试中可以直接使用已经定义好的接口名，也可以在代码旁边写出中文含义注释。

本节接口形参中的 &S、&x 是 C++ 引用，不是 C 函数形参；MaxSize=10 只是课件的固定容量示例。完整算法假定同一时刻未匹配左括号数不超过 MaxSize，若要处理任意长度输入，应使用可扩容栈。容量不足与括号不匹配是两种不同原因，不能混为一谈。

栈结构定义

#define MaxSize 10

typedef struct {
    char data[MaxSize];  // 静态数组存放栈中元素
    int top;             // 栈顶指针
} SqStack;

需要使用的接口

void InitStack(SqStack &S);
bool StackEmpty(SqStack S);
bool Push(SqStack &S, char x);
bool Pop(SqStack &S, char &x);

接口含义

InitStack(S)：初始化栈。
StackEmpty(S)：判断栈是否为空。
Push(S, x)：把字符 x 入栈。
Pop(S, x)：栈顶元素出栈，并用 x 返回。

9.4.2 完整算法

bool bracketCheck(char str[], int length) {
    SqStack S;
    InitStack(S);

    for (int i = 0; i < length; i++) {
        if (str[i] == '(' || str[i] == '[' || str[i] == '{') {
            if (!Push(S, str[i]))
                return false;  // 固定栈容量不足；不代表括号本身不匹配
        } else if (str[i] == ')' || str[i] == ']' || str[i] == '}') {
            if (StackEmpty(S))
                return false;

            char topElem;
            Pop(S, topElem);

            if (str[i] == ')' && topElem != '(')
                return false;

            if (str[i] == ']' && topElem != '[')
                return false;

            if (str[i] == '}' && topElem != '{')
                return false;
        }
    }

    return StackEmpty(S);
}

上述版本允许输入中包含普通字符：普通字符会被跳过。若题目已保证输入只含六种括号，也可以把 else if 简写为 else。

说明

扫描左括号：

Push(S, str[i]);

扫描右括号时，如果栈空：

return false;

扫描右括号时，如果类型不匹配：

return false;

扫描结束后：

return StackEmpty(S);

9.4.3 PDF 代码中的写法修正

原 PDF 中有些地方是课件简写或 OCR 识别结果，正式写题时建议修正为规范形式。

位置	应写成	原因
`for(int i=0,i<length;i++)`	`for (int i = 0; i < length; i++)`	`for` 的三段表达式用分号隔开
`topElem = Pop(S);`	`Pop(S, topElem);`	前文接口是用引用参数返回出栈元素
`topElem != '[]'`	`topElem != '['`	栈中保存的是单个字符

9.5 题型整理

题型：#括号匹配判断

第一部分：解题方法

从左到右扫描字符串。
遇到左括号就入栈。
遇到右括号先看栈是否为空。
若栈空，说明右括号多余，匹配失败。
若栈非空，弹出栈顶左括号并检查类型。
类型不匹配，匹配失败。
全部扫描完成后，检查栈是否为空。
栈空则匹配成功，栈非空则匹配失败。

第二部分：典型例题

例题 1：判断 ([]{}) 是否匹配

扫描过程：

字符	操作	栈内未匹配左括号
`(`	入栈	`(`
`[`	入栈	`([`
`]`	匹配 `[`，出栈	`(`
`{`	入栈	`({`
`}`	匹配 `{`，出栈	`(`
`)`	匹配 `(`，出栈	空

结果： $$ \text{匹配成功} $$

例题 2：判断 ([)] 是否匹配