第一次刷到信息学奥赛一本通1355题的时候我差点被标题带偏。字符串匹配脑子里第一反应是字符串模式匹配KMP、哈希、AC自动机那一套。结果点开题面才发现完全不是那么回事这道题要做的其实是另外一件事判断给定字符串里的括号是否成对出现、嵌套顺序是否正确。也正是因为这题我彻底把“栈”这个数据结构焊死在脑子里了后面再学递归、表达式求值、回溯全都顺风顺水。这道题在信息学奥赛一本通里属于数据结构篇的经典入门题难度不高但它恰好踩中了新手最容易犯的几种错误。很多同学在这里第一次接触stack第一次被“空栈”支配第一次因为一个小边界条件卡一整天。我后来带集训队都会把这题放在“数据结构第一课”里讲效果比单纯背栈的概念好得多。这篇文章我就把这道题从题面、思路、代码到坑位完整拆一遍顺便聊聊从这道题我能延伸出什么更值钱的东西。1. 先把这个题掰开来看它到底考什么1.1 题面解读与隐藏考点1355题的题面描述概括起来是这么一件事输入若干行字符串每一行可能包含普通字符也可能包含三组括号分别是()、[]、{}。程序需要判断这个字符串里的括号是不是合法配对合法输出True不合法输出False。当单独读到一行只有一个英文句点.时整个程序结束。注意两个容易忽略的细节第一这是“多组输入”不是让你只处理一个字符串就结束第二结束符是独立一行的.不是输入里的某个括号。很多新手写这道题时脑子里只有括号忽略了终止条件结果程序一直卡着等输入在本地测试时CtrlZ按半天也没退出还以为自己代码写错了。所谓“括号合法配对”具体说有三个要求左右括号类型要一致左括号出现的顺序要和右括号出现的顺序形成“反序呼应”而且不能有多余的右括号或多余的左括号。下面这个字符串就是经典反例([)]乍一看它有左括号(、[也有对应的右括号)、]数量上似乎“凑齐”了但实际上这是不合法的因为[先于(出现却在(配对完成后才被关闭。用人的直觉感知就是括号“交叉缠绕”了。合法的情况必须是“套娃”式嵌套像([])、{[]}这种。1.2 它和LeetCode 20题“有效的括号”是什么关系如果你刷过力扣看到这题应该会觉得很眼熟。LeetCode第20题“有效的括号”和一本通1355几乎是一个模子刻出来的唯一的区别是LeetCode只给一个字符串一本通给了多组数据并且多了一个.结束符。所以我一直觉得信息学奥赛一本通的题序是有讲究的把多组输入这个环节和栈的基础操作捆在一起就是要你从第一道应用题开始就养成“读入循环”的习惯。很多人在LeetCode上把函数写对了可一到OJ上面临完整程序的输入输出就不知道怎么组织代码。1355题恰好补上这个短板。这个题按难度分应该属于普及组入门偏上的水平适合刚学完数组、准备接触“非线性的数据结构”的人。它能帮你搞清楚的底层问题是栈这个结构到底为了解决什么而存在为什么括号匹配天然适合用栈搞清楚这两点比AC本身值钱得多。2. 代码实现之前把匹配逻辑先理成一条线2.1 括号合法性的本质先遇到的最后匹配我希望你先忘掉代码想象一个场景你面前有一摞盘子每次只能从最上面拿一个也只能往最上面放一个。现在你按顺序往盘子上写左括号和右括号左括号相当于“放一个盘子上去”右括号相当于“从顶上拿走一个盘子”。如果要拿走一个和之前左括号配对的那个盘子就必须先把压在它上面的所有盘子都拿走。这就是栈的核心思想也是括号匹配的本质先出现的左括号反而要等后面所有的嵌套都处理完才能被匹配后出现的左括号会先被匹配。这种“先进后出”的顺序和栈的行为完全一致。用生活化的说法就是最早打开的柜子最后才能关上。明白这个逻辑我们就能把“判断合法性”转化为三个极其机械的判断步骤。每读到一个字符只做三件事之一。2.2 三种非法情况的对照表为了不让自己在代码里东改西改我建议先把“非法”情况枚举清楚。括号匹配的非法情形无非下面三类类型示例问题描述程序里怎么发现右括号提前出现()写成()中间的)先来或者直接)(某个右括号出现时前面没有等待匹配的左括号栈为空却遇到了右括号左右括号类型不匹配(]、[)、{)栈顶左括号与当前右括号不是同一组栈顶是(当前却是]左括号有多余({[]}()全部扫描完后栈里还残留未匹配的左括号循环结束后栈不为空这张表就是调试时的检查清单。代码写完之后别急着提交先把这三类情况都构造一两个测试用例跑一遍。能全部通过的大概率就稳了。2.3 为什么不能用“计数器”代替栈很多新手会想我干嘛要开一个栈我直接用三个计数器分别数左括号和右括号左右数量相等不就匹配了吗这个想法错得非常典型我每次讲这个题都会专门拿出来说。我们拿([)]举例。三个计数器统计(出现1次)出现1次[出现1次]出现1次数量全部相等看起来“左右成对”。但这个字符串是不合法的因为括号交叉了。计数器能统计数量统计不了顺序。所以核心结论是括号匹配这个问题的信息量除了“有哪些括号”还包含“这些括号出现的先后顺序”。顺序信息必须用一个线性结构暂时“记住”而这个结构天然就是栈。因为我们需要记住的正是“最晚出现、最该优先处理”的那一批左括号。3. 完整实现与边界处理从伪代码到可提交代码3.1 多组输入怎么读cin还是getline先解决最容易卡住的输入问题。题面说“字符串中可能包含普通字符”但这个题里的普通字符一般不会包含空格因为OJ的字符串题默认以空格作为分段符如果题目想让你读“带空格的字符串”会明确用getline或者特殊说明。1355题没有说字符串会带空格所以直接用cin s是安全的它会自动把每行字符串按空白字符切分读取。如果你不放心可以用getline(cin, s)按整行读取代码也不复杂区别只是读入后要记得手动清理可能存在的\r换行符。一般来说用cin s就够了因为单行结束符.本身也是一个不含空格的字符串。接下来是终止条件while (cin s) { if (s .) break; // 处理当前字符串 }这样写的好处是读到文件末尾自动退出读到.按题意退出双重保险。千万不能在循环里写死while (true)而忘了手动break。3.2 手写栈还是STL stack本节的代码我用的是“字符数组模拟栈”没有直接用std::stack。不是因为它多高级而是因为信息学奥赛的环境里手写数组栈更透明、更快也方便你在debug时直接打印栈内存。你用std::stack当然也能AC我后面会放STL版本但建议你至少手写一遍把栈底、栈顶的概念彻底吃透。整段代码如下#include bits/stdc.h using namespace std; char st[1005]; // 模拟栈存等待匹配的左括号 int top; char leftOf(char c) { if (c )) return (; if (c ]) return [; if (c }) return {; return \0; } bool isLeft(char c) { return c ( || c [ || c {; } bool isRight(char c) { return c ) || c ] || c }; } int main() { ios::sync_with_stdio(false); cin.tie(0); string s; while (cin s) { if (s .) break; top -1; // 每次新字符串都要清空栈 bool ok true; // 标记当前字符串是否合法 for (char ch : s) { if (isLeft(ch)) { st[top] ch; } else if (isRight(ch)) { if (top -1) { // 栈空右括号多余 ok false; break; } char expectLeft leftOf(ch); if (st[top] ! expectLeft) { // 栈顶左括号和当前右括号不配对 ok false; break; } top--; // 配对成功弹出栈顶 } // 普通字符直接忽略 } // 循环结束后还要检查栈是否清空防止左括号多余 if (top ! -1) ok false; cout (ok ? True : False) \n; } return 0; }leftOf函数是这段代码的“桥梁”给定右括号返回它对应的左括号。这样我们只需要比较st[top]和expectLeft是否相等即可不需要写四五个if-else去特判也不容易写漏。3.3 核心循环里的三个分支我拆解一下主循环里的逻辑遇到左括号(、[、{无脑压栈。因为不管后面是什么它都得“先挂着”等对应的右括号来认领。遇到右括号)、]、}先检查栈是否为空。若为空说明这个右括号是多余的比如()后面又跟了一个)那直接判定非法跳出循环。如果栈顶左括号能和当前右括号配对就弹出栈顶不能配对直接非法。遇到其他字符全部忽略它们不参与匹配属于“路人甲”。这里有一个容易被忽略的点一旦中间某个字符导致ok false我们是直接break跳出循环的但此时还没读完整个字符串栈里也可能还有残留。那么后续的if (top ! -1)判断会不会造成误判不会因为ok已经是false了输出结果不会因为栈空不空而改变。这个break的真正目的是节省时间既然已经知道错了就不用再看剩下的字符了。3.4 最终判定循环结束不等于匹配成功很多第一次写这题的人在主循环里判断得很起劲右括号对不上就false可最后忘记检查栈里是否还有剩余左括号。看下面的字符串({[]}扫描过程非常顺利(入栈{入栈[入栈]到来弹出[}到来弹出{。循环结束时栈顶还有(没有被弹出。如果只看循环里的逻辑就会错误地输出True。所以最后那一句if (top ! -1) ok false;必不可少。这个“收尾检查”对应的是“左括号多余”这一类非法情况和循环中“栈空遇右括号”恰好是对称的两个边界。4. 实战踩坑记录这些细节才是WA的元凶4.1 空栈访问最经典的崩溃现场我在第一次用STL stack写这题时写的是类似下面的代码if (!st.empty() st.top() expectLeft) { st.pop(); } else { ok false; break; }因为加了!st.empty()判断侥幸没出事。但很多初学者会直接写成if (st.top() expectLeft) { ... }一旦字符串以右括号开头比如输入)(此时栈是空的访问st.top()就是访问不存在的元素轻则得到未定义的结果重则直接运行时错误。手写数组栈也一样top -1时访问st[top]就是越界访问。调试这种错误时经验是只要程序出现异常退出、但本地IDE编译没有报错多半是数组越界或者访问了非法内存。先检查所有栈操作处是否做好了“栈空”判断别急着改算法。4.2 把“匹配”写成“相等”的ASCII陷阱还有一次一个学生拿着代码问我为什么全WA我一看他写的是if (st[top] ch) ...这里ch是右括号st[top]是左括号(和)的ASCII码一个是40一个是41永远不可能相等。这个错误非常隐蔽因为代码逻辑看起来“很顺”——“匹配”不就是“相等”嘛。在ASCII编码中三组括号的码值分别是左括号ASCII右括号ASCII(40)41[91]93{123}125它们的差值并不统一所以不能靠“左右括号的ASCII码差某个固定值”来判断匹配。正确做法就是写match函数或者像我的代码一样用leftOf把右括号映射到左括号再比较两个左括号是否相等。4.3 忘记重置栈顶的“多组输入连环坑”这个坑我踩得印象极深。第一组数据跑完栈顶top停在某个位置如果没有在循环开头把top重置为-1第二组数据就会在一个“脏栈”上继续操作。举个例子第一组是()处理完top恰好回到-1看起来没事第一组是((处理完top 1第二组如果是)那左括号就被错误地“继承”了导致下一组数据结果错乱。这提醒我们一组数据的生命周期是独立的。每读入一个string都要重新初始化top -1和ok true。同理用STL stack时要在循环内新建一个stackchar st;或者每次把旧栈clear掉。4.4 自己动手造一组暴力测试用例我把这道题常用的自查用例整理成了一张表。提交前至少跑一遍能过滤掉90%的WA。输入字符串期望输出考察点([])True正常嵌套([)]False交叉嵌套不合法(())True多层嵌套((False左括号过多))False右括号过多ab(c)dTrue普通字符被忽略空串直接读入一行空True没有括号时应当合法空串这个用例我早期完全没考虑过。cin s读入一个空字符串时循环体不执行top保持-1输出True逻辑上是正确的。这说明只要代码的初始化和收尾判断都正确边界情况就会自动被兜住。5. 把栈这招吃透之后还能往哪儿走5.1 下一站中缀表达式求值一本通后面紧跟着的表达式求值、后缀表达式题原理和1355是同一套东西只是栈里存的不再是左括号而是数字和运算符。中缀转后缀的经典算法“调度场算法”本质上就是利用栈把运算符的优先级和括号的嵌套关系统一处理。你已经知道了左括号要压栈、遇到右括号要弹栈那么真正理解“栈里存的不只是字符而是‘还没轮到的任务’”这个概念会比别人快很多。括号匹配是理解“栈顶是最近未完成事务”的最佳样本。5.2 递归与栈是同一件事很多初学者在学递归时对“栈帧”“调用栈”这些概念一头雾水。实际上程序执行递归函数时系统会在内存里维护一个栈每次调用就压入一个栈帧每次return就弹出一个栈帧。所谓“递归转迭代”很多时候就是自己手动维护一个栈来模拟系统栈。这道1355题虽然简单但它已经在强迫你做一件和系统栈一模一样的事把还没处理完的左括号压栈处理完再弹出来。练多了之后你再看递归函数就不会觉得它是“黑魔法”了。5.3 手写栈和STL stack到底怎么选我的建议分两个场景竞赛场景默认手写数组栈。速度快元素访问直观调试时可以任意打印栈内全部内容一旦用std::stack栈内元素只能从头到尾访问调试相对麻烦。工程场景或者注重代码可读性的场景用std::stack有自动内存管理、异常安全代码意图更清晰。STL版本写起来也很简洁核心逻辑不变#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); string s; while (cin s) { if (s .) break; stackchar st; bool ok true; for (char ch : s) { if (ch ( || ch [ || ch {) { st.push(ch); } else if (ch ) || ch ] || ch }) { if (st.empty()) { ok false; break; } char expected (ch )) ? ( : (ch ]) ? [ : {; if (st.top() ! expected) { ok false; break; } st.pop(); } } if (!st.empty()) ok false; cout (ok ? True : False) \n; } return 0; }如果你在考试中只能记住一种写法我建议记住手写数组栈因为它把“栈是数组加一个游标”这个本质暴露得很彻底一旦忘了STL的API也不至于写不出来。5.4 多刷一步用这题练“读题”和“Debug”我最后想说的是这题更大的价值反而不在栈本身而在“防坑”能力。信息学竞赛里WA不是最可怕的可怕的是你不知道为什么WA。1355题坑位集中错误类型丰富非常适合拿来当debug练习题。我教新人的时候会让他们故意把代码改成有bug的版本然后给同学互相查看谁先找出问题。这种做法虽然笨但在入门阶段极其有效你亲手犯过一次top-1没重置的错以后所有涉及多组输入的题都会多留一个心眼。我个人在实际操作中的体会是刷这题千万不要只在编译器里跑一遍样例就提交OJ上WA了也别急着看题解先把上面那张测试用例表跑一遍。我的新学生用这个方法自查80%的情况自己能找出问题剩下20%基本都在“栈空”和“重置”这两个点上。把1355吃透再回头看那些动辄“栈溢出”的递归题你会发现所谓理解数据结构就是面对一个新问题能迅速说出“这个东西的天然处理工具是什么”。1355题给我的正是这个能力。