我在学校带课程实验时见得最多的就是PTA上的“数据结构实验二栈操作与括号匹配判断”。很多同学学栈的时候教材上的代码都能看懂一到PTA上自测就各种过不去要么输出格式不对要么遇到嵌套括号逻辑就乱套。其实括号匹配是栈这个数据结构最经典的应用场景把这个实验吃透后面学表达式求值、函数调用栈、回溯算法都会轻松很多。这篇文章就围绕这个实验从题目拆解、代码实现到PTA提交避坑完整走一遍适合正在学栈、或者在PTA上卡实验二的同学参考。1. 实验背景与核心思路拆解1.1 题目到底要我们做什么先把这个实验题目的本质看清楚。PTA上这类实验题通常的描述是给定一个包含括号的字符串括号一般有三种——圆括号()、方括号[]、花括号{}要求判断字符串中的括号是否全部正确匹配。有的题目还会进一步要求如果不匹配输出第一个出错的位置如果匹配输出“匹配成功”之类的提示。我第一次带学生做这个实验的时候发现很多人没有认真读题直接写了一个“计数器”方案遇到左括号就加一遇到右括号就减一最后看总数是不是零。这个思路对单一类型的括号勉强能判断“数量是否对等”但完全无法处理三种括号的嵌套顺序问题。比如([)]这个字符串三个计数器最终都会归零但括号明显是错误匹配的因为[和)交叉了。所以题目的真实要求是不仅要判断左右括号“数量相等”还要判断“顺序正确、类型匹配”。这就是栈的用武之地——栈的后进先出特性天然契合括号匹配的“最近括号优先配对”规则。如果你还没有理解为什么括号匹配非要用栈只需要记住一句话最后一个出现的左括号必须匹配第一个出现的右括号。这和栈顶元素永远是最后放入的元素是同一件事。1.2 为什么选栈而不是其他数据结构从逻辑上讲括号匹配可以类比成一个“嵌套收纳盒”的场景。你把一个左括号想象成打开一个盒子遇到右括号就是关上最近打开的盒子。箱子是一层层叠起来的你要关的一定是当时最顶层那个还没关的盒子而不是底下的。这就是典型的“后进先出”顺序除了栈没有更合适的数据结构。用数组硬做行不行理论上有办法比如用一个标志数组记录每个括号是否匹配然后循环扫描。但时间复杂度和代码复杂度都会明显上升而且边界情况多。用队列行不行队列是先进先出无法匹配“最近一对”的关系所以不行。用递归行不行递归本质上也是栈的行为但实现起来比显式用栈更绕还容易把栈空间耗尽。所以实验题的标准做法就是自己动手写一个栈然后基于栈完成判断。这里还要提醒一句实验二是“栈操作”的实验所以PTA考察的往往不只是括号匹配算法本身还包括你对栈的基本操作是否熟练——初始化、入栈、出栈、取栈顶、判空、销毁。也就是说代码里你必须自己实现这些栈操作函数不能图省事直接在数组上硬写逻辑。有的同学用C的stack容器几分钟就写完了提交也能过但实验报告里如果写的是“这是STL实现的”分数可能就要打折了。既然实验目的是理解栈最好还是按实验要求手写一遍栈的基本操作再谈优化。2. 栈的表示与基本操作实现2.1 顺序栈和链栈怎么选栈的物理存储结构有两种顺序栈和链栈。PTA实验二这类题目输入字符串的长度通常有限而且我们只需要在括号扫描过程中临时存左括号链栈和顺序栈都能胜任。但作为实验我建议优先写顺序栈原因有三个。第一顺序栈的代码结构更直观数组加栈顶指针一看就懂实验报告也好描述。第二顺序栈的入栈出栈都在表尾操作时间复杂度都是O(1)效率上没有任何问题。第三括号匹配过程中栈内最多只存左括号栈容量设置为输入字符串长度加一就足够几乎不可能溢出用不着链栈那种动态分配的开销。如果你后面做表达式求值那种需要动态扩展的场景再换链栈也不迟。你可以把顺序栈想象成一排固定数量的储物格再加上一个指示器表示“当前最上面的格子是哪一个”。入栈就是往下一个格子里放东西然后把指示器往上移一格出栈就是把指示器往下移一格逻辑上那个格子里的东西就不存在了。#define MAXSIZE 100 typedef struct { char data[MAXSIZE]; int top; } SeqStack; void InitStack(SeqStack *S) { S-top -1; } int Push(SeqStack *S, char c) { if (S-top MAXSIZE - 1) { return 0; // 栈满 } S-top; S-data[S-top] c; return 1; } int Pop(SeqStack *S, char *c) { if (S-top -1) { return 0; // 栈空 } *c S-data[S-top]; S-top--; return 1; } int GetTop(SeqStack *S, char *c) { if (S-top -1) { return 0; } *c S-data[S-top]; return 1; } int IsEmpty(SeqStack *S) { return S-top -1; }注意这里我把top初始化为-1而不是0。两种写法本质一样但top -1时top指向的是栈顶元素的位置入栈时先加一再赋值逻辑更顺top 0则指向的是下一个空闲位置入栈时先赋值再加一。考试或PTA代码里两种都很常见但你最好从头到尾统一不要在同一个实验里混着写否则很容易出现“差一错误”。2.2 栈操作里最容易写错的边界条件栈操作本身不难难的是边界条件。我在批改同学实验代码时发现最常见的错误集中在两个地方。第一个是“栈满”和“栈空”的判断。顺序栈比较容易出现的问题是出栈时没有判断栈是否为空直接对top -1的情况执行top--结果top变成-2下一次判断栈空就失灵了。入栈时没有判断栈是否满如果题目给出了超长字符串数组越界PTA会直接报运行时错误。所以每个栈操作函数务必把空栈、满栈的情况单独处理这是实验二的基本得分点。第二个是“出栈”和“取栈顶”的区别。出栈会改变栈的状态需要把元素从栈里拿出来取栈顶只是看一眼栈顶是什么不改变栈。括号匹配算法里遇到右括号时需要“取栈顶进行比较”确认匹配后再“出栈弹出”。有的同学直接把取栈顶当成出栈来写比较完忘了弹出结果栈里积累了多余的左括号最终判断出错。这两个操作一定要分清。// 取栈顶但不弹出——正确的用法是“先看再弹” char topChar; if (GetTop(S, topChar) IsMatch(topChar, ch)) { Pop(S, topChar); // 匹配成功后弹出 } else { // 不匹配 }顺带补充一个和PTA相关的小细节PTA的题目通常要求输出结尾没有多余空格有的题甚至要求最后的换行符也严格匹配。这些问题与栈逻辑无关却是我见过的最常见的“非技术性丢分”原因。建议每次提交前把输出语句和题目样例逐字符比对一遍不要想当然。3. 括号匹配核心算法与实现3.1 算法流程完整梳理括号匹配的算法流程可以拆成几步我在白板上给同学画过很多次其实核心逻辑非常简单。第一步初始化一个空栈。 第二步从左到右逐个扫描输入字符串的每一个字符。 第三步如果当前字符是左括号(、[、{将其入栈。 第四步如果当前字符是右括号)、]、}先检查栈是否为空。如果栈为空说明“右括号多了”匹配失败如果栈不为空取出栈顶元素和当前右括号进行匹配对比。 第五步如果栈顶左括号与当前右括号类型匹配比如(对应)则弹出栈顶元素继续扫描下一个字符如果不匹配说明字符交叉嵌套或类型不对匹配失败。 第六步字符串扫描结束后检查栈是否为空。如果栈为空说明所有左括号都找到了对应的右括号匹配成功如果栈不为空说明“左括号多了”匹配失败。这个流程里最关键的判断是“右括号来了之后”的三步曲先判空、再取顶、后匹配。判空放在最前面是因为如果栈里已经没有左括号了此时出现右括号无论它是什么类型都一定无法匹配。比如输入())扫描到第三个字符时栈已经空了此时直接判定失败。下面是一个标准的匹配判断函数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(char *str, int len) { SeqStack S; InitStack(S); for (int i 0; i len; i) { char ch str[i]; if (ch ( || ch [ || ch {) { Push(S, ch); } else if (ch ) || ch ] || ch }) { char topChar; if (IsEmpty(S)) { printf(右括号多余位置%d\n, i 1); return 0; } GetTop(S, topChar); if (IsMatch(topChar, ch)) { Pop(S, topChar); } else { printf(括号类型不匹配位置%d\n, i 1); return 0; } } } if (IsEmpty(S)) { printf(匹配成功\n); return 1; } else { printf(左括号多余位置%d\n, S.data[S.top] 1); // 这里的取位置方式需要具体实现 return 0; } }3.2 多种括号嵌套时的判断细节有的同学会问扫描字符串时除了括号还有其他字符怎么办PTA的题目一般分两种情况。一种是不考虑其他字符只对括号进行处理其他字符直接跳过另一种则是把一个完整的表达式作为输入需要区分括号的“左右”和运算符、数字。绝大多数实验二采用第一种方式因为实验名称就是“括号匹配判断”不是“表达式合法性判断”。所以你只需要关心括号字符遇到其他字符直接continue即可。嵌套顺序是另一个容易出问题的点。我们用手写栈实现时天然能保证“栈顶一定是最近出现的左括号”所以只要每次都对栈顶做类型匹配嵌套顺序就自动正确了。真正要注意的是输出错误信息时的“位置”计算。很多PTA题目要求的不是笼统的“匹配失败”而是输出第一个出错位置这个位置通常指的是右括号出现时对应的下标。所以在扫描循环里要保留当前字符的下标值我建议用for计数循环而不是while指针移动这样取下标更方便。还有一种常见场景栈不为空但栈顶元素和当前右括号类型不匹配。例如输入[}扫描到}时栈顶是[类型不匹配。这是“左右类型不一致”要单独输出类型不匹配的信息而不是右括号多余。区分这两种错误类型也是部分PTA题目的得分点。我整理了一个简单的问题对照表方便实验报告里写结论输入特征判定结果说明(())匹配成功正常嵌套()匹配成功孤立的左右括号对也是合法的([)]匹配失败类型不匹配左括号与右括号顺序交叉(()匹配失败左括号多余扫描结束后栈不为空())匹配失败右括号多余出现右括号时栈为空[}匹配失败类型不匹配左括号与右括号类型不对应()视题目要求如果题目说只处理圆括号尖括号应跳过3.3 用生活例子帮助理解算法如果不习惯看代码逻辑我换个方式来解释。想象一下你面前有一摞盘子你要把带有凸起卡扣的盘子和带有凹槽卡扣的盘子配对叠起来。每看到一个左括号就像拿起一个凸扣盘子放在摞上每看到一个右括号就像从摞顶拿起一个盘子看看它是不是能和当前凹扣盘子配对。能配对就叠到一边不能配对就说明这组盘子根本不该在这一对配对。扫描完所有字符后如果摞上还有盘子说明有盘子一直没人来配对。这个例子虽然简单但完美对应算法的每一个步骤摞顶就是栈顶盘子配对就是类型匹配判断最后残留就是左括号多余。想到这个场景写代码就不容易乱了。4. 完整代码设计与PTA提交实战4.1 一份可以直接提交的完整代码下面给出一份能在PTA上直接提交的C语言完整代码。我按“常见的实验二要求”来写输入一行字符串输出“匹配成功”或“匹配失败”的提示信息。如果你在PTA遇到的题目要求输出格式略有不同只需要调整最后几个printf即可核心算法不需要变。#include stdio.h #include string.h #define MAXSIZE 100 typedef struct { char data[MAXSIZE]; int top; } SeqStack; void InitStack(SeqStack *S) { S-top -1; } int Push(SeqStack *S, char c) { if (S-top MAXSIZE - 1) { return 0; } S-top; S-data[S-top] c; return 1; } int Pop(SeqStack *S, char *c) { if (S-top -1) { return 0; } *c S-data[S-top]; S-top--; return 1; } int GetTop(SeqStack *S, char *c) { if (S-top -1) { return 0; } *c S-data[S-top]; return 1; } int IsEmpty(SeqStack *S) { return S-top -1; } int IsLeftBracket(char c) { return c ( || c [ || c {; } int IsRightBracket(char c) { return c ) || c ] || c }; } 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(char *str) { int len strlen(str); SeqStack S; InitStack(S); for (int i 0; i len; i) { char ch str[i]; if (IsLeftBracket(ch)) { Push(S, ch); } else if (IsRightBracket(ch)) { if (IsEmpty(S)) { printf(匹配失败右括号多余位置 %d\n, i 1); return 0; } char topChar; GetTop(S, topChar); if (!IsMatch(topChar, ch)) { printf(匹配失败括号类型不匹配位置 %d\n, i 1); return 0; } Pop(S, topChar); } } if (!IsEmpty(S)) { printf(匹配失败左括号多余\n); return 0; } printf(匹配成功\n); return 1; } int main() { char str[MAXSIZE]; fgets(str, MAXSIZE, stdin); // 去掉字符串末尾的换行符 str[strcspn(str, \n)] \0; CheckBrackets(str); return 0; }这里我建议把IsLeftBracket、IsRightBracket、IsMatch拆成独立函数而不是在主逻辑里一长串if判断。PTA的题目不太管你是否拆分函数但实验报告和后期维护会舒服很多。实际上很多同学实验二“可以做出来但说不清楚”就是因为所有判断都写在一个函数里自己复盘时也找不准逻辑主线。4.2 代码逐段拆解与PTA提交要点先从输入开始说。我用fgets而不是scanf(%s)目的是支持输入字符串中出现空格。PTA的测试用例有时会在括号之间加入空格或者普通字符如果使用scanf读入遇到空格就会截断导致判断结果错误。这是个很容易被忽略的细节。str[strcspn(str, \n)] \0;这行代码的作用是去掉末尾换行。fgets会在读入换行符时把它一起存入字符串如果不处理扫描时会把换行符当作普通字符遍历一遍。虽然换行符既不是左括号也不是右括号会被跳过不影响匹配结果但为了输出和后续处理更干净还是建议去掉。再看主循环。每扫描一个字符先判断是否为左括号这里用了IsLeftBracket函数。注意这个判断要放在右括号判断之前因为左括号的处理方式是入栈右括号的处理方式是出栈二者逻辑完全不同。接着处理右括号时先判空再取顶再匹配再弹出顺序不能乱。PTA提交时需要注意的第二点是内存容量。我的代码把MAXSIZE定义为100。如果题目输入字符串很长这个容量可能不够。保险的做法是把MAXSIZE设成比题目最大长度更大比如1000或者10000。甚至可以动态分配。不过对于实验二这种入门实验100个字符一般够用。如果你不想因为容量问题在PTA上白白丢分可以在定义处直接写一个稍大的值比如10000这样更稳妥。4.3 自测用例与预期输出在提交PTA之前我建议先用下面的测试用例在本地验证一遍确认输出符合预期测试输入预期结果验证点(())匹配成功基本嵌套()[]{}匹配成功并列括号([{}])匹配成功多层嵌套([)]匹配失败括号类型不匹配交叉嵌套(()匹配失败左括号多余左括号数量多())匹配失败右括号多余右括号数量多[}匹配失败括号类型不匹配单对类型不对a(b)c匹配成功非括号字符应跳过这几个用例覆盖了算法的主要分支。我见过有的同学只测试了(())和())两组用例就提交结果被PTA的隐藏用例直接打回。隐藏用例往往就包括([)]这种交叉嵌套以及a(b)c这种混有普通字符的情况。5. 常见问题与PTA提交流程实测5.1 高频报错与排查思路我整理了一下历届同学在PTA上做实验二最常遇到的几个错误按出现频率排序。第一个是“输出格式不对”。PTA的评测核心是输出比对多一个空格、少一个换行、大小写不一致都会判错。比如有的题目要求输出yes和no你输出了YES和NO有的题目要求输出Match succeed!你漏了叹号有的题目要求匹配失败时输出错误位置你的位置从0开始计数而题目要求从1开始。这些都不是算法问题但每次都有一批人中招。解决办法只有一个逐字比对样例输出。第二个是“编译错误”。常见原因包括MAXSIZE宏定义缺失、函数声明顺序不对用了没声明、手贱在seqstack.h里写了windows.h某些PTA编译环境不支持。我建议代码里不要依赖任何平台特有的库只用标准库stdio.h、string.h、stdlib.h这样在任何OJ/PTA环境下都能编译通过。第三个是“运行时错误”。多半是数组越界导致。比如输入字符串长度超过MAXSIZE或者出栈前没有判空导致top越界。这类错误排查方法很简单把输入长度打出来和MAXSIZE对比一下基本就定位了。第四个是“出乎意料的逻辑错误”。比如([)]判断成了匹配成功。这种情况通常是实现时只判断了数量没有做类型匹配或者出栈时机不对匹配判断后忘了弹出栈顶。5.2 本地调试的小技巧PTA自带的在线调试功能有限我用得最多的调试方式是“打印栈内容”。在检查完一个字符后可以用一个临时循环把当前栈里的字符打印出来然后看看到底是哪个环节出了问题。比如我怀疑某一步栈状态不对可以在扫描循环里临时加一段printf(当前字符: %c | 栈: , ch); for (int k 0; k S.top; k) { printf(%c, S.data[k]); } printf(\n);加上这个输出之后把输入([)]跑一遍你会很清晰地看到字符处理到)时栈内是[然后就能确认确实是类型不匹配而不是数量问题。调试完记得删掉这些临时输出不然PTA会因为多余输出而判你格式错误。我个人做实验二调试时还有一个习惯把不同的测试用例写到一个文本文件里用命令行重定向输入工具去跑测试而不是一条条手动敲进终端。比如用a.exe test1.txt这样的方式一次跑完所有用例。这样效率高得多也更容易批量回归。5.3 PTA提交成功之后还要做什么好多同学在PTA上看到“满分通过”就直接关掉页面实验报告随便写两句就交了。但从课程设计的角度这步之后建议继续做三件事。第一尝试用C的STL重写一遍。虽然实验要求手写栈但用std::stack写一遍可以让你直观地看到“手写栈”和“标准库栈”的用法对应关系后面刷题时用STL会非常顺手。对比之后你会发现我的Push对应push我的Pop对应pop我的GetTop对应top我的IsEmpty对应empty。思路完全一致只是API名字不同。第二测试一个更长、更复杂的输入。比如由几百个括号构成的字符串测试一下自己的栈容量是否够用。如果不够用就该思考顺序栈的扩容机制或者换个方向用链栈实现。这个过程相当于把实验从“完成”推向“完善”。第三把代码改写成“输出所有不匹配位置”的版本。PTA实验题一般只要求判断到第一个错误为止但实际文本编辑器中的括号匹配检测往往希望指出所有不匹配的位置方便用户逐个修正。这个扩展思路不复杂但会让你的理解更深一个层次。6. 算法复杂度分析与扩展应用方向6.1 时间复杂度与空间复杂度从算法分析的角度看括号匹配的时间复杂度和空间复杂度都是很容易计算的。扫描阶段每个字符进循环一次时间复杂度是O(n)其中n是字符串长度。在字符入栈和出栈时因为顺序栈的入栈、出栈都是常数时间内完成整个算法最终的时间复杂度是O(n)。空间复杂度方面栈中最多存储所有左括号最坏情况下输入全是左括号此时栈的大小是O(n)所以空间复杂度也是O(n)。这个复杂度意味着用栈做括号匹配是“线性级别”的算法效率非常高。即使输入字符串长度达到几十万、上百万这个算法也能在极短时间内完成。所以完全不需要担心性能问题真正需要担心的是逻辑边界条件。6.2 从括号匹配到更广的栈应用很多同学学完实验二后有一个误解觉得栈只能用来处理带括号的字符串。实际上栈的应用远不止于此。我在课上经常和同学说凡是需要“回溯最近状态”的问题都可以优先考虑栈。一个最直接的扩展是表达式求值。中缀表达式(12)*(34)转后缀表达式、后缀表达式的求值都需要栈。中缀转后缀时栈用于暂存运算符后缀求值时栈用于暂存操作数。这正是实验二之后下一个经典实验“表达式求值”的内容核心思想完全一脉相承。另一个扩展是函数调用的底层机制。程序运行时的函数调用栈本质上就是系统帮你维护的一个大栈。每一次函数调用的返回地址、参数、局部变量都是压入调用栈的“帧”函数返回时弹出一帧。理解实验二的压栈、弹栈对后面理解递归、理解程序运行时的内存布局非常有帮助。还有一个更贴近生活的例子是浏览器的“后退”按钮。你访问页面A再访问B再访问C浏览器会把历史记录压入一个栈每点一次后退就弹出当前页面回到上一个页面。这正是实验二的“栈顶最近匹配”思想在真实产品里的应用。笔试面试里经常考到这类场景题本质都是在考察你有没有真正理解“栈顶操作”的含义。7. 实验报告写作与课程设计衔接建议7.1 实验报告怎么写才不显得空洞实验报告的模板通常包含实验目的、实验内容、算法设计、代码实现、结果分析、实验总结。很多同学不知道“算法设计”怎么写就抄一段代码或者简单画个流程图。其实写得好的算法设计应当包含“数据结构定义”和“核心算法步骤”两部分。数据结构定义部分简要说明你选择了顺序栈以及为什么选择顺序栈而非链栈。这里可以提到括号匹配过程中栈的最大容量不超过字符串长度顺序栈的静态数组即可满足需求且操作简单、效率高。算法步骤部分按“初始化栈、扫描字符串、遇到左括号入栈、遇到右括号先判空再取顶匹配然后弹出、扫描结束后判断栈空”五步来写每步一句话逻辑清晰即可。结果分析部分建议贴出本地调试的测试用例运行截图而不是只写“测试通过”。哪怕是简单罗列测试输入和输出也会让报告显得有据可查。我见过有的同学拿了满分代码实验报告却因为“没有分析过程”被扣分非常可惜。7.2 从实验二到后续实验的思维衔接PTA的数据结构课程实验通常是一脉相承的。实验一做线性表顺序表或链表实验二做栈和队列实验三往往就是二叉树或者图的应用。栈作为“受限的线性表”是第一个对操作做出限制的线性结构它只允许在表尾进行插入和删除操作。理解了实验二你就理解了“操作受限”这四个字的意义。后续实验里栈还会频繁回归。比如二叉树的中序遍历如果不用递归就得用栈模拟系统调用栈图的深度优先搜索也可以借助栈思想来理解。早点把实验二的栈操作写得熟透后面这些实验都会轻松很多。所以我的建议是在实验二上不要满足于“能过PTA”而是要养成“写一个栈操作模块、反复复用”的习惯。把实验二写成一份质量不错的代码后面做表达式求值、背包问题回溯时直接复用会节省大量时间。7.3 一个值得尝试的课后扩展练习如果你学有余力推荐自己加做一个扩展对每一个左括号记录它在原字符串中的下标并在匹配成功时输出“第几个左括号与第几个右括号配对”。这个扩展建立在实验二基础上能让你更深入理解“栈里存的到底是什么”。实现方式也很简单把栈里的data类型从char改成一个结构体结构体里存两个字段——括号类型和原始下标。入栈时不但存(、[、{也存它在原串中的位置出栈时取出结构体输出和当前右括号的配对关系。这个扩展练完之后你会对“什么时候该用char栈、什么时候该用结构体栈”有更实际的判断力。8. 个人经验与复盘总结做了这么多年课程实验指导我发现一个规律实验二这个题目代码篇幅不长但通过率往往并不高。不是因为它难而是因为它考察的细节太多——栈操作的边界条件、类型匹配的判断、输出格式的严谨性任何一块出了问题结果都是零分。这其实是一件好事情因为大学阶段最能锻炼工程习惯的就是这种“逻辑简单但细节要命”的题目。我自己当年做这个实验时也犯过一个很低级的错误把匹配判断写成了“左括号出现次数等于右括号出现次数”结果([)]这种用例直接翻车。后来把栈的图示画出来才彻底理解了为什么要“遇右括号弹栈顶”。之后每次写代码凡是涉及到嵌套、回溯、撤销的问题第一反应就是“这里能不能用栈”这个思维习惯让我在后面刷算法题时收益很大。最后再分享一个使用PTA这类在线评测平台的习惯不要盯着错误的用例发呆而是先构造最小测试用例分步定位。如果匹配失败可以先用单个括号对()测再用嵌套(())测再测交叉([)]每次只加一个变化。这样最多五分钟就能定位到是哪一行逻辑出了问题。比起反复提交等反馈这种方式才是真正提升调试能力的方法。