1. 为什么要用栈解决括号匹配在C语言的学习路径里栈和队列几乎是绕不开的两座山。很多初学者都会问数组就能存数据为什么还要单独搞一个栈出来我的回答通常是——你看完括号匹配这个例子就明白了。括号匹配的规则是这样的给定一串字符串里面包含(、)、[、]、{、}这六种字符你需要判断括号的使用是否合法。什么叫合法([{}])是合法的([)]是不合法的(]是不合法的{[]}是合法的。规则说到底就两条左括号和右括号要能一一对应而且嵌套的顺序不能乱。这个问题的关键在哪里在于“最近出现的左括号必须先被匹配”。举个例子字符串(([]))扫描到第一个右括号)时它要匹配的不是最外层的(而是最近的那个(。这种“后进先出”的需求天然就跟栈的特性吻合了——栈顶就是最新入栈的元素出栈操作永远从栈顶开始。那链条式栈链式栈又比顺序栈好在哪顺序栈用数组实现容量固定一旦装满了就得扩容代码里要判断栈满还要处理 realloc 之类的事情。链式栈没有这个烦恼每入栈一个元素就分配一个节点内存按需分配理论上不受长度限制只要内存够。对于括号匹配这种输入长度不确定的场景链式栈用起来更安心。这个例子特别适合初学者作为第一次“数据结构实战”来练手因为它需要你亲手实现四个核心操作——初始化、入栈、出栈、显示——但又不像链表增删那么复杂。学完这个例子你去理解中缀表达式求值、函数调用栈、浏览器的前进后退会发现它们用的都是同一套思想。2. 链式栈的设计思路节点、栈顶与框架2.1 先想清楚数据结构长什么样链式栈的本质是一个单向链表但只能在“栈顶”这一端做插入和删除。所以我先定义一个节点结构体它由两部分组成数据域和指针域。typedef struct StackNode { char data; // 存放括号字符 struct StackNode *next; // 指向下一个节点 } StackNode;这里我把 data 定义为char因为括号匹配只需要处理单个字符。如果你之后想拿这个栈存整数、浮点数把这个类型换成int、double就行其他逻辑完全不用动。接下来需要定义一个栈顶指针。在链式栈里我不需要像顺序栈那样定义top作为数组下标而是直接定义一个指向StackNode的指针栈顶就是链表的头结点位置。入栈相当于头插法出栈相当于删除头结点。typedef struct { StackNode *top; // 栈顶指针 int count; // 栈中元素个数 } LinkStack;你可能会问已经有了top指针为什么还要count因为显示栈内元素、判断栈是否为空、以及后续统计入栈出栈次数时count能直接告诉你栈的深度省去遍历链表的麻烦。空间开销只是一个int非常划算。2.2 为什么采用“带头节点”还是“不带头节点”链式栈的实现有两种风格一种是有头节点头节点不存数据只是方便统一操作另一种是无头节点top直接指向第一个数据节点。我的建议是写链式栈用无头节点更顺手。原因有三点括号匹配的入栈和出栈都非常频繁无头节点时入栈操作只需要两行代码逻辑更直观判断空栈只需要检查top NULL不用绕一圈去看头节点的 next无头节点的内存更省不需要为了一个哨兵节点多 malloc 一次。当然如果你后续要写的是带并发控制的复杂栈头节点可能帮你省去一些判空的麻烦那是另一套设计思路。就本题而言无头节点就是最优解。2.3 一个容易被忽略的细节栈的销毁与内存释放不少初学者写完入栈、出栈、显示就认为任务完成完全忘了释放内存。在 C 语言里你每次malloc都必须对应一次free否则跑一次两次没感觉连续跑几百组测试用例就会出现内存泄漏程序越跑越慢严重的会直接崩掉。所以我在设计时就规划好了一个DestroyStack函数循环出栈直到栈空再把栈顶指针置空。这个函数一方面用于程序结束前的资源回收另一方面也可以用于“清空栈并重新开始”的场景。void DestroyStack(LinkStack *s) { while (s-top ! NULL) { StackNode *temp s-top; s-top s-top-next; free(temp); } s-count 0; }这里每一次循环都用一个临时指针temp保存当前栈顶节点地址先让top前进到下一个节点再free掉temp顺序不能反。如果把free放在前面下一步访问s-top-next就是访问已经释放的内存属于典型的悬垂指针问题。3. 核心操作逐段拆解3.1 初始化别把指针一开始就搞成野指针初始化是整个链条的第一环也是出错率最高的一环。很多同学喜欢在 main 函数里直接写LinkStack s; Push(s, ();然后一路调用都很“正常”直到程序运行到某个边界条件时突然崩溃回头排查发现s.top一开始就没有赋值。正确的初始化长这样void InitStack(LinkStack *s) { s-top NULL; s-count 0; }逻辑只有两行但意义重大。它保证栈顶指针是NULL而不是一个随机地址保证count是 0 而不是某个垃圾值。后面所有判断空栈的逻辑都是建立在“初始化后的栈顶一定为 NULL”这个前提之上。调用方式要特别注意传入的是结构体指针s因为初始化要修改结构体内部的字段。如果是void InitStack(LinkStack s)形参只是实参的一份拷贝函数内部改得再热闹外面的栈依然是未初始化的状态。这是 C 语言“传值调用”机制导致的经典错误我在后面常见问题部分会再展开。3.2 入栈头插法封装成两行操作入栈操作的思路是新节点指向原栈顶然后让栈顶移动到新节点。代码实现如下void Push(LinkStack *s, char ch) { StackNode *newNode (StackNode *)malloc(sizeof(StackNode)); if (newNode NULL) { printf(内存分配失败入栈操作终止。\n); return; } newNode-data ch; newNode-next s-top; s-top newNode; s-count; }这里有一个非常容易被忽略的检查malloc的返回值是否为 NULL。虽然在你平时跑的作业题里内存分配几乎不可能失败但一旦进入真实项目内存耗尽的情况是真实存在的。面试官也喜欢问这一个点——能不能察觉内存分配失败是健壮性的分水岭。入栈时如果栈是空的s-top是 NULL那么newNode-next NULL栈顶就指向这个唯一节点完全没问题。如果栈里有元素newNode-next指向原栈顶然后s-top换成 newNode新节点就成了新的栈顶。整个过程等效于单链表的头插法只是把“头节点”理解为“栈顶节点”。3.3 出栈先判空再动手出栈要做的三件事判断栈空、保存栈顶值、更新栈顶并释放旧节点。int Pop(LinkStack *s, char *value) { if (s-top NULL) { return 0; // 栈为空无法出栈 } StackNode *temp s-top; *value temp-data; s-top s-top-next; free(temp); s-count--; return 1; }我特意把返回值设计成int1 表示出栈成功0 表示栈空。为什么要这样设计因为括号匹配过程中很有可能会遇到“栈已经空了但还有一个右括号”的情况这时候如果出栈函数没有返回值而是直接 return主调函数根本不知道出栈失败会拿着一个垃圾值去做匹配判断结果全乱套。出栈值的传递我用了char *value指针参数这也是 C 语言里常见的“返回一个值 输出一个值”的模式。你可以理解为函数要么通过 return 告诉外部是否成功要么通过指针参数带出出栈的字符两者互不干扰。3.4 显示栈内容从栈顶往下数显示栈顶到栈底的元素其实就是遍历一遍链表。void DisplayStack(LinkStack *s) { if (s-top NULL) { printf(栈为空。\n); return; } StackNode *cur s-top; printf(当前栈中元素从栈顶到栈底); while (cur ! NULL) { printf(%c , cur-data); cur cur-next; } printf(\n); }这里用了一个临时指针cur来遍历千万不能用s-top直接遍历。如果你写成while (s-top ! NULL) { printf(...); s-top s-top-next; }虽然也能把栈里的元素打出来但副作用是把栈顶指针移到了 NULL整个栈已经被你打空了后面的匹配逻辑全部失效。这是实打实踩过的坑写的时候手一滑就会犯。显示功能虽然和括号匹配没有直接关系但它是调试的“眼睛”。我在调试过程中会频繁调用DisplayStack来观察当前栈的状态确认每一步入栈、出栈后栈顶元素是否符合预期。没有这个函数你就只能干瞪眼猜代码哪里出了问题。4. 完整代码可直接复制的括号匹配程序4.1 主函数逻辑匹配的核心思路括号匹配的主函数逻辑可以用一句话概括左括号入栈右括号判断与栈顶是否匹配。具体的判断规则是遇到([{一律入栈。遇到)看栈顶是否为(是则出栈否则匹配失败。遇到]看栈顶是否为[是则出栈否则匹配失败。遇到}看栈顶是否为{是则出栈否则匹配失败。全部字符扫描完后如果栈为空说明所有左括号都找到了对应的右括号匹配成功栈不为空说明有左括号没被匹配匹配失败。这里我写了一个辅助函数来配对判断int IsMatch(char left, char right) { if (left ( right )) return 1; if (left [ right ]) return 1; if (left { right }) return 1; return 0; }这个辅助函数让主函数的代码保持简洁不用在每个右括号的类型判断里重复写一堆 if。后续如果要支持更多符号对比如尖括号只需要在这个函数里加一行其他逻辑完全不用动。完整主函数int CheckBrackets(const char *str) { LinkStack stack; InitStack(stack); for (int i 0; str[i] ! \0; i) { char ch str[i]; if (ch ( || ch [ || ch {) { Push(stack, ch); } else if (ch ) || ch ] || ch }) { if (stack.top NULL) { printf(错误第 %d 个字符 %c 没有匹配的左括号。\n, i 1, ch); DestroyStack(stack); return 0; } char topChar; Pop(stack, topChar); if (!IsMatch(topChar, ch)) { printf(错误第 %d 个字符 %c 与栈顶 %c 不匹配。\n, i 1, ch, topChar); DestroyStack(stack); return 0; } } // 其他字符直接忽略不参与匹配 } if (stack.top ! NULL) { printf(错误栈中还有 %d 个左括号未匹配。\n, stack.count); DisplayStack(stack); DestroyStack(stack); return 0; } DestroyStack(stack); printf(括号匹配成功\n); return 1; }4.2 完整程序汇总把前面所有函数拼在一起就是一份可以直接在本地编译器运行的完整程序#include stdio.h #include stdlib.h typedef struct StackNode { char data; struct StackNode *next; } StackNode; typedef struct { StackNode *top; int count; } LinkStack; void InitStack(LinkStack *s) { s-top NULL; s-count 0; } void Push(LinkStack *s, char ch) { StackNode *newNode (StackNode *)malloc(sizeof(StackNode)); if (newNode NULL) { printf(内存分配失败入栈操作终止。\n); return; } newNode-data ch; newNode-next s-top; s-top newNode; s-count; } int Pop(LinkStack *s, char *value) { if (s-top NULL) { return 0; } StackNode *temp s-top; *value temp-data; s-top s-top-next; free(temp); s-count--; return 1; } void DisplayStack(LinkStack *s) { if (s-top NULL) { printf(栈为空。\n); return; } StackNode *cur s-top; printf(当前栈中元素从栈顶到栈底); while (cur ! NULL) { printf(%c , cur-data); cur cur-next; } printf(\n); } void DestroyStack(LinkStack *s) { while (s-top ! NULL) { StackNode *temp s-top; s-top s-top-next; free(temp); } s-count 0; } 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) { LinkStack stack; InitStack(stack); for (int i 0; str[i] ! \0; i) { char ch str[i]; if (ch ( || ch [ || ch {) { Push(stack, ch); } else if (ch ) || ch ] || ch }) { if (stack.top NULL) { printf(错误第 %d 个字符 %c 没有匹配的左括号。\n, i 1, ch); DestroyStack(stack); return 0; } char topChar; Pop(stack, topChar); if (!IsMatch(topChar, ch)) { printf(错误第 %d 个字符 %c 与栈顶 %c 不匹配。\n, i 1, ch, topChar); DestroyStack(stack); return 0; } } } if (stack.top ! NULL) { printf(错误栈中还有 %d 个左括号未匹配。\n, stack.count); DisplayStack(stack); DestroyStack(stack); return 0; } DestroyStack(stack); printf(括号匹配成功\n); return 1; } int main() { char str[100]; printf(请输入待检查的字符串不超过99个字符\n); fgets(str, sizeof(str), stdin); // fgets 会带上换行符这里去掉 for (int i 0; str[i] ! \0; i) { if (str[i] \n) { str[i] \0; break; } } int result CheckBrackets(str); printf(检查结果%s\n, result ? 匹配 : 不匹配); return 0; }4.3 运行效果演示我实际编译运行了一下几个典型输入的结果如下输入字符串运行结果(ab)括号匹配成功{[()]}括号匹配成功([)]错误第 4 个字符)与栈顶[不匹配。((((错误栈中还有 4 个左括号未匹配。ab)错误第 4 个字符)没有匹配的左括号。[]{}()括号匹配成功其中([)]这个案例最能体现栈的“就近匹配”特性扫描到)时栈顶是[因为[是最近被压入的左括号它和)不匹配所以直接判定失败而不用管前面还有一个(。5. 踩坑实录五个高频问题与排查方法5.1 传值还是传址为什么栈没有变化这是新手最容易踩的第一个坑。如果函数的形参写的是LinkStack s而不是LinkStack *s那么调用Push(s, ()后函数内部处理的是结构体的一份拷贝外面栈的 top 完全没变。表现为入栈操作执行完接着调用DisplayStack结果栈还是空的。排查方法也很简单检查每个需要修改栈的函数的形参是不是带*。可以记住一个口诀——只要函数体内要修改结构体内容就传地址只是读取内容可以传结构体本身。5.2 fgets 带来的换行符问题我在 main 函数里用fgets读取输入而不是scanf(%s, str)是因为fgets可以读取包含空格的字符串比如(a b) * [c]这种表达式scanf(%s)会在空格处截断。但fgets会把你输入末尾的换行符也读进来结果就是字符串变成了(ab)\n。括号匹配时这个换行符既不是左括号也不是右括号所以被直接忽略往往不会出问题。但如果你后续在栈里压入的是其他字符或者你想要精确的字符串长度这个换行符就可能引发莫名其妙的 bug。所以在读入之后我主动把换行符替换成字符串结束符\0。如果你是在 Windows 的 Dev-C 环境可能还要处理\r\n两个字符原理是一样的注意偏移量。5.3 malloc 后忘记 free内存泄漏在 CheckBrackets 函数里我设置了三个提前返回的出口找不到左括号、括号不匹配、栈非空结束。每个出口我都调用了DestroyStack。如果不调用程序在测试少量用例时不会有任何感觉但一旦放进循环里测试几百组字符串内存占用会肉眼可见地增长。防范举措有两个层面。第一写完代码后全局搜索malloc看每一次分配是否都有对应的free。第二用 Valgrind 工具检测命令是valgrind --leak-checkfull ./a.out它会直接告诉你哪一行分配的内存没有被释放。这是 C 语言开发者必须掌握的基本排查工具。5.4 用 top 直接遍历导致栈被“打空”这个问题我在 3.4 节已经重点提过。真实调试时我曾为了图省事在DisplayStack里用s-top直接遍历结果匹配逻辑全部乱了套折腾了很久才发现是自己的“调试工具”把栈给清了。最稳妥的写法就是用一个局部变量cur来遍历保持s-top指向真正的栈顶。如果你发现自己为了查看栈内容而破坏了栈那就说明遍历方式用错了。5.5 字符数组越界与长度陷阱如果你用scanf(%s, str)输入而字符串长度超过了数组容量就会发生缓冲区溢出。虽然这是网络安全课程里专门讲的话题但我们现在也要有意识地防护。我的处理方法是使用fgets(str, sizeof(str), stdin)第二个参数直接限制最大读取长度这是 C11 标准推荐的安全做法。另外代码中str[100]只能存放 99 个字符加一个结束符输入时我心里要有数。6. 关于链式栈的几个经验之谈6.1 链式栈和顺序栈怎么选写这个练习题时很多同学会问既然数组栈顺序栈也能实现括号匹配而且代码更短为什么还要学链式栈我的看法是两者不是替代关系而是互补关系。顺序栈的优势是随机访问快、缓存友好、实现简单适合栈内元素数量可预估的场景。链式栈的优势是容量动态、不会满栈适合长度未知、波动大的场景。括号匹配这个例子本质上是一个教学脚手架它的最终目的是让你掌握链式栈这个“武器”而不是为了解题本身。你看后面的编译器语法分析、函数调用栈、内存管理中的栈区本质上都是栈思想的应用。理解这个思想比背下来一份代码重要得多。6.2 用count字段辅助日志分析调试链式栈时count字段给了我们一个极其方便的“观察哨”。在Push和Pop函数里可以临时加一行调试代码printf(入栈 %c当前栈深%d\n, ch, s-count);这样就能直观地看到字符串扫描过程中栈深度的变化曲线。我在调试时发现栈深度峰值往往能反映表达式的最大嵌套深度这个指标对于代码编辑器做语法高亮、缩进提示都有实际价值。6.3 扩展思路从括号匹配到表达式求值学完括号匹配你可以顺势给自己加一个扩展任务实现一个支持加减乘除的四则运算表达式求值器。思路是设置两个栈一个数字栈一个运算符栈扫描表达式时按优先级压栈和出栈。你会发现之前括号匹配里学到的所有知识都能复用只是把“括号字符”换成了数字和运算符把“匹配判断”换成了优先级比较。这个扩展练习做完你对栈的理解会从“知其然”升华到“知其所以然”。我个人建议你把链式栈的代码好好封装成一套独立的模块之后做任何项目需要栈结构时直接拿过来用比每次上网抄一段不熟悉的代码要可靠得多。最后再分享一个我自己的实操习惯写完链式栈之后我一定会用 Valgrind 和 AddressSanitizer 各测一遍。前者查内存泄漏后者查越界访问和悬垂指针。这两个工具用熟了你的 C 语言代码质量会上一个台阶调试效率也会明显提升。括号匹配只是起点但代码里的好习惯从这个小小的程序开始养成一点都不亏。