写这篇东西的起因很简单前阵子帮学生看代码一个挺聪明的小伙子卡在了一大坨if嵌套里程序死活编译不过。他一行行盯着看眼睛都快贴屏幕上了还是找不到哪个括号配错了对。我当时就跟他说这种问题别靠肉眼硬刚把字符挨个压进一个栈里遇到左括号就入栈遇到右括号就弹出来比对跑到最后栈是空的说明括号都匹配上了——两分钟就能定位问题。他半信半疑地把这个逻辑写出来果然一下子就找到了那个多余的右括号。也就是从那次之后我越来越觉得用“括号匹配”当引子去讲链式栈的用法简直是C语言教学里最聪明的设计之一问题本身人人都能看懂背后牵出的数据结构却一点都不浅。这篇文章我会从为什么选链式栈而不是顺序栈讲起把栈的初始化、入栈、出栈、遍历显示这些基本操作一个个掰开揉碎再给出一套完整的括号匹配算法实现最后聊聊这段代码放到真实场景里能做点什么。无论是刚学完指针和结构体、想找个像样的综合练习的初学者还是想复习数据结构基础、顺手补一下C语言内存管理的老手这篇应该都能对得上你的胃口。1. 为什么括号匹配这道题天生就该用链式栈来做先别急着看代码把逻辑顺一遍比写代码更重要。括号匹配的规则其实很简单每一个右括号都必须和自己左边“最近的那个尚未配对的左括号”一一对应。这个“最近”两个字就是栈之所以能派上用场的根本原因。1.1 “后进先出”和括号匹配是同一个模型栈的特性四个字就讲完了后进先出。往栈里放东西永远只能放在最顶上取东西也只能从最顶上拿。你用浏览器的时候点“后退”回到的是上一次访问的页面而不是最开始那个页面这就是栈在起作用。括号匹配正好也是一模一样的逻辑。遇到(、[、{就压进栈里等遇到)、]、}时我们需要找的并不是整个表达式里“第一次出现的那个左括号”而是“最近一个还没被配对的左括号”——也就是栈顶那个。如果栈顶弹出来的左括号和当前的右括号是同一类型说明这一对是合法的如果不是说明括号类型交叉嵌套了比如[(这种配对了但类型不对或者(]直接就是错的。这个“最近匹配”的直觉和栈的“后进先出”完全是一回事。你用数组、链表、或者甚至手写一个计数器去模拟最后都会发现还是得退化成“栈”这个模型。所以括号匹配教科书般适合用来讲栈规则清晰边界情况多而且出错的时候你能亲眼看到数据结构到底是怎么运转的。1.2 链式栈和顺序栈的选型博弈那具体实现栈的时候有两个路子用数组做顺序栈或者用链表做链式栈。初学者可能觉得既然数组更好写那直接上顺序栈不就行了这里面的门道值得掰扯一下。顺序栈的思路是开一个固定大小的数组再用一个top变量记录栈顶位置。入栈就像把数组下标往后挪一格再存值出栈就是top减一。它的优点是访问速度快、不需要频繁申请内存缺点是容量在编译期就定死了。假设你预估失误括号嵌套个几百层数组开小了会溢出开大了呢又浪费。链式栈的思路则完全反过来每个元素是一个结构体节点节点里存数据还有一个指针指向下一个节点。入栈就创建一个新节点接到栈顶出栈就把栈顶节点摘下来释放掉。它没有容量上限内存用多少算多少缺点是每一次入栈都要malloc性能上会有些损耗而且用完之后必须记得free不然就内存泄漏了。那括号匹配这道题到底选哪个说实话两种都能做。但我个人更倾向于在教学阶段用链式栈理由有三条括号嵌套深度在理论上不受限。虽然实际代码不会嵌套一万层但链式栈在逻辑上更接近“无限容量”的抽象你不用心里一直惦记着那个数组边界。链式栈涉及结构体、指针、动态内存分配、链表操作这一套组合下来本身就是综合练习的好素材。代码量比顺序栈大一些但练到的东西也多。面试和笔试里手写链式栈的频率比顺序栈高得多。LeetCode上很多栈相关的题目底层实现思路都是链式的。当然如果你只是想在竞赛里快速交卷顺序栈的代码量确实更少。但咱们这篇的目的是把东西讲透所以走链式栈的路子。2. 链式栈的结构体定义与初始化——先把地基夯实动手写代码之前先把数据模型想清楚。链式栈本质上是一个“只在头部增删”的链表所以结构体定义和链表的节点定义非常像。2.1 节点结构体的设计思路链式栈的每个节点需要两块信息一个是数据域存的是栈里的实际元素一个是指针域指向下一个节点。括号匹配场景里我们压入栈的是一个字符所以数据域用char类型就够了。typedef struct StackNode { char data; // 数据域存储括号字符 struct StackNode *next; // 指针域指向栈的下一个节点 } StackNode;有几点值得说。next指针之所以写成struct StackNode *next而不是StackNode *next是因为在类型别名typedef还没执行完之前StackNode这个名字还不存在编译器不认识它。你说这是玄学也好、细节也罢总之面试的时候冷不丁被问到一次答不上来还是很尴尬的。另外你可能会想用char *直接存字符串然后压入一个字符串但那是另一个话题。括号匹配一次只处理一个字符用char简单干净调试的时候一眼就能看出栈顶是什么。2.2 栈顶指针与链表的头节点等价栈需要有一个“栈顶指针”来指向最顶上的节点。在这个实现里栈顶指针其实就是链表的头指针。链表的头指针指向第一个节点栈顶指针也指向第一个节点——两者是一样的东西。初始化要做的事就是把栈置空。很多人第一次写这里容易犯迷糊到底是把指针置NULL就够了还是得malloc一个头节点StackNode *initStack() { return NULL; // 空栈就是栈顶指针为NULL }没错就这样一行代码。链式栈的空栈状态就是栈顶指针为空。不需要弄什么“哨兵头节点”那在部分链表场景里确实有用但在链式栈里纯属画蛇添足。你要是额外malloc了一个头节点后面每次判断栈是否为空都得把头节点的情况单独拎出来考虑代码复杂度会直线上升。这里也顺手提一句为什么top指针要用指针的指针。现实中初始化函数通常写成这样void initStack(StackNode **top) { *top NULL; }如果只传StackNode *top那么在函数内部修改top的值本质上只修改了形参的拷贝外面的指针变量不会跟着变。想要在函数内部改动外部的指针就必须多包一层指针。很多初学者在这个地方翻过车症状就是栈永远“初始化失败”怎么压都压不进去。如果不想用指针的指针也可以让初始化函数返回StackNode *就像前面那段代码调用时直接StackNode *top initStack();。两条路都对教学时我更偏好后者写起来顺手也不容易因为忘了传地址而踩坑。3. 入栈和出栈的完整实现——链式栈的核心操作拆解搭好了结构体下面就到了整篇文章的重头戏入栈push和出栈pop。这两个操作是栈的灵魂括号匹配的全部逻辑都建立在它们之上。3.1 入栈操作新节点永远插在最前面入栈的本质就三步创建新节点、把数据放进去、把新节点连到栈顶。因为栈只允许在顶部操作所以新节点始终是链表的新头节点。StackNode *push(StackNode *top, char value) { // 1. 为新节点分配内存 StackNode *newNode (StackNode *)malloc(sizeof(StackNode)); if (newNode NULL) { printf(内存分配失败!\n); return top; // 内存都没了栈保持不变 } // 2. 写入数据 newNode-data value; // 3. 让新节点指向原来的栈顶然后新节点成为栈顶 newNode-next top; top newNode; return top; }这个操作的时间复杂度是O(1)因为无论栈里已经塞了多少元素都只需要改两个指针不需要遍历。这也是栈比很多其他数据结构高效的原因之一它锁死了操作位置所以代价恒定。这里有三个细节必须提。第一malloc之后要检查返回值是否为NULL。很多教学代码懒得写这一步但你实际跑程序的时候尤其在内存紧缺的环境下malloc确实可能失败。一旦返回NULL还继续往下赋值就是解引用空指针程序直接崩溃。C语言没有异常机制所有错误都得自己兜着所以这个检查不能省。第二先给newNode-next赋值再把top更新为newNode这个顺序不能乱。如果你先执行了top newNode那么原来的栈顶节点指针就找不到了链表从中间断了后面的节点全部丢失。真出这种bug的时候特别坑程序能跑但栈里的元素莫名其妙就丢了排查起来会绕很大一个弯。第三返回值不能丢。我写的是返回新的栈顶指针。如果你在调用时写了push(top, ();忘记接收返回值那top还是原来的旧值链表照样断掉。所以要么像上面这样用返回值接住要么就用指针的指针void push(StackNode **top, char value)在函数内部直接修改*top。两条路选一条千万别混。3.2 出栈操作栈顶弹出指针后移最后释放内存出栈同样三步取栈顶元素的值、把栈顶指针往后挪、释放被摘下的节点。int pop(StackNode **top, char *result) { if (*top NULL) { return 0; // 栈为空出栈失败 } StackNode *temp *top; // 临时保存栈顶节点 *result temp-data; // 把栈顶数据取出 *top temp-next; // 栈顶指针下移 free(temp); // 释放原栈顶节点 return 1; // 出栈成功 }我这次特意用了指针的指针写法因为出栈操作不仅要取出数据还要修改栈顶指针本身。如果你用单指针StackNode *top在函数内部给top赋新值也影响不到外部变量出栈出来的结果没法同步。还有free这一步千万不要省。链式栈自己管内存申了多少就要还多少。你在一个循环里疯狂push一万个节点从不free程序表面安然无恙但内存占用一路飙升最后系统把进程杀掉你都不知道为什么。另外注意一个细节我让出栈函数返回int而不是char。原因在于空栈的时候根本没有元素可取这时候需要一个“出栈失败”的信号。如果你让函数返回char那失败时怎么办返回\0万一栈里存的恰好就是\0呢没法区分。用int做返回值区分成功和失败再用指针参数把数据带出来是C语言里非常经典的做法。如果你实在不习惯指针的指针也可以换一种写法用单指针加返回值StackNode *pop(StackNode *top, char *result) { if (top NULL) { return NULL; } StackNode *temp top; *result temp-data; top top-next; free(temp); return top; }逻辑完全一样只是改成了返回值更新法。两种风格我都见过ACM选手偏爱后者工程码农习惯前者看你自己的手感。3.3 链栈的遍历显示验证栈内状态最直观的方法调试的时候光靠眼睛跟踪指针变量很折磨人最直接的办法就是写一个遍历函数把栈里的元素从顶到底全部打印出来。因为栈只能从栈顶访问所以遍历顺序天然就是“后进先出”。void displayStack(StackNode *top) { if (top NULL) { printf(栈为空\n); return; } printf(栈顶 - ); StackNode *current top; while (current ! NULL) { printf(%c , current-data); current current-next; } printf(- 栈底\n); }这里用一个current指针从栈顶一路往后走。千万不要直接动传入的top否则你的栈顶指针都不知道飞去哪了。每次入栈出栈之后调用一次displayStack就能非常直观地看到“栈里现在还剩什么”。我在给学生演示括号匹配算法的时候每处理一个字符就打印一次栈的状态那种层层压入又层层弹出的感觉看代码是一回事看打印输出又是另一回事后者理解的效率要高得多。3.4 摧毁整个栈避免内存泄漏的收尾操作前面说了链式栈的内存全指望自己回收。栈用完了得写一个“清空”函数把链表上的每一个节点都释放掉。这个函数的思想是不断弹出栈顶直到栈空。void clearStack(StackNode **top) { while (*top ! NULL) { StackNode *temp *top; *top (*top)-next; free(temp); } printf(栈已清空\n); }有人可能觉得程序一结束操作系统会自动回收内存写不写这个函数无所谓。这话在只跑一次的判断题程序里勉强说得通但一旦你的栈是在一个大型程序的某个模块里用到的模块结束而进程还在那内存就泄漏了。生产环境下的内存泄漏就是这么一点一点攒出来的。养成良好的收尾习惯从写练习代码的时候就开始成本最低。4. 括号匹配算法从概念到可运行的完整代码前面所有铺垫都是为了这一刻把栈的操作组装成一个能真正检测括号匹配的程序。4.1 算法的判断流程与边界条件括号匹配算法的完整流程大概是这样走初始化一个空栈。从字符串的第一个字符扫到最后一个字符。如果是左括号(、[、{入栈。如果是右括号)、]、}先看栈是否为空。如果为空说明这个右括号前面根本没有可配对的左括号直接判定不匹配。如果栈不为空弹出栈顶左括号判断它和当前右括号是否是同一类型。整个字符串扫描结束后如果栈里还有剩余左括号说明有些括号从未被关闭还是不匹配栈为空才说明所有括号都正确配对了。边界情况要特别注意空字符串应该算匹配成功因为不存在任何未配对的括号只有右括号没有左括号的情况要在第4步拦下来只有左括号没有右括号的情况要靠最后栈清空与否来判断。4.2 完整代码实现与逐步解析下面这段代码是一个完整的可运行程序你直接复制进编译器就能跑#include stdio.h #include stdlib.h #include string.h typedef struct StackNode { char data; struct StackNode *next; } StackNode; // 初始化空栈 StackNode *initStack(void) { return NULL; } // 入栈 StackNode *push(StackNode *top, char value) { StackNode *newNode (StackNode *)malloc(sizeof(StackNode)); if (newNode NULL) { printf(内存分配失败!\n); return top; } newNode-data value; newNode-next top; return newNode; } // 出栈 StackNode *pop(StackNode *top, char *result) { if (top NULL) { return NULL; } StackNode *temp top; *result temp-data; top top-next; free(temp); return top; } // 判断左右括号是否匹配 int isMatch(char left, char right) { if (left ( right )) return 1; if (left [ right ]) return 1; if (left { right }) return 1; return 0; } // 括号匹配核心算法 int checkBrackets(const char *str) { StackNode *top initStack(); int length (int)strlen(str); for (int i 0; i length; i) { char ch str[i]; if (ch ( || ch [ || ch {) { top push(top, ch); } else if (ch ) || ch ] || ch }) { // 遇到右括号但栈是空的说明无左括号可配 if (top NULL) { printf(第 %d 个字符 %c 匹配失败多余的右括号\n, i 1, ch); clearStack(top); return 0; } char topChar; top pop(top, topChar); if (!isMatch(topChar, ch)) { printf(第 %d 个字符 %c 匹配失败与栈顶 %c 类型不匹配\n, i 1, ch, topChar); clearStack(top); return 0; } } // 其他字符比如字母数字、空格直接忽略不参与匹配 } if (top ! NULL) { printf(匹配失败存在未配对的左括号\n); displayStack(top); clearStack(top); return 0; } printf(括号全部匹配成功!\n); clearStack(top); return 1; } void displayStack(StackNode *top) { if (top NULL) { printf(栈为空\n); return; } printf(栈顶 - ); StackNode *current top; while (current ! NULL) { printf(%c , current-data); current current-next; } printf(- 栈底\n); } void clearStack(StackNode **top) { while (*top ! NULL) { StackNode *temp *top; *top (*top)-next; free(temp); } } int main(void) { const char *test1 ((ab)*[c-d]); const char *test2 ([)]; const char *test3 (ab)*(c-d; const char *test4 (ab)); const char *test5 ; printf(测试1%s\n, test1); checkBrackets(test1); printf(\n测试2%s\n, test2); checkBrackets(test2); printf(\n测试3%s\n, test3); checkBrackets(test3); printf(\n测试4%s\n, test4); checkBrackets(test4); printf(\n测试5空字符串\n); checkBrackets(test5); return 0; }特别提醒一下我在clearStack用的是StackNode **top而上面代码里调用时传top是匹配的但push返回新栈顶pop接收旧栈顶并返回新栈顶两种风格混在一起用初学者可能看着看着就迷糊了。这确实是一个教学上的取舍我想让你见识两种常见写法但代价就是代码风格不够统一。你实际写工程代码时建议统一成一种风格要么全部用返回值传新栈顶要么全部用二级指针混着用容易出隐蔽bug。整个程序的运行结果应该是((ab)*[c-d])匹配成功。([)]第3个字符)和栈顶[类型不匹配失败。(ab)*(c-d最后栈里剩了(失败。(ab))第6个字符)是多余的失败。匹配成功。这五个测试用例分别对应了五种不同的情况正常嵌套、交叉不匹配、缺右括号、缺左括号、空输入。我自己调试的时候也是拿这几组数据反复跑直到全部通过才敢说程序逻辑没问题。4.3 为什么有效括号的判断其实是在做“消除”而不是“计数”这里再把思维拔高一点。很多人第一反应是用三个计数器分别记录三种括号的数量每当看到左括号就加一看到右括号就减一最后看三个计数器是不是都归零。这个思路对()这种单一类型的括号管用但对([)]这种交叉嵌套就彻底失效了。因为(跟]虽然数量上配平了但它们在结构上压根不是一对。栈的思路本质上是一个“即时消除”的过程每看到一个右括号就把它和最近的左括号配对配对成功就把这对消除掉栈里只保留“还没配对的左括号”。这个“消除”操作完成之后剩下的问题只剩“栈是否为空”。它比计数更贴近括号语法的真实语义——括号不仅要数量对位置和顺序也必须对。这也是为什么像IDE、编译器的语法检查器全都用栈来校验括号配对的根本原因。它不是“一种办法”而已它是这个问题在计算模型上的最优解之一。5. 链式栈的常见坑点与调试经验——这些教训是用一次次的段错误换来的代码写出来了能跑通不算完。要真正理解链式栈必须把那些最容易出事的坑提前摸一遍。下面几个问题几乎每个学到这里的人都会踩上至少一个。5.1 空栈出栈最经典的段错误来源前面写的pop里先判断了top NULL但很多人一开始是不写的。直接上来就StackNode *temp top; *result temp-data;。如果此时栈是空的top是NULL对NULL取-data在你面前的就是一个字面意义的“段错误”程序当场崩溃。这种错误最让人头疼的地方在于它不一定是稳定复现的。有时候字符串里最后一个字符恰好是右括号栈刚好被弹空了下一个字符又来一个右括号崩溃就发生了。你调试半天可能试了好几个用例都没问题偏偏某一条输入就会炸。排查的思路是每次出栈前先问“栈是否为空”这永远不该被省略。括号匹配算法里右括号来临时栈为空这个分支尤其重要必须在入逻辑之前就单独处理。很多 LeetCode 上的题解为什么看起来很短不是省略了这个判断而是判断逻辑被写进了循环条件里比如先判断top NULL就直接返回。别学着学着把这一步给省了。5.2 忘记接住返回值或忘记free我之前带的学生里十个人至少有四个人犯过这个错push(top, (); // 没有接收返回值top的值压根没变入栈白入了。链表类的操作基本都要么传二级指针要么接住返回值二者必有其一。千万别觉得push内部改了top外部的top就能跟着变——C语言没有引用传参只传值。另一类错误是free放错了位置。入栈函数里malloc的新节点生命周期要延续到出栈时才能free。有些初学者在入栈函数结尾就把节点释放了结果发现压进去的字符全是乱码。那是因为节点内存虽然已经还给系统了但指针还指着那块已经失效的区域访问它属于未定义行为什么奇怪的结果都可能冒出来。这类问题用调试器查很熬人最好从开头就养成“谁分配谁释放、什么时候分配什么时候释放”的习惯。5.3 用char *直接扫描时别忘掉字符串的长度和边界checkBrackets函数用了strlen(str)获取长度再通过下标访问每一个字符。这里有个隐藏前提传入的字符串必须是以\0结尾的合法C字符串。如果你手动构造的字符数组忘了末尾的\0strlen会一路读到野内存去返回一个巨大的数字循环条件瞬间失控程序直接乱成一锅粥。如果不想依赖strlen也可以改成指针扫描直接while (*str ! \0)。两种写法本质一样但我更推荐下标法调试时能看到i的值出错的时候好定位到底是第几个字符出的问题。5.4 嵌套深度的真实测试与栈溢出风险链式栈理论上没有容量上限但别高兴太早。每入栈一个节点就调用一次malloc。如果你拿一个嵌套了上百万层括号的字符串去测每层都要malloc内存消耗巨大不说递归深入太多还可能把栈空间耗尽。这属于极端场景真实的代码不会嵌套那么深但那种“我们不怕大数据”的幻觉不能有。实测下来嵌套几千层括号在普通PC上没有任何压力代码跑得非常顺滑。这个量级已经远超绝大多数真实代码的嵌套深度了。真要说链式栈比顺序栈有优势的场景恰恰就是这种“深度不可预知”但实际又不会太夸张的情况——数组开大了浪费开小了又不够链表这边完全不用纠结。5.5 用调试输出验证每一步状态实战经验告诉我写完链式栈之后先别急着跑括号匹配而是先单独测试push、pop、displayStack三个基本操作。比如StackNode *top initStack(); top push(top, a); top push(top, b); top push(top, c); displayStack(top); // 预期输出栈顶 - c b a - 栈底 char ch; top pop(top, ch); printf(弹出:%c\n, ch); // 预期输出弹出:c displayStack(top); // 预期输出栈顶 - b a - 栈底先确保每个零件没有问题再组装成完整系统。这比直接写一个500行的大程序然后从头调错要清爽一百倍。C语言不像那些带垃圾回收的高级语言每一步内存操作都得自己心里有数。你能看到打印里的c b a就说明指针关系是对的后面出了任何问题都不用再怀疑链表的连接了。6. 括号匹配链式栈之外这个模型还能走向哪里写完了括号匹配千万别以为链式栈的学习就到此为止了。数据结构这种东西最大的价值不是背下来某种操作步骤而是明白“什么样的问题底子是什么模型”。括号匹配只是栈模型最经典但也最浅的一个应用。6.1 表达式求值从语法到运算的直接延伸你自己写一个计算器输入一串中缀表达式1 2 * 3计算机怎么知道要先算乘再算加普通的从左往右扫描根本做不到。经典的做法是把中缀表达式转成后缀表达式再用栈来求值。遇到数字入栈遇到运算符就弹出两个操作数做运算再把结果压回去。整个过程你会惊讶地发现跟括号匹配里“遇到右括号弹出左括号”的模式几乎一模一样。可以说如果你今天把链式栈的push和pop练熟了明天学表达式求值就是水到渠成的事。6.2 函数调用的底层到底是怎么运作的每一门高级语言都有函数调用栈。你调用函数AA里边再调用函数BB执行完返回A接着往下跑。这个“嵌套调用再逐层返回”的先后顺序和栈的后进先出完全吻合。每调用一个函数系统就往调用栈里压入一个栈帧存着局部变量、返回地址这些信息函数一返回这个栈帧就被弹出。这也是为什么递归不能无限深入——栈的容量是有限制的递归太深就会栈溢出。理解了链式栈你再看递归调用栈这几个字脑子里就不再是一片模糊了。6.3 浏览器历史记录与撤销操作的同一个模型你按一下浏览器“后退”按钮回到的是上一个页面不是最初打开的页面这就是一个标准栈行为。编辑器里的CtrlZ也是每撤销一步就弹出最近的那个操作。这些日常场景都是栈模型只是它们跑在你看不见的地方。学数据结构最有意思的时刻就是你突然意识到原来身边这么多看起来八竿子打不着的东西底层都在干同一件事。6.4 再往后走从中缀转后缀到树与图栈学会了往后还有队列、二叉树、图。中缀转后缀练的是“运算符优先级”二叉树遍历里有一种非递归写法就用栈模拟递归过程图的深度优先搜索同样可以基于栈。你会发现栈这个“简单的容器”简直是无处不在的骨架。C语言本身没有内建栈容器但只要你会写链表你就拥有了一切的起点。把链式栈的代码吃透之后每学一个新结构回头看看这份练习代码都会多一分亲切感。数据结构的学习曲线前期确实陡峭但你亲手写过的每一行malloc和free都会在后面的路上不断给你回报。
C语言链式栈实现括号匹配：原理详解与完整代码
写这篇东西的起因很简单前阵子帮学生看代码一个挺聪明的小伙子卡在了一大坨if嵌套里程序死活编译不过。他一行行盯着看眼睛都快贴屏幕上了还是找不到哪个括号配错了对。我当时就跟他说这种问题别靠肉眼硬刚把字符挨个压进一个栈里遇到左括号就入栈遇到右括号就弹出来比对跑到最后栈是空的说明括号都匹配上了——两分钟就能定位问题。他半信半疑地把这个逻辑写出来果然一下子就找到了那个多余的右括号。也就是从那次之后我越来越觉得用“括号匹配”当引子去讲链式栈的用法简直是C语言教学里最聪明的设计之一问题本身人人都能看懂背后牵出的数据结构却一点都不浅。这篇文章我会从为什么选链式栈而不是顺序栈讲起把栈的初始化、入栈、出栈、遍历显示这些基本操作一个个掰开揉碎再给出一套完整的括号匹配算法实现最后聊聊这段代码放到真实场景里能做点什么。无论是刚学完指针和结构体、想找个像样的综合练习的初学者还是想复习数据结构基础、顺手补一下C语言内存管理的老手这篇应该都能对得上你的胃口。1. 为什么括号匹配这道题天生就该用链式栈来做先别急着看代码把逻辑顺一遍比写代码更重要。括号匹配的规则其实很简单每一个右括号都必须和自己左边“最近的那个尚未配对的左括号”一一对应。这个“最近”两个字就是栈之所以能派上用场的根本原因。1.1 “后进先出”和括号匹配是同一个模型栈的特性四个字就讲完了后进先出。往栈里放东西永远只能放在最顶上取东西也只能从最顶上拿。你用浏览器的时候点“后退”回到的是上一次访问的页面而不是最开始那个页面这就是栈在起作用。括号匹配正好也是一模一样的逻辑。遇到(、[、{就压进栈里等遇到)、]、}时我们需要找的并不是整个表达式里“第一次出现的那个左括号”而是“最近一个还没被配对的左括号”——也就是栈顶那个。如果栈顶弹出来的左括号和当前的右括号是同一类型说明这一对是合法的如果不是说明括号类型交叉嵌套了比如[(这种配对了但类型不对或者(]直接就是错的。这个“最近匹配”的直觉和栈的“后进先出”完全是一回事。你用数组、链表、或者甚至手写一个计数器去模拟最后都会发现还是得退化成“栈”这个模型。所以括号匹配教科书般适合用来讲栈规则清晰边界情况多而且出错的时候你能亲眼看到数据结构到底是怎么运转的。1.2 链式栈和顺序栈的选型博弈那具体实现栈的时候有两个路子用数组做顺序栈或者用链表做链式栈。初学者可能觉得既然数组更好写那直接上顺序栈不就行了这里面的门道值得掰扯一下。顺序栈的思路是开一个固定大小的数组再用一个top变量记录栈顶位置。入栈就像把数组下标往后挪一格再存值出栈就是top减一。它的优点是访问速度快、不需要频繁申请内存缺点是容量在编译期就定死了。假设你预估失误括号嵌套个几百层数组开小了会溢出开大了呢又浪费。链式栈的思路则完全反过来每个元素是一个结构体节点节点里存数据还有一个指针指向下一个节点。入栈就创建一个新节点接到栈顶出栈就把栈顶节点摘下来释放掉。它没有容量上限内存用多少算多少缺点是每一次入栈都要malloc性能上会有些损耗而且用完之后必须记得free不然就内存泄漏了。那括号匹配这道题到底选哪个说实话两种都能做。但我个人更倾向于在教学阶段用链式栈理由有三条括号嵌套深度在理论上不受限。虽然实际代码不会嵌套一万层但链式栈在逻辑上更接近“无限容量”的抽象你不用心里一直惦记着那个数组边界。链式栈涉及结构体、指针、动态内存分配、链表操作这一套组合下来本身就是综合练习的好素材。代码量比顺序栈大一些但练到的东西也多。面试和笔试里手写链式栈的频率比顺序栈高得多。LeetCode上很多栈相关的题目底层实现思路都是链式的。当然如果你只是想在竞赛里快速交卷顺序栈的代码量确实更少。但咱们这篇的目的是把东西讲透所以走链式栈的路子。2. 链式栈的结构体定义与初始化——先把地基夯实动手写代码之前先把数据模型想清楚。链式栈本质上是一个“只在头部增删”的链表所以结构体定义和链表的节点定义非常像。2.1 节点结构体的设计思路链式栈的每个节点需要两块信息一个是数据域存的是栈里的实际元素一个是指针域指向下一个节点。括号匹配场景里我们压入栈的是一个字符所以数据域用char类型就够了。typedef struct StackNode { char data; // 数据域存储括号字符 struct StackNode *next; // 指针域指向栈的下一个节点 } StackNode;有几点值得说。next指针之所以写成struct StackNode *next而不是StackNode *next是因为在类型别名typedef还没执行完之前StackNode这个名字还不存在编译器不认识它。你说这是玄学也好、细节也罢总之面试的时候冷不丁被问到一次答不上来还是很尴尬的。另外你可能会想用char *直接存字符串然后压入一个字符串但那是另一个话题。括号匹配一次只处理一个字符用char简单干净调试的时候一眼就能看出栈顶是什么。2.2 栈顶指针与链表的头节点等价栈需要有一个“栈顶指针”来指向最顶上的节点。在这个实现里栈顶指针其实就是链表的头指针。链表的头指针指向第一个节点栈顶指针也指向第一个节点——两者是一样的东西。初始化要做的事就是把栈置空。很多人第一次写这里容易犯迷糊到底是把指针置NULL就够了还是得malloc一个头节点StackNode *initStack() { return NULL; // 空栈就是栈顶指针为NULL }没错就这样一行代码。链式栈的空栈状态就是栈顶指针为空。不需要弄什么“哨兵头节点”那在部分链表场景里确实有用但在链式栈里纯属画蛇添足。你要是额外malloc了一个头节点后面每次判断栈是否为空都得把头节点的情况单独拎出来考虑代码复杂度会直线上升。这里也顺手提一句为什么top指针要用指针的指针。现实中初始化函数通常写成这样void initStack(StackNode **top) { *top NULL; }如果只传StackNode *top那么在函数内部修改top的值本质上只修改了形参的拷贝外面的指针变量不会跟着变。想要在函数内部改动外部的指针就必须多包一层指针。很多初学者在这个地方翻过车症状就是栈永远“初始化失败”怎么压都压不进去。如果不想用指针的指针也可以让初始化函数返回StackNode *就像前面那段代码调用时直接StackNode *top initStack();。两条路都对教学时我更偏好后者写起来顺手也不容易因为忘了传地址而踩坑。3. 入栈和出栈的完整实现——链式栈的核心操作拆解搭好了结构体下面就到了整篇文章的重头戏入栈push和出栈pop。这两个操作是栈的灵魂括号匹配的全部逻辑都建立在它们之上。3.1 入栈操作新节点永远插在最前面入栈的本质就三步创建新节点、把数据放进去、把新节点连到栈顶。因为栈只允许在顶部操作所以新节点始终是链表的新头节点。StackNode *push(StackNode *top, char value) { // 1. 为新节点分配内存 StackNode *newNode (StackNode *)malloc(sizeof(StackNode)); if (newNode NULL) { printf(内存分配失败!\n); return top; // 内存都没了栈保持不变 } // 2. 写入数据 newNode-data value; // 3. 让新节点指向原来的栈顶然后新节点成为栈顶 newNode-next top; top newNode; return top; }这个操作的时间复杂度是O(1)因为无论栈里已经塞了多少元素都只需要改两个指针不需要遍历。这也是栈比很多其他数据结构高效的原因之一它锁死了操作位置所以代价恒定。这里有三个细节必须提。第一malloc之后要检查返回值是否为NULL。很多教学代码懒得写这一步但你实际跑程序的时候尤其在内存紧缺的环境下malloc确实可能失败。一旦返回NULL还继续往下赋值就是解引用空指针程序直接崩溃。C语言没有异常机制所有错误都得自己兜着所以这个检查不能省。第二先给newNode-next赋值再把top更新为newNode这个顺序不能乱。如果你先执行了top newNode那么原来的栈顶节点指针就找不到了链表从中间断了后面的节点全部丢失。真出这种bug的时候特别坑程序能跑但栈里的元素莫名其妙就丢了排查起来会绕很大一个弯。第三返回值不能丢。我写的是返回新的栈顶指针。如果你在调用时写了push(top, ();忘记接收返回值那top还是原来的旧值链表照样断掉。所以要么像上面这样用返回值接住要么就用指针的指针void push(StackNode **top, char value)在函数内部直接修改*top。两条路选一条千万别混。3.2 出栈操作栈顶弹出指针后移最后释放内存出栈同样三步取栈顶元素的值、把栈顶指针往后挪、释放被摘下的节点。int pop(StackNode **top, char *result) { if (*top NULL) { return 0; // 栈为空出栈失败 } StackNode *temp *top; // 临时保存栈顶节点 *result temp-data; // 把栈顶数据取出 *top temp-next; // 栈顶指针下移 free(temp); // 释放原栈顶节点 return 1; // 出栈成功 }我这次特意用了指针的指针写法因为出栈操作不仅要取出数据还要修改栈顶指针本身。如果你用单指针StackNode *top在函数内部给top赋新值也影响不到外部变量出栈出来的结果没法同步。还有free这一步千万不要省。链式栈自己管内存申了多少就要还多少。你在一个循环里疯狂push一万个节点从不free程序表面安然无恙但内存占用一路飙升最后系统把进程杀掉你都不知道为什么。另外注意一个细节我让出栈函数返回int而不是char。原因在于空栈的时候根本没有元素可取这时候需要一个“出栈失败”的信号。如果你让函数返回char那失败时怎么办返回\0万一栈里存的恰好就是\0呢没法区分。用int做返回值区分成功和失败再用指针参数把数据带出来是C语言里非常经典的做法。如果你实在不习惯指针的指针也可以换一种写法用单指针加返回值StackNode *pop(StackNode *top, char *result) { if (top NULL) { return NULL; } StackNode *temp top; *result temp-data; top top-next; free(temp); return top; }逻辑完全一样只是改成了返回值更新法。两种风格我都见过ACM选手偏爱后者工程码农习惯前者看你自己的手感。3.3 链栈的遍历显示验证栈内状态最直观的方法调试的时候光靠眼睛跟踪指针变量很折磨人最直接的办法就是写一个遍历函数把栈里的元素从顶到底全部打印出来。因为栈只能从栈顶访问所以遍历顺序天然就是“后进先出”。void displayStack(StackNode *top) { if (top NULL) { printf(栈为空\n); return; } printf(栈顶 - ); StackNode *current top; while (current ! NULL) { printf(%c , current-data); current current-next; } printf(- 栈底\n); }这里用一个current指针从栈顶一路往后走。千万不要直接动传入的top否则你的栈顶指针都不知道飞去哪了。每次入栈出栈之后调用一次displayStack就能非常直观地看到“栈里现在还剩什么”。我在给学生演示括号匹配算法的时候每处理一个字符就打印一次栈的状态那种层层压入又层层弹出的感觉看代码是一回事看打印输出又是另一回事后者理解的效率要高得多。3.4 摧毁整个栈避免内存泄漏的收尾操作前面说了链式栈的内存全指望自己回收。栈用完了得写一个“清空”函数把链表上的每一个节点都释放掉。这个函数的思想是不断弹出栈顶直到栈空。void clearStack(StackNode **top) { while (*top ! NULL) { StackNode *temp *top; *top (*top)-next; free(temp); } printf(栈已清空\n); }有人可能觉得程序一结束操作系统会自动回收内存写不写这个函数无所谓。这话在只跑一次的判断题程序里勉强说得通但一旦你的栈是在一个大型程序的某个模块里用到的模块结束而进程还在那内存就泄漏了。生产环境下的内存泄漏就是这么一点一点攒出来的。养成良好的收尾习惯从写练习代码的时候就开始成本最低。4. 括号匹配算法从概念到可运行的完整代码前面所有铺垫都是为了这一刻把栈的操作组装成一个能真正检测括号匹配的程序。4.1 算法的判断流程与边界条件括号匹配算法的完整流程大概是这样走初始化一个空栈。从字符串的第一个字符扫到最后一个字符。如果是左括号(、[、{入栈。如果是右括号)、]、}先看栈是否为空。如果为空说明这个右括号前面根本没有可配对的左括号直接判定不匹配。如果栈不为空弹出栈顶左括号判断它和当前右括号是否是同一类型。整个字符串扫描结束后如果栈里还有剩余左括号说明有些括号从未被关闭还是不匹配栈为空才说明所有括号都正确配对了。边界情况要特别注意空字符串应该算匹配成功因为不存在任何未配对的括号只有右括号没有左括号的情况要在第4步拦下来只有左括号没有右括号的情况要靠最后栈清空与否来判断。4.2 完整代码实现与逐步解析下面这段代码是一个完整的可运行程序你直接复制进编译器就能跑#include stdio.h #include stdlib.h #include string.h typedef struct StackNode { char data; struct StackNode *next; } StackNode; // 初始化空栈 StackNode *initStack(void) { return NULL; } // 入栈 StackNode *push(StackNode *top, char value) { StackNode *newNode (StackNode *)malloc(sizeof(StackNode)); if (newNode NULL) { printf(内存分配失败!\n); return top; } newNode-data value; newNode-next top; return newNode; } // 出栈 StackNode *pop(StackNode *top, char *result) { if (top NULL) { return NULL; } StackNode *temp top; *result temp-data; top top-next; free(temp); return top; } // 判断左右括号是否匹配 int isMatch(char left, char right) { if (left ( right )) return 1; if (left [ right ]) return 1; if (left { right }) return 1; return 0; } // 括号匹配核心算法 int checkBrackets(const char *str) { StackNode *top initStack(); int length (int)strlen(str); for (int i 0; i length; i) { char ch str[i]; if (ch ( || ch [ || ch {) { top push(top, ch); } else if (ch ) || ch ] || ch }) { // 遇到右括号但栈是空的说明无左括号可配 if (top NULL) { printf(第 %d 个字符 %c 匹配失败多余的右括号\n, i 1, ch); clearStack(top); return 0; } char topChar; top pop(top, topChar); if (!isMatch(topChar, ch)) { printf(第 %d 个字符 %c 匹配失败与栈顶 %c 类型不匹配\n, i 1, ch, topChar); clearStack(top); return 0; } } // 其他字符比如字母数字、空格直接忽略不参与匹配 } if (top ! NULL) { printf(匹配失败存在未配对的左括号\n); displayStack(top); clearStack(top); return 0; } printf(括号全部匹配成功!\n); clearStack(top); return 1; } void displayStack(StackNode *top) { if (top NULL) { printf(栈为空\n); return; } printf(栈顶 - ); StackNode *current top; while (current ! NULL) { printf(%c , current-data); current current-next; } printf(- 栈底\n); } void clearStack(StackNode **top) { while (*top ! NULL) { StackNode *temp *top; *top (*top)-next; free(temp); } } int main(void) { const char *test1 ((ab)*[c-d]); const char *test2 ([)]; const char *test3 (ab)*(c-d; const char *test4 (ab)); const char *test5 ; printf(测试1%s\n, test1); checkBrackets(test1); printf(\n测试2%s\n, test2); checkBrackets(test2); printf(\n测试3%s\n, test3); checkBrackets(test3); printf(\n测试4%s\n, test4); checkBrackets(test4); printf(\n测试5空字符串\n); checkBrackets(test5); return 0; }特别提醒一下我在clearStack用的是StackNode **top而上面代码里调用时传top是匹配的但push返回新栈顶pop接收旧栈顶并返回新栈顶两种风格混在一起用初学者可能看着看着就迷糊了。这确实是一个教学上的取舍我想让你见识两种常见写法但代价就是代码风格不够统一。你实际写工程代码时建议统一成一种风格要么全部用返回值传新栈顶要么全部用二级指针混着用容易出隐蔽bug。整个程序的运行结果应该是((ab)*[c-d])匹配成功。([)]第3个字符)和栈顶[类型不匹配失败。(ab)*(c-d最后栈里剩了(失败。(ab))第6个字符)是多余的失败。匹配成功。这五个测试用例分别对应了五种不同的情况正常嵌套、交叉不匹配、缺右括号、缺左括号、空输入。我自己调试的时候也是拿这几组数据反复跑直到全部通过才敢说程序逻辑没问题。4.3 为什么有效括号的判断其实是在做“消除”而不是“计数”这里再把思维拔高一点。很多人第一反应是用三个计数器分别记录三种括号的数量每当看到左括号就加一看到右括号就减一最后看三个计数器是不是都归零。这个思路对()这种单一类型的括号管用但对([)]这种交叉嵌套就彻底失效了。因为(跟]虽然数量上配平了但它们在结构上压根不是一对。栈的思路本质上是一个“即时消除”的过程每看到一个右括号就把它和最近的左括号配对配对成功就把这对消除掉栈里只保留“还没配对的左括号”。这个“消除”操作完成之后剩下的问题只剩“栈是否为空”。它比计数更贴近括号语法的真实语义——括号不仅要数量对位置和顺序也必须对。这也是为什么像IDE、编译器的语法检查器全都用栈来校验括号配对的根本原因。它不是“一种办法”而已它是这个问题在计算模型上的最优解之一。5. 链式栈的常见坑点与调试经验——这些教训是用一次次的段错误换来的代码写出来了能跑通不算完。要真正理解链式栈必须把那些最容易出事的坑提前摸一遍。下面几个问题几乎每个学到这里的人都会踩上至少一个。5.1 空栈出栈最经典的段错误来源前面写的pop里先判断了top NULL但很多人一开始是不写的。直接上来就StackNode *temp top; *result temp-data;。如果此时栈是空的top是NULL对NULL取-data在你面前的就是一个字面意义的“段错误”程序当场崩溃。这种错误最让人头疼的地方在于它不一定是稳定复现的。有时候字符串里最后一个字符恰好是右括号栈刚好被弹空了下一个字符又来一个右括号崩溃就发生了。你调试半天可能试了好几个用例都没问题偏偏某一条输入就会炸。排查的思路是每次出栈前先问“栈是否为空”这永远不该被省略。括号匹配算法里右括号来临时栈为空这个分支尤其重要必须在入逻辑之前就单独处理。很多 LeetCode 上的题解为什么看起来很短不是省略了这个判断而是判断逻辑被写进了循环条件里比如先判断top NULL就直接返回。别学着学着把这一步给省了。5.2 忘记接住返回值或忘记free我之前带的学生里十个人至少有四个人犯过这个错push(top, (); // 没有接收返回值top的值压根没变入栈白入了。链表类的操作基本都要么传二级指针要么接住返回值二者必有其一。千万别觉得push内部改了top外部的top就能跟着变——C语言没有引用传参只传值。另一类错误是free放错了位置。入栈函数里malloc的新节点生命周期要延续到出栈时才能free。有些初学者在入栈函数结尾就把节点释放了结果发现压进去的字符全是乱码。那是因为节点内存虽然已经还给系统了但指针还指着那块已经失效的区域访问它属于未定义行为什么奇怪的结果都可能冒出来。这类问题用调试器查很熬人最好从开头就养成“谁分配谁释放、什么时候分配什么时候释放”的习惯。5.3 用char *直接扫描时别忘掉字符串的长度和边界checkBrackets函数用了strlen(str)获取长度再通过下标访问每一个字符。这里有个隐藏前提传入的字符串必须是以\0结尾的合法C字符串。如果你手动构造的字符数组忘了末尾的\0strlen会一路读到野内存去返回一个巨大的数字循环条件瞬间失控程序直接乱成一锅粥。如果不想依赖strlen也可以改成指针扫描直接while (*str ! \0)。两种写法本质一样但我更推荐下标法调试时能看到i的值出错的时候好定位到底是第几个字符出的问题。5.4 嵌套深度的真实测试与栈溢出风险链式栈理论上没有容量上限但别高兴太早。每入栈一个节点就调用一次malloc。如果你拿一个嵌套了上百万层括号的字符串去测每层都要malloc内存消耗巨大不说递归深入太多还可能把栈空间耗尽。这属于极端场景真实的代码不会嵌套那么深但那种“我们不怕大数据”的幻觉不能有。实测下来嵌套几千层括号在普通PC上没有任何压力代码跑得非常顺滑。这个量级已经远超绝大多数真实代码的嵌套深度了。真要说链式栈比顺序栈有优势的场景恰恰就是这种“深度不可预知”但实际又不会太夸张的情况——数组开大了浪费开小了又不够链表这边完全不用纠结。5.5 用调试输出验证每一步状态实战经验告诉我写完链式栈之后先别急着跑括号匹配而是先单独测试push、pop、displayStack三个基本操作。比如StackNode *top initStack(); top push(top, a); top push(top, b); top push(top, c); displayStack(top); // 预期输出栈顶 - c b a - 栈底 char ch; top pop(top, ch); printf(弹出:%c\n, ch); // 预期输出弹出:c displayStack(top); // 预期输出栈顶 - b a - 栈底先确保每个零件没有问题再组装成完整系统。这比直接写一个500行的大程序然后从头调错要清爽一百倍。C语言不像那些带垃圾回收的高级语言每一步内存操作都得自己心里有数。你能看到打印里的c b a就说明指针关系是对的后面出了任何问题都不用再怀疑链表的连接了。6. 括号匹配链式栈之外这个模型还能走向哪里写完了括号匹配千万别以为链式栈的学习就到此为止了。数据结构这种东西最大的价值不是背下来某种操作步骤而是明白“什么样的问题底子是什么模型”。括号匹配只是栈模型最经典但也最浅的一个应用。6.1 表达式求值从语法到运算的直接延伸你自己写一个计算器输入一串中缀表达式1 2 * 3计算机怎么知道要先算乘再算加普通的从左往右扫描根本做不到。经典的做法是把中缀表达式转成后缀表达式再用栈来求值。遇到数字入栈遇到运算符就弹出两个操作数做运算再把结果压回去。整个过程你会惊讶地发现跟括号匹配里“遇到右括号弹出左括号”的模式几乎一模一样。可以说如果你今天把链式栈的push和pop练熟了明天学表达式求值就是水到渠成的事。6.2 函数调用的底层到底是怎么运作的每一门高级语言都有函数调用栈。你调用函数AA里边再调用函数BB执行完返回A接着往下跑。这个“嵌套调用再逐层返回”的先后顺序和栈的后进先出完全吻合。每调用一个函数系统就往调用栈里压入一个栈帧存着局部变量、返回地址这些信息函数一返回这个栈帧就被弹出。这也是为什么递归不能无限深入——栈的容量是有限制的递归太深就会栈溢出。理解了链式栈你再看递归调用栈这几个字脑子里就不再是一片模糊了。6.3 浏览器历史记录与撤销操作的同一个模型你按一下浏览器“后退”按钮回到的是上一个页面不是最初打开的页面这就是一个标准栈行为。编辑器里的CtrlZ也是每撤销一步就弹出最近的那个操作。这些日常场景都是栈模型只是它们跑在你看不见的地方。学数据结构最有意思的时刻就是你突然意识到原来身边这么多看起来八竿子打不着的东西底层都在干同一件事。6.4 再往后走从中缀转后缀到树与图栈学会了往后还有队列、二叉树、图。中缀转后缀练的是“运算符优先级”二叉树遍历里有一种非递归写法就用栈模拟递归过程图的深度优先搜索同样可以基于栈。你会发现栈这个“简单的容器”简直是无处不在的骨架。C语言本身没有内建栈容器但只要你会写链表你就拥有了一切的起点。把链式栈的代码吃透之后每学一个新结构回头看看这份练习代码都会多一分亲切感。数据结构的学习曲线前期确实陡峭但你亲手写过的每一行malloc和free都会在后面的路上不断给你回报。