洛谷 B2165 括号匹配我印象里是很多新手第一次接触“栈”这道坎。题目本身只有十几行代码但 AC 率和改错难度一点也不低因为很多人根本没弄懂它到底在考什么直接凭感觉写了个计数器就交了。这篇东西我就把这道题的考点、原理、实现和容易踩的坑一次说清楚尤其会解释为什么“数括号数量”这种直觉做法在这里必挂。1. 题目表面是字符串题实际上考的是“顺序合法”1.1 题面到底给出了什么限制B2165 的输入是一行只包含(、)、[、]四种字符的字符串你要判断这串括号是否匹配输出Yes或No。听起来简单但“匹配”两个字很容易被理解成“左括号和右括号数量一样”。我见过不少第一次做这题的人第一版代码就是四个计数器分别统计(、)、[、]数量相同就输出 Yes。这个思路在只看样例()的时候确实成立但只要稍微换几个用例就会翻车。比如字符串)(它有一个左括号和一个右括号数量完全相等可它显然不合法。因为第一个字符就是右括号它前面没有任何左括号可以和它配对。再比如样例里的([)]左右括号各两个数量也凑齐了可它依旧不合法。原因其实不复杂这串里第 3 个字符是)它想关闭小括号但当前“还没关闭”的括号里最近一个是[而不是(。也就是说([)]的嵌套关系是交叉的括号必须遵循“先开后关、后开先关”的次序不能跳着关。1.2 合法括号串的递归定义大学数据结构教材里通常会给一个递归定义空串是合法括号串如果 A 是合法括号串那么(A)和[A]也是合法括号串如果 A、B 都是合法括号串那么 AB 也是合法括号串。这个定义翻译成人话就是每个右括号必须和它前面最近一个还没有被配对的同类型左括号配对而且配对过程不能交叉。([)]之所以不合法是因为)想和它前面的(配对但中间还夹着一个未关闭的[。你必须在关闭[之后才有资格去关闭更外层的(一旦夹层存在就已经交叉了。这个递归定义还有一个隐藏结论合法括号串天然地呈现出嵌套结构。最内层的括号总是最早被关闭最外层的括号总是最后被关闭。换句话说“后打开的括号先关闭”这不就是栈吗栈的英文叫 stack一种只能在一端进出先进后出的结构。括号问题的所有解法本质都是在模拟这个“后进先出”的语义。1.3 为什么计数法没救有的读者可能会反驳我见过有的字符串题也判断括号用个计数器就过了。那类题通常有额外限制比如只有一种括号、且输入保证所有左括号都出现在右括号之前。而 B2165 同时出现两种括号顺序又是任意给的计数器根本表达不了“谁还没被关闭”“最近未关闭的是哪个”这两条关键信息。举一个更极端的例子([]]。从数量看小括号一对、中括号一对完美。但从语义看扫描到第 3 个字符]的时候当前未曾关闭的左括号有(和[最近的是[所以]可以关闭栈顶的[弹掉以后栈里剩下(。接着第 4 个字符又是]此时栈顶是(]和(类型不匹配失败。计数器完全看不出这个流程只有能记录“最近打开的括号是谁”的数据结构才能办到。这正是栈存在的价值。2. 先想明白“盒子模型”再写代码2.1 把扫描过程想象成往盒子里放东西我讲栈的时候喜欢用一个类比你手里有一个只能从顶部放东西和取东西的盒子现在要把括号串从左到右处理一遍。见到左括号就把它放进盒子见到右括号就看看盒子最上面那个左括号和它是不是一对是就拿走不是或者盒子已经空了那整串就废了。以[()]为例扫描到[放入盒子盒子内容是[扫描到(再放入盒子盒子内容是[ (注意栈底是[栈顶是(扫描到)盒子顶部正好是(类型匹配取出盒子变回[扫描到]盒子顶部正好是[类型匹配取出盒子空最终盒子是空的说明每个左括号都找到了自己的右括号输出 Yes。这个过程中后放进去的(反而先被取走先放进去的[后被取走这正是“后进先出”。再看经典的失败样例([)](入盒栈([入盒栈( [)来了但栈顶是[小括号并没有配对成功失败从这张状态图可以直观看到非法不是到底才发现的而是扫描到第 3 个字符就足以否决整串。这也是栈算法的一大特点大多数非法情况可以提前终止不需要看完整个输入。2.2 为什么只能看“栈顶”不能随便配也许有人会问既然我知道)对应的是(为什么不能从盒子中间把它取出来因为括号串的嵌套规则不允许交叉。如果我允许任意配对([)]就会被错误判定为合法让)配(让]配[数量对、类型也对看起来没问题。但合法的括号结构里内层必须完全被外层包裹不能一个括号只关一半。所以当前右括号能配对的左括号只能是所有未配对左括号中“最新”的那个也就是栈顶。你永远看不到栈中间的更早元素不是实现上的限制而是这个问题本身的逻辑约束。2.3 这题用栈的时间复杂度因为每个字符只会被处理一次要么压栈要么弹栈要么直接推出结论所以时间复杂度是 O(n)空间复杂度最坏 O(n)。最坏情况是什么整个串全是左括号比如((((((所有字符都会压进栈栈的深度等于字符串长度。这题输入规模对 OJ 来说并不大用标准库std::stack和用定长数组模拟栈都能轻松通过。真正影响成绩的从来不是性能而是边界条件的正确性。3. 主循环的三条规则和“结束后检查”3.1 扫描时的决策表把整套判断逻辑做成一张表写代码前先对照它会少踩很多坑当前字符当前栈状态操作结论(或[任意压入栈继续扫描)或]栈为空无法配对输出 No结束)或]栈顶是同类型左括号弹出栈顶继续扫描)或]栈顶是不同类型左括号类型不匹配输出 No结束所有字符处理完栈不为空有左括号剩余输出 No所有字符处理完栈为空全部配对输出 Yes这张表里最容易忽略的是最后一行扫描结束后栈里可能还残留左括号。比如输入((整个过程没有任何右括号来弹栈循环顺利跑完但显然不是合法括号串。所以必须在全部处理完之后额外检查一次栈是否为空把(!stack.empty())当成失败条件写上。3.2 伪代码版本用伪代码表达主循环读入字符串 s 初始化空栈 st 初始化 ok true for c in s: if c 是左括号: 把 c 压入 st else: if st 为空: ok false break top st 的栈顶 if (c ) 且 top () 或 (c ] 且 top [): 弹出 st else: ok false break if st 不为空: ok false 输出 ok ? Yes : No注意“右括号时先判栈空”这一步。很多初学代码直接写成if (c )) { if (st.top() () ... }一旦字符串以右括号开头st.top()会访问空栈的栈顶程序直接崩溃或者行为未定义。在 OJ 上表现就是 Runtime Error 或者神秘的 Wrong Answer。3.3 为什么必须在循环里 break 而不是 continue当发现一个右括号已经无法配对时后续字符即使看起来“正常”也不能改变整串非法的结论。比如)(第一个)就栈空按理说已经否了如果继续扫第二个(并把它入栈循环结束栈非空结果还是 No好像也能过。但如果输入是)()呢继续扫到(入栈、)弹栈循环结束栈为空如果不在出错时 break就可能错误输出 Yes。所以一旦判定失败立刻 break 或者直接return 0都行不要让后续字符有机会“救”回来。4. 三种实现方式对比标准库、数组栈、Python4.1 标准库 std::stack 版本直接上代码#include bits/stdc.h using namespace std; int main() { string s; cin s; stackchar st; bool ok true; for (char c : s) { if (c ( || c [) { st.push(c); } else { if (st.empty()) { ok false; break; } char top st.top(); if ((c ) top () || (c ] top [)) { st.pop(); } else { ok false; break; } } } if (!st.empty()) ok false; cout (ok ? Yes : No) \n; return 0; }使用#include bits/stdc.h是竞赛圈的惯例省去写多个头文件的麻烦洛谷是支持这个头文件的。如果你不喜欢这种写法也可以只包含iostream、stack和string。核心逻辑没有差别。4.2 字符数组模拟栈版本我早年刷题时不太喜欢泛滥的容器分配也更喜欢感知到底层内存怎么走所以会用定长数组模拟栈。这里给出一个版本#include bits/stdc.h using namespace std; int main() { string s; cin s; char st[1000005]; int top 0; bool ok true; for (char c : s) { if (c ( || c [) { st[top] c; } else { if (top 0) { ok false; break; } if ((c ) st[top] () || (c ] st[top] [)) { top--; } else { ok false; break; } } } if (top ! 0) ok false; cout (ok ? Yes : No) \n; return 0; }这里top表示栈中元素个数也相当于是下一个可写入位置减一。遇到左括号就把top加 1然后写入遇到匹配的右括号就把top减 1。这样栈底在st[1]栈顶在st[top]。如果你习惯从 0 开始可以把st[top]作为入栈操作但出栈判断时要记得对应改成top - 1两种写法都行关键是前后保持一致。字符数组大小我直接开了 1000005足以覆盖常见数据范围。4.3 一种我不推荐的简写网上有人把代码压缩成“遇到右括号就弹栈弹之前看看栈顶类型”的写法if (c ) || c ]) { if (!st.empty()) st.pop(); }这个版本在输入([)]时会输出什么它先压(再压[遇到)直接弹掉栈顶[遇到]再弹掉(最后栈空输出 Yes。显然错误。弹栈之前必须判断“类型是否匹配”这是本题的核心不能省。你压入栈的内容不只是“一个左括号”还包含了它的类型信息弹出时要把这个信息和右括号比对否则栈就和计数器没有区别了。4.4 Python 参考写法现在很多同学也会用 Python 交题我把完整实现也贴出来s input().strip() st [] ok True for c in s: if c in ([: st.append(c) else: if not st: ok False break top st[-1] if (c ) and top () or (c ] and top [): st.pop() else: ok False break if st: ok False print(Yes if ok else No)Python 的列表天然支持append和pop()就是很好的栈。要注意s input().strip()是为了去掉行尾换行符和可能的首尾空白。因为原题输入只含括号字符不会有空格strip()之后不会误删括号。5. 边界情况、输入读法和提交时的常见病5.1 必测的边界用例我每次给别人讲这题都会让 TA 把下面这组用例全部跑过再提交输入期望输出原因空串Yes没有括号递归定义里空串合法()Yes最简单合法串[]Yes中括号同样合法([])Yes嵌套合法([)]No交叉嵌套类型错位)(No第一个右括号直接失败((No循环结束后栈非空))No第一个右括号栈空即失败)()No提前失败的典型例子[No只有一个左括号未被关闭所谓空串在 OJ 输入里可能表现为一行空行。洛谷原题通常会保证输入非空但你在本地测试时可以验证代码逻辑。无论如何循环不执行、栈为空、输出 Yes这符合定义。5.2 读入用 cin 还是 getline原题输入只有括号字符中间没有空格所以cin s最方便它自动过滤前面可能的空白字符。如果你用getline(cin, s)也能读进来但要注意 getline 会把行内空格也读入万一测试数据里带空格你的程序就可能把空格当成未知字符处理。本题没有这个风险不过“按题面选择读入方式”是个好习惯。某些变种题会在括号串里混入其他字符那时反而要按字符逐个处理把非括号字符忽略掉规则需要另说。5.3 条件表达式里的优先级在if ((c ) top () || (c ] top [))这行里运算符的优先级高于||所以你甚至可以少写一个括号。但为了阅读不出错我建议保留完整括号。竞赛代码不是越短越好而是越不容易错越好。这行逻辑的意思很直白右括号是)时栈顶必须是(右括号是]时栈顶必须是[两个条件任选其一成立就说明这次配对成功。5.4 时间复杂度与空间复杂度说明遍历字符串只需要 O(n)每次操作都是常数时间所以总时间 O(n)。空间复杂度方面最坏情况是字符串全部为左括号栈深 O(n)一般也不会超过这个范围。对 B2165 这种入门题重点是逻辑正确性能根本不用过度关注。甚至说你要是对栈还不熟完全可以用一个非常长的字符串做本地性能测试看看扫描速度会有很直观的感受。5.5 提交时最容易翻车的几个点第一使用std::stack时忘了引入stack如果在洛谷用bits/stdc.h没问题但到了其他编译环境可能编译错误。第二把 Yes 和 No 的大小写写错这题要求的是Yes、No不是YES、NO也不是yes。第三忘记在循环结束后检查剩余栈导致((输出 Yes。第四访问空栈的top()导致运行时错误。第五最多也最隐蔽的弹栈时不检查类型把([)]判成正确。把这几条记住这题就能稳稳过关。6. 从 B2165 出发能延伸出哪些同类问题6.1 只有一种括号时的简化如果题目只判断小括号比如洛谷 P1739 表达式括号匹配逻辑可以简化成用一个计数器遇到(加一遇到)减一任何时刻计数器为负数则失败最终计数器必须为零。为什么能用计数器因为只有一种括号不存在“栈顶类型是否匹配”的问题任何右括号都可以配任何左括号。这个简化恰好反过来验证了 B2165 为什么要用栈两种括号并存以后类型检查变成了硬需求计数器无能为力。6.2 最长合法括号子串类题目洛谷有题目叫括号匹配也有要求找最长合法括号子串长度的变种比如 LeetCode 32 或者洛谷 P1944。这类题单纯用“是/否判断”的栈写法已经不够至少要记录左括号的位置或者改用动态规划。但它的状态转移基础还是“最近未匹配的左括号”这一层逻辑。如果你在 B2165 上能把栈的进出状态完全理顺再看那些题会轻松很多因为你已经知道如何用一个位置栈去计算长度而不是只用一个值去判断布尔结果。6.3 真实开发场景里的括号匹配括号匹配并不是只存在于 OJ 题里。文本编辑器要实时高亮括号、IDE 要自动补全、计算器要推导表达式优先级、JSON 解析器要处理嵌套对象这些东西背后都涉及“成对结构的最近匹配”。甚至 XML 的标签闭合也是同款模型只是标签名比单字符更长判断逻辑也更重。栈之所以在数据结构教材里反复出现就是为了让你先在小括号上练熟这套思想以后遇到任何嵌套结构第一反应就是“可不可以抽象成栈”。就我个人做这题的经验来说最值得养成的习惯不是背代码而是在草稿纸上把字符串扫描时的栈状态变化从头画一遍。画完一遍之后所有边界情况基本都能想清楚再写代码只是翻译工作。遇到 WA也不要急着调输出回到状态图里重新推一遍输入用例绝大多数 bug 都出在你以为“没问题”的分支上。把 B2165 的栈模型吃透后面做括号相关的动态规划和解析器题目你会觉得很多套路都是老朋友。
B2165括号匹配：用栈解决括号顺序合法问题
洛谷 B2165 括号匹配我印象里是很多新手第一次接触“栈”这道坎。题目本身只有十几行代码但 AC 率和改错难度一点也不低因为很多人根本没弄懂它到底在考什么直接凭感觉写了个计数器就交了。这篇东西我就把这道题的考点、原理、实现和容易踩的坑一次说清楚尤其会解释为什么“数括号数量”这种直觉做法在这里必挂。1. 题目表面是字符串题实际上考的是“顺序合法”1.1 题面到底给出了什么限制B2165 的输入是一行只包含(、)、[、]四种字符的字符串你要判断这串括号是否匹配输出Yes或No。听起来简单但“匹配”两个字很容易被理解成“左括号和右括号数量一样”。我见过不少第一次做这题的人第一版代码就是四个计数器分别统计(、)、[、]数量相同就输出 Yes。这个思路在只看样例()的时候确实成立但只要稍微换几个用例就会翻车。比如字符串)(它有一个左括号和一个右括号数量完全相等可它显然不合法。因为第一个字符就是右括号它前面没有任何左括号可以和它配对。再比如样例里的([)]左右括号各两个数量也凑齐了可它依旧不合法。原因其实不复杂这串里第 3 个字符是)它想关闭小括号但当前“还没关闭”的括号里最近一个是[而不是(。也就是说([)]的嵌套关系是交叉的括号必须遵循“先开后关、后开先关”的次序不能跳着关。1.2 合法括号串的递归定义大学数据结构教材里通常会给一个递归定义空串是合法括号串如果 A 是合法括号串那么(A)和[A]也是合法括号串如果 A、B 都是合法括号串那么 AB 也是合法括号串。这个定义翻译成人话就是每个右括号必须和它前面最近一个还没有被配对的同类型左括号配对而且配对过程不能交叉。([)]之所以不合法是因为)想和它前面的(配对但中间还夹着一个未关闭的[。你必须在关闭[之后才有资格去关闭更外层的(一旦夹层存在就已经交叉了。这个递归定义还有一个隐藏结论合法括号串天然地呈现出嵌套结构。最内层的括号总是最早被关闭最外层的括号总是最后被关闭。换句话说“后打开的括号先关闭”这不就是栈吗栈的英文叫 stack一种只能在一端进出先进后出的结构。括号问题的所有解法本质都是在模拟这个“后进先出”的语义。1.3 为什么计数法没救有的读者可能会反驳我见过有的字符串题也判断括号用个计数器就过了。那类题通常有额外限制比如只有一种括号、且输入保证所有左括号都出现在右括号之前。而 B2165 同时出现两种括号顺序又是任意给的计数器根本表达不了“谁还没被关闭”“最近未关闭的是哪个”这两条关键信息。举一个更极端的例子([]]。从数量看小括号一对、中括号一对完美。但从语义看扫描到第 3 个字符]的时候当前未曾关闭的左括号有(和[最近的是[所以]可以关闭栈顶的[弹掉以后栈里剩下(。接着第 4 个字符又是]此时栈顶是(]和(类型不匹配失败。计数器完全看不出这个流程只有能记录“最近打开的括号是谁”的数据结构才能办到。这正是栈存在的价值。2. 先想明白“盒子模型”再写代码2.1 把扫描过程想象成往盒子里放东西我讲栈的时候喜欢用一个类比你手里有一个只能从顶部放东西和取东西的盒子现在要把括号串从左到右处理一遍。见到左括号就把它放进盒子见到右括号就看看盒子最上面那个左括号和它是不是一对是就拿走不是或者盒子已经空了那整串就废了。以[()]为例扫描到[放入盒子盒子内容是[扫描到(再放入盒子盒子内容是[ (注意栈底是[栈顶是(扫描到)盒子顶部正好是(类型匹配取出盒子变回[扫描到]盒子顶部正好是[类型匹配取出盒子空最终盒子是空的说明每个左括号都找到了自己的右括号输出 Yes。这个过程中后放进去的(反而先被取走先放进去的[后被取走这正是“后进先出”。再看经典的失败样例([)](入盒栈([入盒栈( [)来了但栈顶是[小括号并没有配对成功失败从这张状态图可以直观看到非法不是到底才发现的而是扫描到第 3 个字符就足以否决整串。这也是栈算法的一大特点大多数非法情况可以提前终止不需要看完整个输入。2.2 为什么只能看“栈顶”不能随便配也许有人会问既然我知道)对应的是(为什么不能从盒子中间把它取出来因为括号串的嵌套规则不允许交叉。如果我允许任意配对([)]就会被错误判定为合法让)配(让]配[数量对、类型也对看起来没问题。但合法的括号结构里内层必须完全被外层包裹不能一个括号只关一半。所以当前右括号能配对的左括号只能是所有未配对左括号中“最新”的那个也就是栈顶。你永远看不到栈中间的更早元素不是实现上的限制而是这个问题本身的逻辑约束。2.3 这题用栈的时间复杂度因为每个字符只会被处理一次要么压栈要么弹栈要么直接推出结论所以时间复杂度是 O(n)空间复杂度最坏 O(n)。最坏情况是什么整个串全是左括号比如((((((所有字符都会压进栈栈的深度等于字符串长度。这题输入规模对 OJ 来说并不大用标准库std::stack和用定长数组模拟栈都能轻松通过。真正影响成绩的从来不是性能而是边界条件的正确性。3. 主循环的三条规则和“结束后检查”3.1 扫描时的决策表把整套判断逻辑做成一张表写代码前先对照它会少踩很多坑当前字符当前栈状态操作结论(或[任意压入栈继续扫描)或]栈为空无法配对输出 No结束)或]栈顶是同类型左括号弹出栈顶继续扫描)或]栈顶是不同类型左括号类型不匹配输出 No结束所有字符处理完栈不为空有左括号剩余输出 No所有字符处理完栈为空全部配对输出 Yes这张表里最容易忽略的是最后一行扫描结束后栈里可能还残留左括号。比如输入((整个过程没有任何右括号来弹栈循环顺利跑完但显然不是合法括号串。所以必须在全部处理完之后额外检查一次栈是否为空把(!stack.empty())当成失败条件写上。3.2 伪代码版本用伪代码表达主循环读入字符串 s 初始化空栈 st 初始化 ok true for c in s: if c 是左括号: 把 c 压入 st else: if st 为空: ok false break top st 的栈顶 if (c ) 且 top () 或 (c ] 且 top [): 弹出 st else: ok false break if st 不为空: ok false 输出 ok ? Yes : No注意“右括号时先判栈空”这一步。很多初学代码直接写成if (c )) { if (st.top() () ... }一旦字符串以右括号开头st.top()会访问空栈的栈顶程序直接崩溃或者行为未定义。在 OJ 上表现就是 Runtime Error 或者神秘的 Wrong Answer。3.3 为什么必须在循环里 break 而不是 continue当发现一个右括号已经无法配对时后续字符即使看起来“正常”也不能改变整串非法的结论。比如)(第一个)就栈空按理说已经否了如果继续扫第二个(并把它入栈循环结束栈非空结果还是 No好像也能过。但如果输入是)()呢继续扫到(入栈、)弹栈循环结束栈为空如果不在出错时 break就可能错误输出 Yes。所以一旦判定失败立刻 break 或者直接return 0都行不要让后续字符有机会“救”回来。4. 三种实现方式对比标准库、数组栈、Python4.1 标准库 std::stack 版本直接上代码#include bits/stdc.h using namespace std; int main() { string s; cin s; stackchar st; bool ok true; for (char c : s) { if (c ( || c [) { st.push(c); } else { if (st.empty()) { ok false; break; } char top st.top(); if ((c ) top () || (c ] top [)) { st.pop(); } else { ok false; break; } } } if (!st.empty()) ok false; cout (ok ? Yes : No) \n; return 0; }使用#include bits/stdc.h是竞赛圈的惯例省去写多个头文件的麻烦洛谷是支持这个头文件的。如果你不喜欢这种写法也可以只包含iostream、stack和string。核心逻辑没有差别。4.2 字符数组模拟栈版本我早年刷题时不太喜欢泛滥的容器分配也更喜欢感知到底层内存怎么走所以会用定长数组模拟栈。这里给出一个版本#include bits/stdc.h using namespace std; int main() { string s; cin s; char st[1000005]; int top 0; bool ok true; for (char c : s) { if (c ( || c [) { st[top] c; } else { if (top 0) { ok false; break; } if ((c ) st[top] () || (c ] st[top] [)) { top--; } else { ok false; break; } } } if (top ! 0) ok false; cout (ok ? Yes : No) \n; return 0; }这里top表示栈中元素个数也相当于是下一个可写入位置减一。遇到左括号就把top加 1然后写入遇到匹配的右括号就把top减 1。这样栈底在st[1]栈顶在st[top]。如果你习惯从 0 开始可以把st[top]作为入栈操作但出栈判断时要记得对应改成top - 1两种写法都行关键是前后保持一致。字符数组大小我直接开了 1000005足以覆盖常见数据范围。4.3 一种我不推荐的简写网上有人把代码压缩成“遇到右括号就弹栈弹之前看看栈顶类型”的写法if (c ) || c ]) { if (!st.empty()) st.pop(); }这个版本在输入([)]时会输出什么它先压(再压[遇到)直接弹掉栈顶[遇到]再弹掉(最后栈空输出 Yes。显然错误。弹栈之前必须判断“类型是否匹配”这是本题的核心不能省。你压入栈的内容不只是“一个左括号”还包含了它的类型信息弹出时要把这个信息和右括号比对否则栈就和计数器没有区别了。4.4 Python 参考写法现在很多同学也会用 Python 交题我把完整实现也贴出来s input().strip() st [] ok True for c in s: if c in ([: st.append(c) else: if not st: ok False break top st[-1] if (c ) and top () or (c ] and top [): st.pop() else: ok False break if st: ok False print(Yes if ok else No)Python 的列表天然支持append和pop()就是很好的栈。要注意s input().strip()是为了去掉行尾换行符和可能的首尾空白。因为原题输入只含括号字符不会有空格strip()之后不会误删括号。5. 边界情况、输入读法和提交时的常见病5.1 必测的边界用例我每次给别人讲这题都会让 TA 把下面这组用例全部跑过再提交输入期望输出原因空串Yes没有括号递归定义里空串合法()Yes最简单合法串[]Yes中括号同样合法([])Yes嵌套合法([)]No交叉嵌套类型错位)(No第一个右括号直接失败((No循环结束后栈非空))No第一个右括号栈空即失败)()No提前失败的典型例子[No只有一个左括号未被关闭所谓空串在 OJ 输入里可能表现为一行空行。洛谷原题通常会保证输入非空但你在本地测试时可以验证代码逻辑。无论如何循环不执行、栈为空、输出 Yes这符合定义。5.2 读入用 cin 还是 getline原题输入只有括号字符中间没有空格所以cin s最方便它自动过滤前面可能的空白字符。如果你用getline(cin, s)也能读进来但要注意 getline 会把行内空格也读入万一测试数据里带空格你的程序就可能把空格当成未知字符处理。本题没有这个风险不过“按题面选择读入方式”是个好习惯。某些变种题会在括号串里混入其他字符那时反而要按字符逐个处理把非括号字符忽略掉规则需要另说。5.3 条件表达式里的优先级在if ((c ) top () || (c ] top [))这行里运算符的优先级高于||所以你甚至可以少写一个括号。但为了阅读不出错我建议保留完整括号。竞赛代码不是越短越好而是越不容易错越好。这行逻辑的意思很直白右括号是)时栈顶必须是(右括号是]时栈顶必须是[两个条件任选其一成立就说明这次配对成功。5.4 时间复杂度与空间复杂度说明遍历字符串只需要 O(n)每次操作都是常数时间所以总时间 O(n)。空间复杂度方面最坏情况是字符串全部为左括号栈深 O(n)一般也不会超过这个范围。对 B2165 这种入门题重点是逻辑正确性能根本不用过度关注。甚至说你要是对栈还不熟完全可以用一个非常长的字符串做本地性能测试看看扫描速度会有很直观的感受。5.5 提交时最容易翻车的几个点第一使用std::stack时忘了引入stack如果在洛谷用bits/stdc.h没问题但到了其他编译环境可能编译错误。第二把 Yes 和 No 的大小写写错这题要求的是Yes、No不是YES、NO也不是yes。第三忘记在循环结束后检查剩余栈导致((输出 Yes。第四访问空栈的top()导致运行时错误。第五最多也最隐蔽的弹栈时不检查类型把([)]判成正确。把这几条记住这题就能稳稳过关。6. 从 B2165 出发能延伸出哪些同类问题6.1 只有一种括号时的简化如果题目只判断小括号比如洛谷 P1739 表达式括号匹配逻辑可以简化成用一个计数器遇到(加一遇到)减一任何时刻计数器为负数则失败最终计数器必须为零。为什么能用计数器因为只有一种括号不存在“栈顶类型是否匹配”的问题任何右括号都可以配任何左括号。这个简化恰好反过来验证了 B2165 为什么要用栈两种括号并存以后类型检查变成了硬需求计数器无能为力。6.2 最长合法括号子串类题目洛谷有题目叫括号匹配也有要求找最长合法括号子串长度的变种比如 LeetCode 32 或者洛谷 P1944。这类题单纯用“是/否判断”的栈写法已经不够至少要记录左括号的位置或者改用动态规划。但它的状态转移基础还是“最近未匹配的左括号”这一层逻辑。如果你在 B2165 上能把栈的进出状态完全理顺再看那些题会轻松很多因为你已经知道如何用一个位置栈去计算长度而不是只用一个值去判断布尔结果。6.3 真实开发场景里的括号匹配括号匹配并不是只存在于 OJ 题里。文本编辑器要实时高亮括号、IDE 要自动补全、计算器要推导表达式优先级、JSON 解析器要处理嵌套对象这些东西背后都涉及“成对结构的最近匹配”。甚至 XML 的标签闭合也是同款模型只是标签名比单字符更长判断逻辑也更重。栈之所以在数据结构教材里反复出现就是为了让你先在小括号上练熟这套思想以后遇到任何嵌套结构第一反应就是“可不可以抽象成栈”。就我个人做这题的经验来说最值得养成的习惯不是背代码而是在草稿纸上把字符串扫描时的栈状态变化从头画一遍。画完一遍之后所有边界情况基本都能想清楚再写代码只是翻译工作。遇到 WA也不要急着调输出回到状态图里重新推一遍输入用例绝大多数 bug 都出在你以为“没问题”的分支上。把 B2165 的栈模型吃透后面做括号相关的动态规划和解析器题目你会觉得很多套路都是老朋友。
