1. 为什么括号匹配是栈最经典的入门场景括号匹配这道题几乎每个刷过题、面过试的程序员都不陌生——栈、括号匹配、左括号入栈、右括号弹栈比对满打满算十来行代码。但说句实话我在面试别人的时候真能一遍写对的人其实不多大部分人纠结的不是思路而是各种边角情况第一个字符就是右括号怎么办字符串遍历完了栈里还有东西怎么办左右括号类型对不上怎么办这些细节恰恰是这道题的精髓。先说清楚题目本身避免后面云里雾里。给一个字符串里面只包含( ) [ ] { }这六种字符判断括号的嵌套顺序是否合法。合法意味着每一个右括号都能恰好配上一个最近的、尚未匹配的左括号并且类型一致。比如([{}])合法([)]不合法(([]))合法)(不合法。直观感受一下([)]里下标 0 的(和下标 3 的)能配对但中间的[却先和)相遇了这种交叉嵌套在括号体系里是被禁止的。这个场景离我们太近了。编译器解析源代码时要检查语法括号是否配平IDE 编辑器要实时高亮未闭合的括号计算器计算带括号的表达式时要先处理内层括号JSON/XML 解析器要处理嵌套结构。这些工具底层都在做本质相同的事维护一个“最近未闭合”的待处理列表。而这个“最近”两个字直接指向了栈这个数据结构——后进先出正好用来记录谁是当前最内层的未闭合左括号。我教学员的时候常打一个比方栈就像一摞盘子你洗好一个放上去一个用的时候只能从最上面拿。括号的配对规则也是这样字符串从左往右扫遇到左括号就往“盘子堆”上压一个遇到右括号时能跟它配对的只有当前堆顶的那一个。盘子堆顶永远代表“最新出现的那个还没配对的左括号”这是栈后进先出特性和嵌套结构之间的天然对应也是这道题非栈不可的根本原因。2. 算法核心思路与边界条件拆解2.1 三步主流程整个算法就三步我建议任何人在动手写代码之前先把这个流程在心里过一遍能避免一半以上的失误。从左到右遍历字符串中的每一个字符遇到左括号(、[、{时无条件压入栈遇到右括号)]})时先看一眼栈是否为空为空说明这个右括号没有对应的左括号直接判定非法不为空则取栈顶元素检查两个括号类型是否匹配匹配就弹栈不匹配直接判定非法遍历完整个字符串之后还要再检查一步栈是否为空。如果栈里还残留着左括号说明有左括号一直没有被闭合同样非法。这第三步太容易漏了字符串为((()的时候每一步宽度检查都是正常的没有任何右括号触发失败分支但遍历结束后栈里有三个(这当然是非法输入。2.2 四类边界条件的判定策略我梳理了这道题最常见的四种边界场景面试里考的就是你有没有提前想到它们场景示例判定结果判定时机空字符串合法遍历结束栈为空首字符是右括号)(,]非法第一次遇到右括号时栈为空类型不匹配(],[)非法栈顶元素与右括号类型不符左括号多余(((),{}][非法遍历结束后栈非空空字符串是一个容易被忽略的测试输入很多初学者看到空串就懵了。其实空串意味着没有括号需要配对天然合法算法跑完栈为空正确返回true就行不需要特判。关键在于类型不匹配和空栈弹栈这两条是代码实现里最容易出逻辑漏洞的地方。2.3 匹配关系怎么组织更优雅左右括号的对应关系实现上有两种常见写法一种是写一个isMatch(left, right)函数里面用 if-else 或者 switch 判断三组配对另一种是建立一个右括号到左括号的映射表比如{): (, ]: [, }: {}遇到右括号直接查表比对栈顶。后者在代码整洁度和可读性上明显胜出我推荐优先使用映射表因为 if-else 链一旦括号类型增多代码会迅速变得难以维护。如果有天产品经理要求扩展成 尖括号或者 HTML 标签映射表只需要多加一个键值对而 if-else 得再改一堆分支。3. 代码实现与细节解读3.1 C 语言版本手写数组栈C 语言没有现成的栈容器需要自己实现这也正好把栈的原理彻底暴露出来。我用动态数组实现了一个简单栈容量不足时自动翻倍扩容这是最接近工程实践的做法。#include stdio.h #include stdlib.h #include string.h #include stdbool.h typedef struct { char *data; int top; int capacity; } Stack; void initStack(Stack *s, int cap) { s-data (char *)malloc(sizeof(char) * cap); s-top -1; s-capacity cap; } bool isEmpty(Stack *s) { return s-top -1; } void push(Stack *s, char c) { if (s-top 1 s-capacity) { s-capacity * 2; s-data (char *)realloc(s-data, sizeof(char) * s-capacity); } s-data[s-top] c; } char pop(Stack *s) { if (isEmpty(s)) { return \0; } return s-data[s-top--]; } char peek(Stack *s) { if (isEmpty(s)) { return \0; } return s-data[s-top]; } bool isLeft(char c) { return c ( || c [ || c {; } bool isMatch(char left, char right) { return (left ( right )) || (left [ right ]) || (left { right }); } bool isValid(const char *s) { Stack st; initStack(st, 16); int n strlen(s); for (int i 0; i n; i) { char c s[i]; if (isLeft(c)) { push(st, c); } else { if (isEmpty(st)) { free(st.data); return false; } char topChar peek(st); if (!isMatch(topChar, c)) { free(st.data); return false; } pop(st); } } bool result isEmpty(st); free(st.data); return result; }这里有几个容易踩的坑我说一下栈的top初始化为 -1代表空栈。这样入栈时先自增再赋值出栈时直接访问再自减不用单独维护栈内元素数量。每次函数 return 之前必须free(st.data)否则每次调用都会泄漏内存。我在两个false分支里都释放了最后的结果分支也释放了。写 C 的人对内存管理要有条件反射只要 malloc 了就一定要能找到对应的 free 路径。pop和peek对空栈的防御性返回\0是必要的因为 C 语言里对空栈做data[--top]会产生未定义行为越界访问数组是灾难性的。虽然我在isValid里已经先判断了空栈但底层函数的防御性检查仍然值得保留防止未来有人改了调用方。3.2realloc扩容的代价与时机我在这里用了realloc实现动态扩容初始容量 16满了直接翻倍。为什么是翻倍而不是加固定大小因为翻倍扩容的均摊时间复杂度是 O(1)加固定大小扩容的均摊时间虽然也是 O(1)但常数更大而且总扩容次数更多。对于括号匹配这种一次性的短字符串处理其实初始 16 个字符通常根本不会触发扩容但工程习惯要养成以后你的栈要服务几百万次 push 时扩容策略就决定了性能上限。realloc还有一个隐患如果分配失败会返回 NULL直接赋值给s-data会让原来的指针丢失造成泄漏。严格的生产代码应该用一个临时指针接收realloc的返回值先判断是否为 NULL 再赋值。篇幅关系我没有在这个示例里写全但你自己写的时候最好补上这一层防御。3.3 Python 版本十行以内解决问题Python 的list天生就是栈append是入栈pop是出栈取最后一个元素用stack[-1]。用上映射表之后核心逻辑极其简洁。def is_valid(s: str) - bool: stack [] pairs {): (, ]: [, }: {} for ch in s: if ch in ([{: stack.append(ch) elif ch in pairs: if not stack or stack[-1] ! pairs[ch]: return False stack.pop() return not stack注意if not stack这个判断把空栈的情况和类型不匹配的情况合并处理了空栈时stack[-1]会抛 IndexError所以必须先判断。Python 的and短路求值在这里保证了安全not stack为真时根本不会执行后面的stack[-1]。这段代码的正确性依赖短路机制新手容易把两个条件写反导致空栈时崩溃。这段代码和 C 版本逻辑完全一致差别只是容器由底层替你实现了。建议初学者两个版本都写一遍能彻底明白“栈是一种抽象逻辑数组只是它的实现方式之一”这句话。同样的逻辑用链表也一样可以实现栈只是数组在连续内存访问上更高效缓存命中率更高。4. 复杂度分析与性能优化空间4.1 时间和空间复杂度这个算法的时间复杂度是 O(n)其中 n 是输入字符串长度。每个字符最多被处理两次一次入栈一次出栈。扫描本身的遍历是 n 次操作加上栈操作的均摊 O(1)总体是线性时间。空间复杂度在最坏情况下是 O(n)也就是当字符串全是一串未闭合的左括号时栈里会积累 n 个字符。有人会问能不能做到 O(1) 额外空间对纯括号匹配来说如果是只有一种括号确实可以用一个计数器记录未闭合左括号数量就行。但题目一旦规定多种括号类型且必须合法交叉嵌套计数器就无法区分[和(了。你可以试想用三个计数器分别记录三种左括号遇到([)]这个输入时三个计数器都能对上但实际上它是非法的。原因就是括号的交叉嵌套要求我们记住“顺序”而不只是“数量”。栈本质上是在用额外的空间保存顺序信息这是“多类型括号匹配”这一复杂度下不可避免的代价。4.2 少存字符空间减半很多人的第一版实现会把左右括号都压栈这是多余的。我们只需要压左括号因为右括号的作用仅是“拿来比较”它自己永远不需要被后续的什么字符匹配。遇到右括号时从栈里弹出左括号比对用完即弃。这个小小的优化能省下近一半的栈空间虽然复杂度量级不变但工程上占用越少越友好。我还见过一种写法用一个整型栈存左括号的 ASCII 码比较时直接算差值。比如(的 ASCII 是 40)是 41[是 91]是 93{是 123}是 125。三组括号的左右 ASCII 差值恰好都是 1或 2所以有人用right - left 1 || right - left 2来判断匹配。这个技巧能通过一些题目的测试但可读性太差而且依赖 ASCII 编码的巧合一旦字符集变化就是隐患。我不推荐在正式代码里用这种“聪明写法”面试官也不会因此加分。4.3 提前剪枝长度必须为偶数还有一个零成本的优化遍历前先判断strlen(s) % 2 ! 0奇数长度的字符串必然非法因为括号必须成对。这个判断消耗 O(1) 时间却能帮我们跳过大量不可能合法的输入。虽然strlen本身就是 O(n)但反正后面也要完整扫描一遍提前检查一次不会增加复杂度纯粹是白捡的剪枝。同理如果允许只包含括号字符还可以先确认字符串里没有其他非法字符不过这属于额外约束看题目要求。5. 常见问题排查与调试实录5.1 我见过的高频 Bug 排行榜这些年帮同事和学员 review 过无数版括号匹配代码我总结了几个出现频率最高的错误按坑的等级排个序坑位错误写法问题后果空栈直接弹栈char top pop(st);且没有 isEmpty 判断未定义行为轻则乱取值重则程序崩溃忘记最后检查栈空遍历结束直接return true(((被误判为合法匹配方向写反if (stack[-1] ! ch)推了右括号再比较逻辑彻底混乱全错栈顶取成了未弹出的字符用peek但记成了弹出出栈元素丢失后续匹配错乱三种括号共用一组判断用一个isMatch但不区分左右无法发现交叉嵌套的非法情况其中空栈直接弹栈是最隐蔽的。C 语言里空栈时data[--top]会访问data[-1]也就是栈数组首地址的前一个字节那个位置的数据完全不可预期。这在本地测试时可能碰巧不炸但一旦被恶意输入比如输入第一个字符就是)触发结果不可控。所以我在讲解时有个硬性要求任何涉及pop、peek的地方先问自己一句“这里有没有可能栈是空的”。5.2 定位 bug 的实用调试手段如果你实现完发现测试不过我推荐按下面的顺序排查比盲改快得多。第一打印栈的内容。在入栈和出栈的位置各加一行打印输出当前字符和栈内所有元素。括号匹配的栈内容很简单一眼就能看出问题。比如输入([)]你会看到扫到)时栈是[ ( , [ ]栈顶是[它和)不匹配立刻定位到算法判断正确是你的isMatch写错了还是查表写错了。第二用最小测试集逐个过。我调试时习惯先用四个最小用例、()、(){}[]、([)]。这四个用例分别验证空串处理、基本配对、多类型并存、交叉嵌套非法。如果这四个都过了再上长用例和随机用例。很多人的代码在()上是对的到([)]就翻车这通常是匹配逻辑没有正确区分三种括号类型造成的。第三检查你的弹栈时机。常见错误是在匹配成功后没有pop导致栈反复拿同一个元素比较。这种错误的表现是()能过但(())会错——内层的)匹配了外层的(然后外层的)又来匹配同一个(结果自然是错的。5.3 面试中的加分细节这道题在面试里已经不是“能不能做出来”的问题而是“能不能做得漂亮、聊得清楚”。我自己面试候选人时会特别关注三个点候选人有没有主动问“输入里只有括号吗还是可能有空格和其他字符”——这暴露了需求分析意识候选人有没有主动提边界条件再写代码——这暴露了测试思维候选人能否解释清楚“为什么栈是唯一合理的数据结构”——这暴露了对数据结构的理解深度所以我的建议是先和面试官确认输入范围然后口述流程和边界条件最后再动笔。写完之后主动说“我来补几个测试用例验证一下”这一句话的加分效果比代码本身更大。这道题本身不难区分度全在沟通和严谨性上。6. 从括号匹配到更广阔的应用场景6.1 表达式求值与编译原理括号匹配只是栈应用的冰山一角。编译原理里词法分析之后的语法分析阶段表达式求值用的还是栈中缀表达式转后缀表达式、后缀表达式计算、运算符优先级处理全都要依赖栈。你在计算器里输入一个(a b) * c底层就是把中缀转成后缀a b c *再用一个栈完成求值。括号在这里的作用是临时改变运算优先级而匹配规则保证的正是这个“临时改变”是合法的。很多全栈开发者写后端接口时也会遇到类似场景比如解析用户提交的查询语法、模板引擎的标签嵌套。我自己写过一个简单的模板引擎处理{{if}}...{{endif}}的嵌套时用的就是同一套思路遇到起始标签入栈遇到结束标签出栈比对最后的归属关系天然形成一棵树。理解了括号匹配你就理解了嵌套型文本解析的一半。6.2 函数调用栈与栈帧把视野拉开一点程序运行时的函数调用本质也是在用栈。每次函数调用压入一个栈帧里面装着局部变量、返回地址、参数等函数返回时弹出栈帧回到调用者的现场。这就是热搜词里“栈帧形成过程”、“调用栈回溯”的底层逻辑。调试器打印的调用栈本质就是当前时刻所有未返回函数栈帧的列表最上方永远是最新进入的函数。理解了这一点你再看递归和回溯算法会更通透递归函数的每一层调用就是在压栈返回就是在弹栈。括号匹配里的栈和递归难度里那个装状态参数的栈本质上用的是同一个抽象模型。以后你刷二叉树遍历、深度优先搜索、迷宫寻路这类回溯问题会发现全都长着类似的模样。6.3 同类变体题和扩展方向刷题讲究触类旁通括号匹配这个点能衍生出一串相关的题目最小添加使字符串有效给定字符串算至少加多少个括号能让它合法。解法依然是栈统计匹配失败的次数即可括号的得分给一个合法的括号串按特定规则算分。需要在栈里存分数而不是字符最长有效括号找字符串中最长的合法括号子串。经典解法是栈存下标HTML/XML 标签匹配把[](){}换成div和/div匹配规则从字符相等变成字符串相等本质思路完全一致这些题我建议都刷一遍因为每一道都会强化你对“栈里存什么”的思考。括号匹配存的是字符最长有效括号存的是下标括号得分存的是数值同样是栈存取的对象不同解题思路就完全打开了。实际操作中的体会是栈这个数据结构理解透了受益的不只是刷题更是日常写代码时对“上下文嵌套”这类问题的敏感度。我最后分享一个小技巧写任何嵌套结构的处理逻辑之前先画一个简单的压栈弹栈示意图哪怕在纸上画几笔都行比直接写代码快得多也稳得多。栈的代码本身没有难度难的是在动手之前想清楚栈里到底要放什么。
括号匹配与栈：经典算法原理、边界条件与多语言实现
1. 为什么括号匹配是栈最经典的入门场景括号匹配这道题几乎每个刷过题、面过试的程序员都不陌生——栈、括号匹配、左括号入栈、右括号弹栈比对满打满算十来行代码。但说句实话我在面试别人的时候真能一遍写对的人其实不多大部分人纠结的不是思路而是各种边角情况第一个字符就是右括号怎么办字符串遍历完了栈里还有东西怎么办左右括号类型对不上怎么办这些细节恰恰是这道题的精髓。先说清楚题目本身避免后面云里雾里。给一个字符串里面只包含( ) [ ] { }这六种字符判断括号的嵌套顺序是否合法。合法意味着每一个右括号都能恰好配上一个最近的、尚未匹配的左括号并且类型一致。比如([{}])合法([)]不合法(([]))合法)(不合法。直观感受一下([)]里下标 0 的(和下标 3 的)能配对但中间的[却先和)相遇了这种交叉嵌套在括号体系里是被禁止的。这个场景离我们太近了。编译器解析源代码时要检查语法括号是否配平IDE 编辑器要实时高亮未闭合的括号计算器计算带括号的表达式时要先处理内层括号JSON/XML 解析器要处理嵌套结构。这些工具底层都在做本质相同的事维护一个“最近未闭合”的待处理列表。而这个“最近”两个字直接指向了栈这个数据结构——后进先出正好用来记录谁是当前最内层的未闭合左括号。我教学员的时候常打一个比方栈就像一摞盘子你洗好一个放上去一个用的时候只能从最上面拿。括号的配对规则也是这样字符串从左往右扫遇到左括号就往“盘子堆”上压一个遇到右括号时能跟它配对的只有当前堆顶的那一个。盘子堆顶永远代表“最新出现的那个还没配对的左括号”这是栈后进先出特性和嵌套结构之间的天然对应也是这道题非栈不可的根本原因。2. 算法核心思路与边界条件拆解2.1 三步主流程整个算法就三步我建议任何人在动手写代码之前先把这个流程在心里过一遍能避免一半以上的失误。从左到右遍历字符串中的每一个字符遇到左括号(、[、{时无条件压入栈遇到右括号)]})时先看一眼栈是否为空为空说明这个右括号没有对应的左括号直接判定非法不为空则取栈顶元素检查两个括号类型是否匹配匹配就弹栈不匹配直接判定非法遍历完整个字符串之后还要再检查一步栈是否为空。如果栈里还残留着左括号说明有左括号一直没有被闭合同样非法。这第三步太容易漏了字符串为((()的时候每一步宽度检查都是正常的没有任何右括号触发失败分支但遍历结束后栈里有三个(这当然是非法输入。2.2 四类边界条件的判定策略我梳理了这道题最常见的四种边界场景面试里考的就是你有没有提前想到它们场景示例判定结果判定时机空字符串合法遍历结束栈为空首字符是右括号)(,]非法第一次遇到右括号时栈为空类型不匹配(],[)非法栈顶元素与右括号类型不符左括号多余(((),{}][非法遍历结束后栈非空空字符串是一个容易被忽略的测试输入很多初学者看到空串就懵了。其实空串意味着没有括号需要配对天然合法算法跑完栈为空正确返回true就行不需要特判。关键在于类型不匹配和空栈弹栈这两条是代码实现里最容易出逻辑漏洞的地方。2.3 匹配关系怎么组织更优雅左右括号的对应关系实现上有两种常见写法一种是写一个isMatch(left, right)函数里面用 if-else 或者 switch 判断三组配对另一种是建立一个右括号到左括号的映射表比如{): (, ]: [, }: {}遇到右括号直接查表比对栈顶。后者在代码整洁度和可读性上明显胜出我推荐优先使用映射表因为 if-else 链一旦括号类型增多代码会迅速变得难以维护。如果有天产品经理要求扩展成 尖括号或者 HTML 标签映射表只需要多加一个键值对而 if-else 得再改一堆分支。3. 代码实现与细节解读3.1 C 语言版本手写数组栈C 语言没有现成的栈容器需要自己实现这也正好把栈的原理彻底暴露出来。我用动态数组实现了一个简单栈容量不足时自动翻倍扩容这是最接近工程实践的做法。#include stdio.h #include stdlib.h #include string.h #include stdbool.h typedef struct { char *data; int top; int capacity; } Stack; void initStack(Stack *s, int cap) { s-data (char *)malloc(sizeof(char) * cap); s-top -1; s-capacity cap; } bool isEmpty(Stack *s) { return s-top -1; } void push(Stack *s, char c) { if (s-top 1 s-capacity) { s-capacity * 2; s-data (char *)realloc(s-data, sizeof(char) * s-capacity); } s-data[s-top] c; } char pop(Stack *s) { if (isEmpty(s)) { return \0; } return s-data[s-top--]; } char peek(Stack *s) { if (isEmpty(s)) { return \0; } return s-data[s-top]; } bool isLeft(char c) { return c ( || c [ || c {; } bool isMatch(char left, char right) { return (left ( right )) || (left [ right ]) || (left { right }); } bool isValid(const char *s) { Stack st; initStack(st, 16); int n strlen(s); for (int i 0; i n; i) { char c s[i]; if (isLeft(c)) { push(st, c); } else { if (isEmpty(st)) { free(st.data); return false; } char topChar peek(st); if (!isMatch(topChar, c)) { free(st.data); return false; } pop(st); } } bool result isEmpty(st); free(st.data); return result; }这里有几个容易踩的坑我说一下栈的top初始化为 -1代表空栈。这样入栈时先自增再赋值出栈时直接访问再自减不用单独维护栈内元素数量。每次函数 return 之前必须free(st.data)否则每次调用都会泄漏内存。我在两个false分支里都释放了最后的结果分支也释放了。写 C 的人对内存管理要有条件反射只要 malloc 了就一定要能找到对应的 free 路径。pop和peek对空栈的防御性返回\0是必要的因为 C 语言里对空栈做data[--top]会产生未定义行为越界访问数组是灾难性的。虽然我在isValid里已经先判断了空栈但底层函数的防御性检查仍然值得保留防止未来有人改了调用方。3.2realloc扩容的代价与时机我在这里用了realloc实现动态扩容初始容量 16满了直接翻倍。为什么是翻倍而不是加固定大小因为翻倍扩容的均摊时间复杂度是 O(1)加固定大小扩容的均摊时间虽然也是 O(1)但常数更大而且总扩容次数更多。对于括号匹配这种一次性的短字符串处理其实初始 16 个字符通常根本不会触发扩容但工程习惯要养成以后你的栈要服务几百万次 push 时扩容策略就决定了性能上限。realloc还有一个隐患如果分配失败会返回 NULL直接赋值给s-data会让原来的指针丢失造成泄漏。严格的生产代码应该用一个临时指针接收realloc的返回值先判断是否为 NULL 再赋值。篇幅关系我没有在这个示例里写全但你自己写的时候最好补上这一层防御。3.3 Python 版本十行以内解决问题Python 的list天生就是栈append是入栈pop是出栈取最后一个元素用stack[-1]。用上映射表之后核心逻辑极其简洁。def is_valid(s: str) - bool: stack [] pairs {): (, ]: [, }: {} for ch in s: if ch in ([{: stack.append(ch) elif ch in pairs: if not stack or stack[-1] ! pairs[ch]: return False stack.pop() return not stack注意if not stack这个判断把空栈的情况和类型不匹配的情况合并处理了空栈时stack[-1]会抛 IndexError所以必须先判断。Python 的and短路求值在这里保证了安全not stack为真时根本不会执行后面的stack[-1]。这段代码的正确性依赖短路机制新手容易把两个条件写反导致空栈时崩溃。这段代码和 C 版本逻辑完全一致差别只是容器由底层替你实现了。建议初学者两个版本都写一遍能彻底明白“栈是一种抽象逻辑数组只是它的实现方式之一”这句话。同样的逻辑用链表也一样可以实现栈只是数组在连续内存访问上更高效缓存命中率更高。4. 复杂度分析与性能优化空间4.1 时间和空间复杂度这个算法的时间复杂度是 O(n)其中 n 是输入字符串长度。每个字符最多被处理两次一次入栈一次出栈。扫描本身的遍历是 n 次操作加上栈操作的均摊 O(1)总体是线性时间。空间复杂度在最坏情况下是 O(n)也就是当字符串全是一串未闭合的左括号时栈里会积累 n 个字符。有人会问能不能做到 O(1) 额外空间对纯括号匹配来说如果是只有一种括号确实可以用一个计数器记录未闭合左括号数量就行。但题目一旦规定多种括号类型且必须合法交叉嵌套计数器就无法区分[和(了。你可以试想用三个计数器分别记录三种左括号遇到([)]这个输入时三个计数器都能对上但实际上它是非法的。原因就是括号的交叉嵌套要求我们记住“顺序”而不只是“数量”。栈本质上是在用额外的空间保存顺序信息这是“多类型括号匹配”这一复杂度下不可避免的代价。4.2 少存字符空间减半很多人的第一版实现会把左右括号都压栈这是多余的。我们只需要压左括号因为右括号的作用仅是“拿来比较”它自己永远不需要被后续的什么字符匹配。遇到右括号时从栈里弹出左括号比对用完即弃。这个小小的优化能省下近一半的栈空间虽然复杂度量级不变但工程上占用越少越友好。我还见过一种写法用一个整型栈存左括号的 ASCII 码比较时直接算差值。比如(的 ASCII 是 40)是 41[是 91]是 93{是 123}是 125。三组括号的左右 ASCII 差值恰好都是 1或 2所以有人用right - left 1 || right - left 2来判断匹配。这个技巧能通过一些题目的测试但可读性太差而且依赖 ASCII 编码的巧合一旦字符集变化就是隐患。我不推荐在正式代码里用这种“聪明写法”面试官也不会因此加分。4.3 提前剪枝长度必须为偶数还有一个零成本的优化遍历前先判断strlen(s) % 2 ! 0奇数长度的字符串必然非法因为括号必须成对。这个判断消耗 O(1) 时间却能帮我们跳过大量不可能合法的输入。虽然strlen本身就是 O(n)但反正后面也要完整扫描一遍提前检查一次不会增加复杂度纯粹是白捡的剪枝。同理如果允许只包含括号字符还可以先确认字符串里没有其他非法字符不过这属于额外约束看题目要求。5. 常见问题排查与调试实录5.1 我见过的高频 Bug 排行榜这些年帮同事和学员 review 过无数版括号匹配代码我总结了几个出现频率最高的错误按坑的等级排个序坑位错误写法问题后果空栈直接弹栈char top pop(st);且没有 isEmpty 判断未定义行为轻则乱取值重则程序崩溃忘记最后检查栈空遍历结束直接return true(((被误判为合法匹配方向写反if (stack[-1] ! ch)推了右括号再比较逻辑彻底混乱全错栈顶取成了未弹出的字符用peek但记成了弹出出栈元素丢失后续匹配错乱三种括号共用一组判断用一个isMatch但不区分左右无法发现交叉嵌套的非法情况其中空栈直接弹栈是最隐蔽的。C 语言里空栈时data[--top]会访问data[-1]也就是栈数组首地址的前一个字节那个位置的数据完全不可预期。这在本地测试时可能碰巧不炸但一旦被恶意输入比如输入第一个字符就是)触发结果不可控。所以我在讲解时有个硬性要求任何涉及pop、peek的地方先问自己一句“这里有没有可能栈是空的”。5.2 定位 bug 的实用调试手段如果你实现完发现测试不过我推荐按下面的顺序排查比盲改快得多。第一打印栈的内容。在入栈和出栈的位置各加一行打印输出当前字符和栈内所有元素。括号匹配的栈内容很简单一眼就能看出问题。比如输入([)]你会看到扫到)时栈是[ ( , [ ]栈顶是[它和)不匹配立刻定位到算法判断正确是你的isMatch写错了还是查表写错了。第二用最小测试集逐个过。我调试时习惯先用四个最小用例、()、(){}[]、([)]。这四个用例分别验证空串处理、基本配对、多类型并存、交叉嵌套非法。如果这四个都过了再上长用例和随机用例。很多人的代码在()上是对的到([)]就翻车这通常是匹配逻辑没有正确区分三种括号类型造成的。第三检查你的弹栈时机。常见错误是在匹配成功后没有pop导致栈反复拿同一个元素比较。这种错误的表现是()能过但(())会错——内层的)匹配了外层的(然后外层的)又来匹配同一个(结果自然是错的。5.3 面试中的加分细节这道题在面试里已经不是“能不能做出来”的问题而是“能不能做得漂亮、聊得清楚”。我自己面试候选人时会特别关注三个点候选人有没有主动问“输入里只有括号吗还是可能有空格和其他字符”——这暴露了需求分析意识候选人有没有主动提边界条件再写代码——这暴露了测试思维候选人能否解释清楚“为什么栈是唯一合理的数据结构”——这暴露了对数据结构的理解深度所以我的建议是先和面试官确认输入范围然后口述流程和边界条件最后再动笔。写完之后主动说“我来补几个测试用例验证一下”这一句话的加分效果比代码本身更大。这道题本身不难区分度全在沟通和严谨性上。6. 从括号匹配到更广阔的应用场景6.1 表达式求值与编译原理括号匹配只是栈应用的冰山一角。编译原理里词法分析之后的语法分析阶段表达式求值用的还是栈中缀表达式转后缀表达式、后缀表达式计算、运算符优先级处理全都要依赖栈。你在计算器里输入一个(a b) * c底层就是把中缀转成后缀a b c *再用一个栈完成求值。括号在这里的作用是临时改变运算优先级而匹配规则保证的正是这个“临时改变”是合法的。很多全栈开发者写后端接口时也会遇到类似场景比如解析用户提交的查询语法、模板引擎的标签嵌套。我自己写过一个简单的模板引擎处理{{if}}...{{endif}}的嵌套时用的就是同一套思路遇到起始标签入栈遇到结束标签出栈比对最后的归属关系天然形成一棵树。理解了括号匹配你就理解了嵌套型文本解析的一半。6.2 函数调用栈与栈帧把视野拉开一点程序运行时的函数调用本质也是在用栈。每次函数调用压入一个栈帧里面装着局部变量、返回地址、参数等函数返回时弹出栈帧回到调用者的现场。这就是热搜词里“栈帧形成过程”、“调用栈回溯”的底层逻辑。调试器打印的调用栈本质就是当前时刻所有未返回函数栈帧的列表最上方永远是最新进入的函数。理解了这一点你再看递归和回溯算法会更通透递归函数的每一层调用就是在压栈返回就是在弹栈。括号匹配里的栈和递归难度里那个装状态参数的栈本质上用的是同一个抽象模型。以后你刷二叉树遍历、深度优先搜索、迷宫寻路这类回溯问题会发现全都长着类似的模样。6.3 同类变体题和扩展方向刷题讲究触类旁通括号匹配这个点能衍生出一串相关的题目最小添加使字符串有效给定字符串算至少加多少个括号能让它合法。解法依然是栈统计匹配失败的次数即可括号的得分给一个合法的括号串按特定规则算分。需要在栈里存分数而不是字符最长有效括号找字符串中最长的合法括号子串。经典解法是栈存下标HTML/XML 标签匹配把[](){}换成div和/div匹配规则从字符相等变成字符串相等本质思路完全一致这些题我建议都刷一遍因为每一道都会强化你对“栈里存什么”的思考。括号匹配存的是字符最长有效括号存的是下标括号得分存的是数值同样是栈存取的对象不同解题思路就完全打开了。实际操作中的体会是栈这个数据结构理解透了受益的不只是刷题更是日常写代码时对“上下文嵌套”这类问题的敏感度。我最后分享一个小技巧写任何嵌套结构的处理逻辑之前先画一个简单的压栈弹栈示意图哪怕在纸上画几笔都行比直接写代码快得多也稳得多。栈的代码本身没有难度难的是在动手之前想清楚栈里到底要放什么。
![Linux Shell 括号用法：${}、$()、[]、[[]]、(()) 区别](http://pic.xiahunao.cn/yaotu/Linux Shell 括号用法：${}、$()、[]、[[]]、(()) 区别)
