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; stack<char> 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 就像一颗种子。我教过的不少学生，最初对栈和递归毫无概念，就是从这道题开始建立起“合法括号序列”这个具象的模型。希望这篇题解也能帮你把这一层窗户纸捅破。