前阵子做数据结构实验正好轮到了栈这一章的 PTA 练习里面最有代表性的一道题就是”括号匹配判断”。题目本身一句话就能说清给你一串字符里面可能出现()[]{}三种括号判断它们在嵌套和顺序上是不是成对匹配的。听起来很简单可我第一版代码用的是“数括号个数”结果碰到([)]这种输入直接翻车。后来老老实实用栈实现才真正理解这道题为什么能成为栈的入门必考题。这篇文章把我完成这个实验的全过程整理了一遍包含算法核心逻辑、C 语言完整实现、PTA 这类在线评测系统里容易踩的输入输出坑以及一批可以直接拿去跑的测试用例。如果你是正在做数据结构实验的大学生或者刚接触栈的自学者可以参考这套思路少走一点弯路。1. 实验目标与前置知识——括号匹配为什么是栈的入门必做题1.1 这个实验到底在解决什么问题括号匹配题目在真实场景里随处都是写代码时的花括号、表达式里的圆括号、数组下标里的方括号甚至 HTML 标签的嵌套也可以用同一套思路去检查。判断“匹配”至少要满足两个条件第一每个右括号必须有一个同类型的左括号在它之前出现并且两者之间不能有交叉未闭合的括号。第二扫描完整串之后所有左括号都应该被闭合不能有“孤儿”左括号。不合法的情况大致分三类。第一类是左括号多余比如((())最后一对括号缺了右半边。第二类是右括号多余比如()))扫描到某个右括号时前面已经没有可匹配的左括号了。第三类最阴险左右括号数量相等但类型或者顺序不对比如([)]你要说它“数量对”确实一对不多一对不少可)匹配到的却是前面那个还没闭合的[明显是交叉嵌套不合语法。这道实验题看起来只是让数组里的一串字符“配对”但它背后涉及的概念正是栈这一章最核心的能力保存一种“倒序”的等待关系。理解了这一点后面做表达式求值、括号自动补全、甚至编译原理里的语法分析都会顺畅很多。1.2 栈的“后进先出”恰好匹配嵌套逻辑为什么说括号匹配和栈是天生一对因为括号的嵌套结构本质上是“递归”的内部的括号先闭合外层的括号后闭合。当我读到一个右括号时真正要匹配的是“最近一次出现、且还没有匹配成功的那个左括号”。这个“最近一次”就是栈顶。拿字符串[()]举例。扫描到[时入栈栈里是[扫描到(时入栈栈里是[、(。接着扫描到)此时栈顶是(正好配对弹出。再扫描到]此时栈顶是[配对弹出。最后栈空判定合法。整个过程栈里的元素越靠近栈顶对应的左括号在原文中的位置就越靠后但它应当越先被右括号匹配。这就像叠盘子后放上去的盘子一定先被拿走。括号匹配问题需要的正是这种“后进先出”的等待队列所以栈是自然解而不是老师故意为难你。我之前也试着用队列、用数组计数去硬凑最后发现都是在绕远路。一旦接受“每次只看最近一个未匹配左括号”这个视角代码逻辑就一下子清楚了。2. 算法逻辑逐层拆解——从计数陷阱到出栈校验2.1 为什么“数括号个数”不行很多初学者写这道题的第一版都会这样做分别统计(和)的个数如果相等就输出 YES。问题是这种计数方案把“顺序信息”完全抹掉了。([)]就是经典反例。统计小括号一个(、一个)统计方括号一个[、一个]。数量全都相等。但你把括号按位置展开(在最左[在第二)在第三]在最后。第三个字符)出现时离它最近、还没被匹配的左括号是[不是(。此时应该报错但计数法根本不知道这个顺序差异。计数法相当于把一行括号“压扁”成几个数字丢失了所有位置关系。而括号匹配本质上是一个“就近配对”问题它需要的信息是动态的在遍历过程中你要随时知道“当前还欠着哪些左括号谁是最新的”。这些信息只能用一种额外结构保存下来栈就是这个结构。另外还有一种看似聪明的写法分别记录三种括号各自的左右数量然后只判断“同类的数量相等”。这种写法同样挡不住([)]因为它压根没有检查类型之间的交叉关系。真正正确的判断维度是“配对顺序”不是单纯的计数统计。2.2 匹配算法的完整流程设计正确的栈匹配算法其实只有四步初始化一个空栈。从左到右扫描字符串。当前字符是左括号(、[、{时直接压栈。当前字符是右括号)、]、}时先看栈是否为空。如果为空说明这个右括号没有可配对的左括号直接返回非法。如果栈不为空就弹出栈顶元素判断栈顶左括号是否与当前右括号同类型。如果类型不匹配返回非法。扫描完整个字符串后检查栈是否为空。栈为空说明所有左括号都被正确闭合返回合法栈不为空说明还有未匹配的左括号返回非法。为什么第一步遇到左括号直接压栈就行因为左括号的“未来”是不确定的它可能很快被匹配也可能要等到很后面。你不知道它什么时候结束那就先把它“放一边”等着用一个栈保存所有还没被匹配的左括号。为什么第二步要先判断栈空因为右括号出现时它必须先在某个左括号之后才有意义。如果一个右括号出现时前面没有任何待匹配的左括号说明它自己是多余的比如字符串)和()后的那个)都属于这种情况。为什么第三步要弹出栈顶而不是检查别的左括号因为括号嵌套永远是“就近闭合”当前右括号只能匹配离它最近的那个尚未闭合的左括号。在栈里离它最近的未匹配左括号就是栈顶。如果栈顶都不匹配那么整个字符串里不存在任何合法匹配——因为就算你假设把栈里更深的某个左括号拿来配对也会越过这个栈顶元素形成交叉。最后一步为什么还要检查栈空因为可能出现“左括号一直没等到右括号”的情况。比如字符串((()扫描结束之后栈里还剩着一个(它们都是没有被闭合的所以必须判非法。这三步加起来正好覆盖了上一节说的三类非法情况左括号多余、右括号多余、顺序交叉。2.3 时间复杂度与空间复杂度分析这个算法的时间复杂度是 O(n)其中 n 是字符串长度。每个字符最多被压栈一次、出栈一次遍历本身也只做常数次比较。空间复杂度是 O(n)。因为最坏情况下字符串全是左括号比如((((((...栈里要放 n 个元素。但平均情况下栈的大小通常远小于 n因为括号在正常语法里是会闭合的。O(n) 是这个问题的理论下界因为无论如何你都必须读完整个字符串才能确认最后一个右括号有没有匹配所以不存在更优的复杂度。这也是这个算法设计得非常干净的原因思路直观、实现简单、效率最优。3. C 语言完整代码实现与逐段解析3.1 栈的结构体定义与基础操作实验课老师通常要求体现栈的 ADT抽象数据类型所以我先用结构体方式写一版完整的 C 代码。栈用数组实现数组元素类型是chartop 指向当前栈顶元素的位置。top 初始化为 -1代表空栈。#include stdio.h #include string.h #define MAXSIZE 100005 typedef struct { char data[MAXSIZE]; int top; } Stack; void initStack(Stack *s) { s-top -1; } int stackEmpty(Stack *s) { return s-top -1; } int stackFull(Stack *s) { return s-top MAXSIZE - 1; } void push(Stack *s, char c) { if (stackFull(s)) { return; } s-data[s-top] c; } char pop(Stack *s) { if (stackEmpty(s)) { return \0; } return s-data[s-top--]; } int isPair(char left, char right) { if (left ( right )) return 1; if (left [ right ]) return 1; if (left { right }) return 1; return 0; } int bracketMatch(const char *str) { Stack s; initStack(s); int len strlen(str); for (int i 0; i len; i) { char c str[i]; if (c ( || c [ || c {) { push(s, c); } else if (c ) || c ] || c }) { if (stackEmpty(s)) { return 0; } char top pop(s); if (!isPair(top, c)) { return 0; } } } return stackEmpty(s); } int main() { char str[MAXSIZE]; if (fgets(str, MAXSIZE, stdin) ! NULL) { str[strcspn(str, \n)] \0; if (bracketMatch(str)) { printf(YES\n); } else { printf(NO\n); } } return 0; }这里最重要的是pop函数和bracketMatch函数的配合。pop在栈空时返回\0但bracketMatch在调用pop之前已经用stackEmpty检查过了所以不会出现“空栈弹出”的事故。两条逻辑一前一后顺序不能反。isPair函数只负责判断“两个括号是否同型配对”不关心栈的状态。这样把“类型匹配”和“栈操作”拆分到两个函数里逻辑清晰也方便测试。3.2 不用结构体的简洁写法如果你是在 PTA 上快速刷题不要求展示 ADT 封装完全可以直接用一个全局数组加一个 top 变量来写。逻辑完全一样代码更短。char stk[MAXSIZE]; int tp -1; int checkBrackets(const char *s) { for (int i 0; s[i]; i) { if (s[i] ( || s[i] [ || s[i] {) { stk[tp] s[i]; } else if (s[i] ) || s[i] ] || s[i] }) { if (tp 0) return 0; char topChar stk[tp--]; if (!isPair(topChar, s[i])) return 0; } } return tp 0; }为什么我推荐先用结构体版写一遍再用简洁版提交因为实验课老师大概率会检查代码里有没有体现栈的“进、出、判空”等操作。用数组裸写虽然没错但封装成 ADT 之后你对栈这种数据结构的理解会更加具象后续做到队列、二叉树实验时也会更容易迁移。3.3 PTA 常见输入输出格式的适配写法PTA 括号匹配题目常见的输入格式有两种一种是直接给一行字符串让你判断另一种是先给一个整数 T表示有 T 行字符串需要判断。单行输入的写法上面已经给出了。这里重点说多组输入的坑。先看这段代码int T; scanf(%d, T); getchar(); // 吃掉 scanf 之后残留的换行符 while (T--) { fgets(str, MAXSIZE, stdin); str[strcspn(str, \n)] \0; if (bracketMatch(str)) { printf(YES\n); } else { printf(NO\n); } }注意scanf(%d, T)后面的getchar()。scanf读走数字后回车换行符还会留在缓冲区里如果你不把它吃掉第一次fgets就会读到空行导致第一组数据永远是空的最后输出结果整体错位。这是多组输入里最常见的失误。strcspn(str, \n)的作用是找出字符串里第一个换行符的位置然后把它替换成字符串结束符\0相当于安全地去掉了fgets带进来的换行。别小看这一步如果不处理你的字符串末尾会带一个\n它虽然没有匹配逻辑上的影响但某些题目对读取内容有特殊要求时末尾换行会引入莫名其妙的错误。另外如果题目明确说字符串不包含空格你完全可以用scanf(%s, str)代替fgets省去处理换行的步骤。但一旦字符串可能包含空格就必须用fgets否则空格后面的内容会被当成本次输入之外的数据匹配结果自然不对。4. PTA 评测的隐藏规则与调试心得4.1 输入格式里的四个常见坑第一gets()函数别再用。gets在 C11 标准里已经被移除了PTA 的编译器升级之后你写gets很可能直接编译失败或者编译时给出一堆 warning。替代方案就是fgets再手动去换行符。这是我从编译错误里学到的教训。第二scanf(%d, T)之后一定要处理残留换行。前面已经解释过不加getchar()第一组数据就读空了。如果你不想用一个单独的getchar也可以直接写scanf(%d\n, T)把换行符放进格式串里但这种方式可读性差一点我习惯还是单独写一行。第三不要向标准输出打印任何提示信息。比如你本地调试时习惯写printf(请输入字符串)上传到 PTA 就会导致答案错误。因为在线评测系统只比对标准输出内容多一个字符都是多余的。本地调试归本地调试提交版本必须干净。第四输出的大小写要严格照抄题目。PTA 的字符串比对是精确匹配题目要求YES你就不能输出Yes要求yes也不能输出YES。这种错误在逻辑完全正确的情况下还能让人浪费很多时间所以提交前先看一眼输出样例。4.2 空串、单字符、长嵌套这些边界情况边界条件看起来简单但往往就是扣分的点。空串应该返回合法。因为没有括号不存在任何未匹配项。有些同学容易下意识觉得“没东西就是错”其实不对。bracketMatch()在执行中不会进入循环最后stackEmpty(s)返回 1输出 YES这是符合我们上面定义的正确行为。长度为 1 的字符串也要分别处理(会在扫描结束后发现栈非空而出错)会在第一次遇到右括号时发现栈为空而出错如果是普通字母a既不是左括号也不是右括号会被跳过最后栈空输出 YES。这个逻辑对题目里“其他字符忽略不计”的要求天然成立。嵌套深度非常大的时候比如 100000 个连续的(栈空间需要能存下 100000 个字符。如果 MAXSIZE 开成 10000程序就会越界轻则答案错误重则段错误。我的做法是先看题目给的字符串长度范围再决定数组大小。如果题目没有明说范围或者允许动态内存我会把 MAXSIZE 定成一个比较宽裕的值比如 100005避免边界测试时翻车。4.3 本地能跑、PTA 却报错的排查思路如果你在本地编译器上把所有样例都跑过了但提交 PTA 还是 WA不要急着改逻辑先按这个顺序排查。第一步看是不是多组输入的换行残留问题。加一句fgets打桩把实际读到的字符串输出到屏幕上确认第一行没有变成空行最后一组数据也没有被吞掉。第二步看是不是没去换行符导致字符串末尾多了一个\n。这个字符不影响括号匹配逻辑但如果题目要求“输出该字符串是否匹配”你可能在后续步骤里受到干扰。第三步看是不是输出格式出了问题。把样例输出逐字符对比一遍比如末尾有没有换行、大小写对不对、中间有没有多余空格。第四步检查栈边界。数组开小了会出现“部分正确”或者“段错误”。把 MAXSIZE 临时调大十倍再试一次如果立刻通过说明就是容量问题。第五步如果返回的是编译错误优先检查你有没有用gets、有没有在for循环里声明int i时使用了编译器不支持的语法。PTA 的环境一般支持 C99也就是可以在循环里声明变量但为了稳妥也可以把变量声明提到函数开头。这套排查顺序是实际提交过程中积累出来的。每次按部就班走一遍基本能在十分钟内定位问题而不是对着错误输出两眼一抹黑。5. 测试用例设计——正确性验证的完整清单5.1 可以直接抄走的测试样例下面是我做这个实验时实际用到的一组用例包含合法、非法和边界三种情况。你可以在本地把它们逐条跑一遍确认程序输出符合预期。输入期望输出说明()YES最基本的一对[]YES方括号示例{}YES花括号示例()[]{}YES多组并列匹配不需要如果题目只要求三种括号([]{})YES混合嵌套{[()]}YES深层嵌套((()))YES同类型多层嵌套[({})]YES不同类型嵌套(NO只有左括号缺右括号)NO只有右括号无左括号(]NO类型不匹配([)]NO经典交叉数量相等也不行{[}]NO交叉嵌套())NO右括号多余((()NO左括号多余空串YES没有括号天然合法abcYES其他字符忽略栈空在这些用例中([)]是最有价值的一条它能帮你区分“只会数个数”和“正确用栈”两种实现。如果程序在([)]上输出了 YES说明你的代码没有真正检查匹配顺序只是统计了数量。测试方法也很简单。把输入保存到一个文本文件里比如input.txt然后运行gcc -o bracket bracket.c ./bracket input.txt如果你的代码是按多组输入写的input.txt里第一行写组数后面每行一个字符串如果按单行输入写的input.txt里就放一个字符串。文件重定向的方式保证了测试的稳定性和可重复性特别适合反复改代码后回归。5.2 嵌套深度与栈容量的估算思路一个常见的坑是栈容量开得太小。要算出合理容量直接假设最坏情况输入长度为 n 的字符串而且所有字符都是左括号。那么每一次扫描都执行入栈操作栈里最多会同时存在 n 个元素。所以栈大小必须至少是“字符串最大长度 1”。如果题目给定了 n 的范围比如最多 100000直接开char data[100005]就行。如果题目没给稳妥起见开一个较大的数组或者用动态数组malloc按需分配。不过大多数 PTA 数据结构题目的字符串长度上限都不会太大100005 的数组足够应对绝大多数情况。这里也顺带说一个更省心的方案如果你所在的题目允许使用 C直接用 STL 的stackchar就不用手动管理容量了。#include iostream #include stack #include string using namespace std; bool checkBrackets(const string s) { stackchar st; for (char c : s) { if (c ( || c [ || c {) { st.push(c); } else if (c ) || c ] || c }) { if (st.empty()) return false; char top st.top(); st.pop(); if ((top ( c ! )) || (top [ c ! ]) || (top { c ! })) { return false; } } } return st.empty(); }STL 版本的优势是代码量小不容易犯越界错误。实验课如果老师要求手写栈你还是得用结构体版本但如果是自己刷题STL 的版本会更高效。两个版本我都写过最后给我的感觉是手写一遍能加深对 top 指针的理解STL 能帮你在算法题里节省时间二者不冲突。6. 括号匹配的实战延伸——从实验课到真实工程6.1 代码编辑器里的括号配对检查你平时用的代码编辑器在输入一个右括号时经常会高亮显示它对应的那个左括号。这个功能背后用到的思想就是括号匹配。简单实现思路是扫描缓冲区文本时遇到左括号就把它的位置压进栈遇到右括号时弹出栈顶位置如果配对就在编辑界面上把这两个位置高亮。真实编辑器可能还会记录行号、缩进、括号类型等额外信息但核心结构依然是栈。如果你以后要写代码格式化工具、语法检查插件这个思路可以直接套用。我自己写过一个小脚本专门扫描源代码文件检查花括号是否完整在几百行的函数里发现了一个漏掉的}。那时候我才切实感受到实验课里那个看似简单的栈真的能帮上日常工作的忙。6.2 表达式求值与编译器语法分析中的栈括号匹配只是栈应用的开始。在中缀表达式转后缀表达式的过程里栈也扮演着核心角色遇到左括号入栈遇到右括号则一直弹出运算符直到把左括号也弹出来。这和括号匹配实验的弹出逻辑几乎同构。编译器的语法分析阶段也大量使用栈。函数调用的参数列表、块结构的大括号、数组的方括号本质上都是嵌套语法成分。许多语法分析器在检查语法错误时就是利用“遇到左括号入栈、遇到右括号弹栈校验”这套机制来报告错误位置和类型。所以括号匹配不是一道孤零零的实验题它是后续理解表达式求值、语法分析、JSON 和 XML 校验等一堆内容的基石。把这道题的逻辑吃透后面遇到栈的变形题会感觉非常亲切。6.3 再分享一个实用的扩展小技巧如果你想把这个实验做成一个真正能用的工具可以在栈里不只存字符还同时存行号和列号。这样当程序发现最后一个未匹配左括号时能直接告诉你“第 12 行第 27 列附近有一个{没有被闭合。”实现起来只是在入栈时多压一份位置信息并不复杂但体验感完全不同。我后来写括号检查脚本时就是这么做的。在处理几千行的大型配置文件时它比单纯输出 NO 有用得多因为你能立刻跳到具体行去修问题。数据结构实验的意义就在这里不只是为了通过评测而是让你学会用合适的结构解决真实世界里那些“需要记住顺序”的问题。最后从这次实验中得到的最有用的一句话是不要急着写代码先把“最近一次出现、且还没关闭的东西应该如何记录”想清楚。栈不是课本里一个静态的概念它就是专门用来解决这类“倒序配对”问题的工具。如果你也被括号匹配卡过不妨按我上面的流程完整走一遍手动模拟几个用例、确认逻辑、再提交。一次跑通时的满足感真的比看十遍课件都来得真实。