信息学奥赛一本通1355题我当年刷栈专题时印象很深。题目全名叫“字符串匹配问题”猛一看以为是KMP或者字符串哈希点进去才发现挂的标签是栈stack考的是一道非常经典的括号匹配题给你一个字符串里面有()、[]、{}三种括号让你判断这些括号是否成对匹配、嵌套是否合法。这篇文章不打算替你念一遍题解我想按自己做题时的真实思考顺序把这道题为什么用栈、代码怎么写、有哪些容易挂的边界一次讲透。不管你是刚开始学信息学奥赛的新手还是已经刷到提高篇想巩固栈的选手这题都值得认真过一遍。1. 题目到底在考什么栈的“后进先出”与括号配对的天然对应1.1 一句话看懂1355题题面大意输入一个字符串里面可能包含字母、数字以及()、[]、{}三种括号判断其中的括号是否匹配匹配输出 YES否则输出 NO。这里说的“匹配”不只是左括号和右括号数量相等还包括两个层面第一每个右括号必须和“最近的未匹配的左括号”类型一致第二如果题面带着“括号互相包含时从内层到外层必须是()、[]、{}”这样的优先级约束那么嵌套顺序也得合法。很多初学者看到“字符串匹配”四个字第一反应是 KMP、字典树、字符串哈希这些高级玩意实际这题和它们没有半点关系。它就是一道最典型的栈应用题考察对“后进先出”的理解。你只要想明白一个问题就够了当扫描到右括号时应该找哪个左括号去配对1.2 为什么括号匹配天生适合用栈我习惯用手动模拟来理解算法。拿{[()]}这个字符串举例从左往右逐字符读读到{这是左括号先放着读到[也是左括号先放着读到(还是左括号先放着读到)现在需要找一个左括号和它配对。找哪个显然是最新放下的(不是最早放下的{。问题来了程序怎么知道“最新放下的左括号”是哪个这正好是栈的天职。栈的后进先出LIFO特性让最后 push 进去的元素永远在栈顶于是“最近未匹配的左括号”就是栈顶。配对成功后把栈顶 pop 掉下一个“最近未匹配的左括号”又浮到栈顶。这个逻辑和现实中的套娃一模一样最里面的娃娃最后塞进去却要最先拿出来。或者你想成编辑器的撤销操作也行最后一次操作最先被撤销。括号匹配就是这种“最内层先闭合”的结构栈和它完全同构。如果不用栈你只能用一个变量记录“当前最内层左括号是谁”遇到嵌套层次变浅还要回退代码会变得又丑又容易错。而用栈push 就是进入一层pop 就是退出一层思路非常干净。1.3 三种括号并存时栈顶才是唯一的“当前裁判”如果字符串里只有小括号确实可以靠一个计数器解决遇到(加一遇到)减一最后判断是否为零。但本题有三种括号计数法立刻失效——因为某个右括号出现时你根本不知道它应该匹配哪种左括号。以经典反例([)]为例遇到(入栈遇到[入栈遇到)时栈顶是[[和)不配对直接判非法。你可能觉得(和)明明是一对为什么不能匹配问题在于它们中间插了一个[导致)无法和“当前最内层的左括号”配对。这就是括号匹配里的“顺序错误”。多括号匹配必须维护一个信息当前最内层未匹配的左括号是谁。这个信息只能存在栈顶。每当一个右括号到来只有栈顶有资格和它“对线”这也就是为什么我把栈顶称为“当前裁判”。时间复杂度 O(n)空间复杂度最坏 O(n)n 是字符串长度。2. 先别急着写代码优先级规则的两个常见版本2.1 版本A只要求左右括号类型一致很多学校OJ上这道题其实只考最基础的栈应用遇到左括号压栈遇到右括号先看栈空不空再和栈顶比对类型配对成功就弹栈最后看栈是否为空。在这个版本里([])这类输入是合法的(和)配对[和]配对各自都成功。它只要求“左右类型一致”和“先左后右”不额外限制嵌套顺序。代码结构大概是if (c ( || c [ || c {) { st.push(c); } else if (c ) || c ] || c }) { if (st.empty() || !match(st.top(), c)) { ok false; break; } st.pop(); }这也是 LeetCode 第20题“有效的括号”的标准解法。如果你做题时确认题面里没有那句“从内层到外层必须是()、[]、{}”用版本A就够了。2.2 版本B嵌套时内层括号必须“更小”但如果你打开一本通1355原题很多题面或题解里会出现这句话如果括号有互相包含的形式从内层到外层必须是()、[]、{}。这句话是什么意思通俗说就是小括号应该出现在最里层中括号在中间一层大括号在最外层。反过来([])这种“外层小括号、内层中括号”的顺序就不合法。于是需要给三种括号定义一个优先级我习惯这样定(的优先级是 1[的优先级是 2{的优先级是 3。入栈一个左括号之前先看栈顶。新来的左括号会位于当前栈顶的“更里面”它的优先级如果比栈顶还高说明出现了“外层小括号、内层中括号”这种错误的从外到内顺序直接失败。写成代码就是if (!st.empty() level(c) level(st.top())) { ok false; break; }为什么允许相等优先级为了支持同类型括号的多层嵌套。比如(())或[[()]]两对小括号或两对中括号套在一起时优先级都是相等的这种嵌套完全合法。2.3 版本差异会导致同一串数据的不同结果版本A和版本B并不是等价的最典型的差异就是([])版本A认为 YES版本B认为 NO。我列了几个典型输入方便你对拍输入串版本A纯配对版本B含优先级{[()]}YESYES[()]YESYES([])YESNO([{}])YESNO([)]NONO(()NONO)()NONO所以做题前一定要先确认题面到底有没有优先级约束。我下面给的完整代码是版本B如果你确认自己的OJ不需要优先级把那两行 level 判断删掉就变回版本A。别盲目照搬网上题解很多题解互相抄题面版本都不一样。3. 完整C实现从入栈到出栈的每一步3.1 数据结构与辅助函数为什么用 stack我用 STL 的stackchar原因很简单一个括号字符在栈里只存char就够了不需要额外信息而stack的push、pop、top都是 O(1)。这题的字符量级很小STL 完全够用。除了栈本身还需要两个辅助函数level(c)返回左括号的优先级非左括号返回 0match(left, right)判断左右括号是否类型一致。如果你不习惯 STL或者想省掉头文件依赖也可以用数组模拟栈核心写法是char st[300]; int top 0; // 入栈st[top] c; // 出栈top--; // 栈顶st[top - 1]; // 判断栈空top 0;原理和 STL 完全一样只是手动管理下标。竞赛里两种都常见用哪个看你顺手。3.2 主循环逻辑左括号入栈、右括号出栈、其他字符跳过对字符串从左到右扫描每个字符只可能是三种情况遇到左括号(、[、{按版本B判断优先级再入栈遇到右括号)、]、}先判断栈是否为空再判断栈顶是否与它匹配匹配就 pop否则失败遇到其他字符直接跳过不参与匹配。这里有一个非常容易踩坑的顺序问题右括号分支里必须先判空再取栈顶。如果写成先取栈顶再判空遇到右括号开头的字符串就会访问到并不存在的栈顶元素轻则逻辑错误重则直接崩溃。代码里我用if (st.empty() || !match(st.top(), c))利用||的短路特性栈空时根本不会执行后面的match。3.3 多组输入写法while(getline(cin,s)) 的边界一本通这类题库输入通常是一行一个字符串可能有多个测试数据一直读到 EOF 结束。最稳的写法是string s; while (getline(cin, s)) { if (s.empty()) continue; // 处理 s }用getline而不是cin s是为了兼容字符串里万一出现空格的情况。如果题目保证没有空格用while (cin s)也没问题但getline更通用。空行要跳过不然会多输出一组 YES。3.4 完整代码下面这段是按版本B含优先级规则写的完整代码#include bits/stdc.h using namespace std; int level(char c) { if (c () return 1; if (c [) return 2; if (c {) return 3; return 0; } bool match(char left, char right) { return (left ( right )) || (left [ right ]) || (left { right }); } int main() { string s; while (getline(cin, s)) { if (s.empty()) continue; stackchar st; bool ok true; for (char c : s) { if (c ( || c [ || c {) { // 版本B的优先级判断确认题面不需要时直接删掉这两行 if (!st.empty() level(c) level(st.top())) { ok false; break; } st.push(c); } else if (c ) || c ] || c }) { if (st.empty() || !match(st.top(), c)) { ok false; break; } st.pop(); } } if (!st.empty()) ok false; cout (ok ? YES : NO) endl; } return 0; }如果你确认题目是版本A只需要把入栈前的if (!st.empty() level(c) level(st.top()))这两行删掉。保留优先级判断的代码在版本A的数据上会误判([])这类输入所以这个选择一定要和题面对齐。4. 边界条件与易错点排查AC与WA往往只差一行4.1 扫描完字符串后栈非空最容易踩的坑扫描过程中一路都很顺利没有出现任何明显的不匹配但字符串结束时栈里还剩着左括号。比如(()或者([()]前面都配对着最后却多出一个左括号。这时候必须判非法因为左括号数量比右括号多最后没有右括号来收尾。处理方式就是在整个循环结束后判断if (!st.empty()) ok false;。很多初学者漏掉这一步明明多了一个(还是输出 YES白白 WA 一次。4.2 右括号来了但栈空反过来以右括号开头的字符串比如)(、]abc[第一个字符就遇上了空栈。这时候没有任何左括号可以配对直接失败。代码里我写的是if (st.empty() || !match(st.top(), c))一个条件同时覆盖“栈空”和“栈顶不匹配”两种情况靠||的短路特性保证安全。这是我写括号题的习惯右括号分支第一步永远是查空宁可多写一次判断也别在栈空时访问top()。4.3 非括号字符的处理题目里字符串往往不只是括号还夹杂字母比如(abc[def]{ghi})。处理方式很简单不处理。遇到非括号字符就跳过它既不入栈也不弹栈。这里有一个很隐蔽的坑千万不要把字母、数字也 push 进栈。一旦入栈右括号匹配时栈顶就是字母match永远返回 false整个字符串直接判非法。如果你发现自己程序老是对带字母的样例输出 NO先检查是不是多写了一个else { st.push(c); }。4.4 空行与EOF多组数据的题还有一层隐藏陷阱评测数据里如果有空行getline会读到一个空串空串的“括号匹配结果”按代码会输出 YES导致输出多一行。所以前面那句if (s.empty()) continue;一定要加。另外while (getline(cin, s))读到 EOF 时自动退出循环不需要手动break。如果你改成单组输入的写法记得只处理一次就结束别把循环留成死等待。5. 从1355题延伸一旦看懂栈这些题就是同一种题5.1 中缀表达式求值与括号配对学完1355再去看中缀表达式转后缀、表达式求值会发现套路几乎一样。表达式里的括号让运算符优先级发生跳变遇到左括号就把当前状态压栈遇到右括号再弹栈恢复。1355练熟之后再看求值代码里那堆stackint和stackchar至少不会一头雾水。5.2 括号生成从“验证”到“构造”LeetCode 第22题要求生成 n 对括号的所有合法串它和“验证括号串”是同一个知识点的两面。合法串的充要条件是任意前缀中左括号数量不小于右括号数量最终左右数量相等。这和栈匹配的规则本质一致——右括号比左括号多栈会提前空左括号比右括号多栈结束时会非空。做生成题时用 DFS 维护两个计数规则正好可以和栈判定的逻辑互相印证。我觉得这是很好的进阶练习先做几道验证题再做几道构造题对括号模型的理解会完全不一样。5.3 从“是否合法”到“哪里不合法”1355只输出 YES/NO属于判断题。如果题目再进一步要你输出第一个非法位置或者求最长有效括号子串的长度栈仍然是主力工具只是栈里存的不再是字符而是下标。入栈时把下标 push 进去出栈时用当前下标和栈里存的下标相减就能算出配对区间长度。LeetCode 第32题“最长有效括号”就是这么做的。甚至写 HTML 解析器时标签配对也是同一套思想遇到div入栈遇到/div比对栈顶标签名。栈这种“最近未匹配元素”的模型应用面比我最初学的时候想得广得多。我个人刷栈专题时有个习惯每写一道括号题先把三种必挂场景贴在注释里——右括号来时栈空、字符串扫完栈非空、最近的左括号类型不匹配。写完代码照这三条自查一遍WA 率能降一半。1355这道题虽然简单但它是我理解“栈顶即最近未匹配元素”这个模型最好的入口把这个模型刻进脑子里后面的表达式求值、浏览器标签解析、DFS回溯都会轻松很多。