从栈到计数器：括号匹配与合法括号序列的判定

1. 从题面定义到栈括号序列这题到底在说什么洛谷 B3758 这道题我第一眼看到的时候差点以为就是“用栈模拟括号匹配”的模板题但实际上它比模板题多考了一层东西它把“合法括号序列”的三种等价位面全揉在了一起。2021 年江苏省“信息与未来”活动把这个题目放进小学组赛程难度不大但我一直觉得它是特别适合用来建立“定义、算法、证明”三层思维的一道入门题。很多人拿到这种题的第一反应是开一个栈遇到左括号就压入遇到右括号就判断栈顶最后看栈是否为空。这个流程本身没有错但如果你只背到这个程度遇到题目稍加变形比如出现?字符、求最长合法子串、输出全部合法序列就会卡住。所以我决定把这道题当成一个“母题”来讲先彻底搞清楚它要我们判断的到底是什么。题目给出的“合法括号序列”通常采用这样的递归定义空字符串是一个合法的括号序列如果 A 是一个合法的括号序列那么(A)也是一个合法的括号序列如果 A 和 B 都是合法的括号序列那么 AB 也是一个合法的括号序列。这就是整道题的“宪法”。很多同学做题时把括号匹配当成一个单纯的技巧问题忽略了递归定义才是真正的核心。你看按照这个定义()合法(()())合法()与()()都合法而)(、())、(()都不合法。我们后面写的所有解法本质上都是在模拟这三条规则。从定义到算法有一个很自然的桥梁栈。定义里的第二条说“如果 A 合法那么 (A) 合法”这句话翻译成人话就是一对左右括号之间夹着的部分不能出现“右括号跑到左括号前面”的情况。如果我们从左往右读字符串用栈来记录还没配对的左括号那么在读到一个右括号的时候栈里就必须正好有一个左括号等着它。栈不空配对成功弹出栈为空直接宣告非法。但这个栈的使用方式有一个值得大家注意的地方这个栈里只压了一种字符就是左括号。既然栈里永远只可能有同一种元素那“栈是否为空”就完全可以退化成一个整数计数器。这就是下一节要讲的东西如何把一个栈浓缩成一个int。我建议新手在学这道题的时候先老老实实写一遍栈版本再把栈版本“翻译”成计数器版本。两个版本都需要能独立写出来因为考试的时候你会下意识地用计数器版本省空间而对拍、讲解思路的时候又需要栈版本更容易说清楚。2. 计数器版本的两种理解一次遍历加一个 int 的底气为什么计数器版本是对的这是整道题最关键的证明也是很多人没有想过的部分。我们把从左到右的扫描过程当成一次“括号平衡游戏”。维护一个整型变量cnt遇到左括号就加 1遇到右括号就减 1。如果我们能保证整个过程中cnt永远不小于 0并且在扫描结束后cnt正好等于 0那么这串括号就是合法的。先从不合法的情况反推。什么时候一定不合法第一种情况扫描过程中某个时刻cnt变成了负数。这意味着什么意味着在这个位置之前右括号比左括号多了至少一个。你可以把它理解成“你先伸手要钱可钱包里根本没有钱”这种括号序列无论如何都不可能满足定义第二条要求的那对括号关系。在)(这样的字符串里第一个字符就让cnt变成 -1直接出局。第二种情况扫描结束后cnt大于 0。这说明左括号的总数比右括号总数多。这里要留意可能出现“过程中从没为负、但最后不等于 0”的情况比如(()。它读起来好像是“前一半匹配了最后多了一个左括号”但多余的左括号永远找不到对应的右括号自然不合法。所以合法性判断只需要两个条件扫描全程cnt不小于 0扫描结束cnt恰好为 0。你会不会觉得奇怪为什么不需要关注括号的具体位置只需要看数量关系答案是括号匹配是一种“偏序结构”它比普通计数更严格但这道简单题目里“过程中不为负”已经把我们需要的嵌套结构信息全部编码进去了。举个反直觉的例子()()()()四个片段拼起来合法吗合法。计数器的过程中cnt在 0 和 1 之间跳动永远不为负最后回到 0。再看(()())计数过程是 1、2、1、2、1、0也满足。反过来())在第 3 个字符处cnt变为 -1非法。你会发现这个计数器并不是简单地统计左右括号数量的差它其实是一种“前缀和约束”任意前缀中左括号数量都不少于右括号数量且总数相等。这个结论其实就藏在定义里。你可以把定义的第二条和第三条不断展开任何合法括号序列都可以拆成一棵树每一对括号把中间的内容包裹起来而多个并列的括号组合就是顺序拼接。对树做从左到右的前序遍历恰好就是“先左后右、匹配结束回到当前层”的计数特征。理解了这一层你就不会再把cnt 0的检查漏掉了。漏掉它会出大问题比如())(()只靠“最后 cnt 0”判断会错误输出合法但实际它是非法的。这个坑我在下面的踩坑部分会专门再提一次。3. 四种实现方式与完整代码下面给出几种实现。代码不是重点重点是每种实现背后的思考角度。C 选手建议至少掌握前两种Python 选手可以直接用第三种第四种递归写法纯粹是为了加深对题面定义的理解。3.1 计数器版 C 实现这是考场最推荐的写法时间 O(n)空间 O(1)。#include bits/stdc.h using namespace std; int main() { string s; cin s; int cnt 0; for (char c : s) { if (c () { cnt; } else { cnt--; if (cnt 0) { cout No endl; return 0; } } } cout (cnt 0 ? Yes : No) endl; return 0; }注意我在读到右括号时是先cnt--再判断是否小于 0而不是先判断再减。两种写法都可以但先减后判断更容易和“前缀和为负”的定义对上号。有些同学写if (cnt 0) 非法在遇到右括号时提前判断实际上也是在模拟同一个条件。3.2 栈版 C 实现栈版的优势在于它的语义更接近定义便于扩展思考。#include bits/stdc.h using namespace std; int main() { string s; cin s; stackchar st; for (char c : s) { if (c () { st.push(c); } else { if (st.empty()) { cout No endl; return 0; } st.pop(); } } cout (st.empty() ? Yes : No) endl; return 0; }你对比一下就会发现st.empty()的检查本质上就是计数器里cnt 0的判断。栈里元素的数量就是cnt所以这个栈可以“降维”成一个整数。如果哪天题目改成同时出现[、{、(多种括号那就不能降维了因为栈必须区分括号类型这时候栈版本才是唯一正确的解法。记住这个区分点以后做题会很有用。3.3 Python 版实现Python 写起来会更短尤其适合快速验证思路。s input().strip() cnt 0 ok True for c in s: if c (: cnt 1 else: cnt - 1 if cnt 0: ok False break if ok and cnt 0: print(Yes) else: print(No)这里有个小细节input().strip()是为了去掉末尾的换行符。如果题目数据里字符串可能包含空格建议使用sys.stdin.readline().strip()或sys.stdin.read().split()进一步处理但通常竞赛题的字符串就是普通一行没有空格。3.4 按定义递归判断的参考代码这版代码我不推荐在考场写因为它最坏是 O(n^2)但它有一个其他写法没有的价值它逐字逐句地执行了题目定义。#include bits/stdc.h using namespace std; string s; bool legal(int l, int r) { if (l r) return true; // 空串合法 if (s[l] ! () return false; // 合法序列不可能以右括号开始 int depth 0; for (int i l; i r; i) { if (s[i] () depth; else depth--; if (depth 0) return false; if (depth 0) { return legal(l 1, i - 1) legal(i 1, r); } } return false; } int main() { cin s; cout (legal(0, (int)s.size() - 1) ? Yes : No) endl; return 0; }这个递归的思路是从左端点出发找到第一对匹配的括号把中间部分和右边剩余部分分别递归判断。它本质上是在还原定义里的第二、第三条规则。为什么能找到第一对匹配括号因为从头扫描第一个让depth归零的位置必然是第一个左括号对应的配对右括号。这个结论严格证明也不难可以当成一个思维练习。4. 踩坑记录WA、RE 与边界情况的复盘这题看起来简单但我见过太多人在细节上翻车。这里把我的踩坑经验整理成几类每一条都是真实的教训。4.1 漏掉“过程中 cnt 0”的判断这是最常见的错误。只看最终cnt 0遇到())这种数据会得到错误结果。原因是第三个字符是右括号它出现时已经没有任何左括号可以和它匹配了此时整个串已经非法。哪怕后面再补几个左括号让总数平衡也无法改变“那个右括号是孤儿”的事实。我建议你在写代码时养成一个习惯任何涉及前缀约束的题先用极端的例子来测试。比如))((、())(、(()这三个数据必须全部返回非法。4.2 空串和只有一个字符的边界按照定义空串是合法括号序列。计数器版对空串的处理是天然的cnt 0循环不执行最后cnt 0输出合法。但如果你的代码里有“读入后直接判断长度是否为 0然后输出非法”的逻辑那就错了。只有一个字符的情况(和)都是非法。前者结束cnt 0后者中途就cnt 0。这两个测试数据也很容易被人忽略。4.3 题目要求的输出格式洛谷题面的输出格式往往有严格规定。我写这篇文章时用的是Yes/No但如果你在真实比赛或刷题时遇到这道题请一定先看题面要求的字符串是YES/NO、yes/no还是true/false。大写小写拼错WA 一次不冤枉但很憋屈。我自己的习惯是把题目的输出说明复制到代码注释的第一行避免写着写着忘了。4.4 栈版本的 RE 风险栈版最容易遇到运行时错误的地方是stack::pop()时栈为空。如果代码里写的是if (c )) { st.pop(); }那么输入一旦以)开头程序就会对空栈执行pop()轻则返回值未定义重则直接 RE。测试数据)(立即就能暴露这个问题。所以必须在pop()之前检查st.empty()。4.5 大数据的性能与类型这道题数据范围不大int完全够用。但如果题目规模到十万、百万级别cnt也只是个计数器int仍够用不必开long long。真正需要注意的是读入速度。如果你用cin处理超长字符串记得加上ios::sync_with_stdio(false);和cin.tie(nullptr);否则在极端数据下可能被 IO 卡到超时。4.6 复杂度分析的结论无论计数器版还是栈版都是每个字符进出一次时间复杂度 O(n)空间复杂度计数器版 O(1)栈版 O(n)。在小学组比赛里O(n) 通常指扫描一遍就能出结果。如果这题你写出了两重循环或递归里每次重置扫描的版本复杂度变成 O(n^2)在小数据范围下能过但绝不是最优思路。学习阶段我还是建议大家追求最优解法因为这样能养成好习惯。5. 从这一题出发几个经典括号类变形题B3758 让我觉得值得写一篇长文是因为它像一棵树的根顺着它可以长出好几个常考题。5.1 生成所有合法括号序列给定一对括号总数n要求输出所有合法括号序列。这本质上就是“括号生成”问题LeetCode 22 题考过很多公司的笔试题也考过。核心思路是 DFS 回溯任何时候右括号数量不能超过左括号数量左括号数量不能超过 n。#include bits/stdc.h using namespace std; int n; void dfs(int left, int right, string cur) { if (left n right n) { cout cur \n; return; } if (left n) dfs(left 1, right, cur (); if (right left) dfs(left, right 1, cur )); } int main() { cin n; dfs(0, 0, ); return 0; }这段代码的剪枝条件right left和 B3758 的cnt 0本质上是一回事右括号必须在自己对应的左括号之后出现。5.2 最长合法括号子串这个题比 B3758 难了一档。给你一个字符串不一定是全合法的括号序列求其中最长的一段连续子串使得它是合法的括号序列。经典做法是动态规划dp[i]表示以第 i 个字符结尾的最长合法括号子串长度。当s[i] )且s[i-1] (时dp[i] dp[i-2] 2。当s[i] )且s[i-1] )时如果s[i - dp[i-1] - 1] (那么dp[i] dp[i-1] 2 dp[i - dp[i-1] - 2]。这个状态转移的细节很多如果第一次接触 DP建议先手工推算())(())这个例子把每个位置的dp值都写出来比看十遍题解都有用。5.3 带通配符的括号匹配题目变形字符串里可能出现??可以替换成左括号或者右括号问是否存在一种替换方案使得整个序列合法。这题有一个漂亮的贪心解法从左往右维护一个区间[low, high]表示当前未匹配的左括号数量的可能范围遇到(让整个区间加一遇到)让整个区间减一遇到?则区间同时向两边展开。最后看区间是否包含 0。这个变形我在教课的时候经常拿来接在 B3758 之后讲因为它的本质就是把“单个计数器”换成“计数器区间”思维跨度不算大但很能训练脑筋。5.4 多类型括号与表达式求值如果括号变成( )、[ ]、{ }三类判断合法就必须用栈因为字符串中不同类型的括号必须严格配对。不能再只用计数器了理由我在第 3.2 节提过。表达式求值中括号的处理也是一个经典应用。比如简单的中缀表达式1 2 * (3 - 4)借助栈处理括号就可以让运算符优先级判断变得更加直观。这类题目在信息学奥赛里很常见从 B3758 的“一个计数器”到“栈存储操作数和运算符”其实就是一条平滑的成长路径。6. 写给新手如何把一道水题变成一道母题最后分享一点我的个人复盘方法。很多人刷完一道简单题过两天就忘得干干净净我也曾是这样。后来我给自己定了一个规矩任何一道 AC 过的题必须花十分钟做三件事——重新推导核心证明、手写至少一种不同实现、联想一道相关的变形题。这个习惯让我的刷题效率翻了几倍。对 B3758 来说我的复盘顺序大概是这样的第一重新写一遍计数器版本的证明。不是背代码而是用纸笔写“为什么任意前缀左括号数不小于右括号数 整串左右括号总数相等等价于合法括号序列”想清楚这个才算真的会了。第二把栈版本和计数器版本对照着看一遍。注意它们在哪里做了相同的判断在哪里导致了不同的空间复杂度。多类型括号的情景会用到栈版本只有单一类型时仍然可以用计数器这两者的适用范围必须清清楚楚。第三找一道变形题来做。我推荐按难度阶梯先做生成所有合法括号序列再做最长合法括号子串最后挑战带通配符的括号匹配。每一次回头都能看到 B3758 的影子。另外我建议新手养成构造“极限测试数据”的习惯。对于这道题我给你一套现成的测试串全部跑一遍基本不会留死角输入期望结果覆盖点空串合法空边界(非法多左括号)非法开头右括号()合法基本匹配()()合法并列合法序列(())合法嵌套合法序列(()非法末尾缺右括号())非法末尾多右括号)(非法开头即非法(()())合法复杂嵌套与并列这些数据就是你的“对拍器”。如果代码能在这十组上全部给出正确结果再提交到洛谷基本就没有悬念。从一场小学组比赛的一道入门题到 LeetCode 原题级别的括号生成再到动态规划和贪心解法B3758 就像一颗种子。我教过的不少学生最初对栈和递归毫无概念就是从这道题开始建立起“合法括号序列”这个具象的模型。希望这篇题解也能帮你把这一层窗户纸捅破。