OI-wiki 括号序列专题：合法性判定、卡特兰计数与字典序算法的完整解析-平芜编程栈

OI-wiki 括号序列专题：合法性判定、卡特兰计数与字典序算法的完整解析

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

导读：括号序列（balanced bracket sequence）是 OI / ICPC 竞赛中最基础也最高频的字符串结构之一，从栈模拟判合法，到卡特兰数计数，再到字典序后继与排名求解，几乎覆盖了该主题的全部经典考点。本文以 OI-wiki docs/topic/bracket.md 为主线，结合仓库内卡特兰数专题与普通生成函数的内容进行纵深扩充，读完你将掌握括号序列四大经典问题的算法原理、复杂度分析与可复用的 C++ 实现。

1. 合法括号序列的定义

OI-wiki 中对合法括号序列（balanced bracket sequence）给出了一个递归定义：一个仅由(和)构成的字符串 $s$ 是合法的，当且仅当它满足以下三条规则之一：

空串：$\varepsilon$ 是合法括号序列；
包裹：如果 $s$ 是合法括号序列，那么 $(s)$ 也是合法括号序列；
拼接：如果 $s,t$ 都是合法括号序列，那么 $st$ 也是合法括号序列。

例如(())()是合法括号序列，而)()不是（前缀)处左括号数已经少于右括号数，且最终左、右括号数不相等）。

等价刻画：从另一个角度看，合法括号序列等价于"左括号总数等于右括号总数，且任意前缀中左括号数不少于右括号数"。这一刻画在实际判定与计数中更为常用，后文的贪心栈算法正是建立在这个性质之上。

变种括号序列：实际题目中常出现多种不同的括号，如[()]{}。这类变种序列的定义与朴素括号序列相似，只是配对关系变为()、[]、{}三组。变种序列要求每一对括号的类型严格匹配，即栈顶弹出的必须是当前右括号对应的那一种左括号。OI-wiki 原文还特别注明：英语中一般称左括号为 opening bracket，右括号为 closing bracket，在阅读英文题面与算法资料时常用到这对术语。

2. 判断括号序列是否合法：贪心 + 栈

判断 $s$ 是否为合法括号序列的经典方法是贪心思想，时间复杂度 $O(n)$，且同样适用于变种括号序列。

2.1 算法流程

维护一个栈，从左到右依次扫描 $i=1,2,\ldots,|s|$：

如果 $s_i$ 是右括号，且栈非空、栈顶元素是 $s_i$ 对应的左括号，就弹出栈顶元素；
否则，将 $s_i$ 压入栈中。

扫描结束后：

若栈为空，则 $s$ 是合法括号序列；
否则不是。

2.2 正确性论证

贪心策略的正确性可以从两方面论证：

右括号必须立刻匹配最近的左括号：当扫描到右括号 $s_i$ 时，它只能与"尚未匹配的、最靠近它的"左括号配对。若栈顶不是与之匹配的左括号，则说明二者之间存在未匹配的左括号或类型不匹配，此时无论后续字符如何，这个右括号都无法找到正确配对，因此必然不合法；
结束时栈空蕴含"括号数相等"：栈中剩余的只能是未匹配的左括号（或多余的右括号），只要栈非空就说明左右括号没有两两配对，序列必然不合法。

以)()为例：第一个字符)是右括号但栈为空，直接压栈；结束后栈非空，判定为不合法，与定义一致。

3. 合法括号序列计数：卡特兰数

3.1 递推式的导出

设长度为 $2n$ 的合法括号序列个数为 $f_n$。不妨枚举与 $s_1$ 匹配的那个右括号的位置，假设它是第 $2i+2$ 个字符（编号从 $0$ 开始）。那么：

$s[2..2i+1]$（夹在 $s_1$ 与它匹配的右括号之间）本身是一个长度为 $2i$ 的合法括号序列；
$s[2i+3..2n]$ 是一个长度为 $2(n-i-1)$ 的合法括号序列。

由乘法原理并对 $i$ 求和，得到：

$$ f_n=\sum_{i=0}^{n-1}f_i f_{n-i-1} $$

这正是卡特兰数（Catalan 数）的递推式，因此：

$$ f_n = \frac{1}{n+1}\binom{2n}{n} $$

卡特兰数数列的前几项为 $1,1,2,5,14,42,132,429,1430,\ldots$（见 docs/math/combinatorics/catalan.md 中引用的 OEIS A000108）。

3.2 变种括号序列的计数

对于变种括号序列，方法是类似的。假设有 $k$ 种不同类型的括号，每个"左括号位置"有 $k$ 种选择（与之配对的右括号类型随之确定），因此长度为 $2n$ 的变种合法括号序列数为：

$$ f'_n=\frac{1}{n+1}\binom{2n}{n}k^n $$

3.3 与更多组合问题的联系

卡特兰数远不止"括号计数"一个应用。OI-wiki 的卡特兰数专题指出，其递推关系 $C_n=\sum_{i=0}^{n-1}C_iC_{n-1-i}$ 具有天然的递归分拆结构，并给出了多个等价的组合问题（均可通过构造双射互相转化）：

路径计数：$n\times n$ 方格图中不越过对角线 $y=x$ 的单调路径数为 $C_n$；
圆内不相交弦：$2n$ 个点两两连边且互不相交的方案数为 $C_n$；
凸多边形三角剖分：$(n+2)$ 边形对角线不相交地剖分为三角形的方案数为 $C_n$；
二叉树计数：$n$ 个结点的形态不同二叉树数为 $C_n$；
出栈序列计数：进栈序列 $1,2,\ldots,n$ 的合法出栈序列数为 $C_n$；
±1 数列计数：由 $n$ 个 $+1$ 和 $n$ 个 $-1$ 组成、任意前缀和非负的数列数为 $C_n$。

其中括号序列与格路之间存在直接双射：将左括号视为向上一步、右括号视为向右一步，合法括号序列恰好对应不越过对角线的合法路径。该专题还通过生成函数（见 docs/math/poly/ogf.md 的"卡特兰数的生成函数"一节）证明了通项公式 $C_n=\frac{(2n)!}{n!(n+1)!}$ 以及递推形式 $C_n=\frac{4n-2}{n+1}C_{n-1}$，这些形式分别将计数问题转化为组合数计算或顺次递推，可高效求解。

4. 字典序后继：求下一个合法括号序列

4.1 问题定义

给出合法括号序列 $s$，要求在按字典序升序排序的长度为 $|s|$ 的所有合法括号序列中，求出 $s$ 的下一个合法括号序列。在本问题中约定：左括号的字典序小于右括号（即(<)），且不考虑变种括号序列。

4.2 核心算法

OI-wiki 给出的构造思路如下：

找到最大的下标 $i$，使得 $s_i$ 是左括号(，并且满足 $s[1,i-1]$ 中左括号的数量大于右括号的数量；
将 $s_i$ 改为右括号)；
重构后缀 $s[i+1,|s|]$。

第二步的合法性：由于 $s[1,i-1]$ 中左括号数大于右括号数，把 $s_i$ 从(改成)后，$s[1,i]$ 仍然是一个"前缀合法"的序列（任意前缀左括号数不少于右括号数），这样才有可能扩展成合法序列。

第三步的填充策略：设 $s_i$ 变成右括号后，$s[1,i]$ 中左括号比右括号多 $k$ 个。为了保持总括号数相等，序列的最后 $k$ 个字符必须是右括号；而中间的 $s[i+1,|s|-k]$ 则用

$$ ((\dots(())\dots)) $$

的形式填充（即先连续放尽可能多的左括号，再放对应数量的右括号），因为这样的填充方式在字典序上最小。

该算法的时间复杂度是 $O(n)$。

4.3 参考实现（OI-wiki 原文代码）

bool next_balanced_sequence(string& s) { int n = s.size(); int depth = 0; for (int i = n - 1; i >= 0; i--) { if (s[i] == '(') depth--; else depth++; if (s[i] == '(' && depth > 0) { depth--; int open = (n - i - 1 - depth) / 2; int close = n - i - 1 - open; string next = s.substr(0, i) + ')' + string(open, '(') + string(close, ')'); s.swap(next); return true; } } return false; }

对实现逐行拆解：

从后往前扫描（i = n-1递减），用一个depth变量记录"当前后缀中右括号比左括号多多少个"。具体地，遇到(时depth--，遇到)时depth++；
当遇到s[i]=='('且depth > 0时，说明把s[i]翻转为)后，s[1,i]中左括号仍比右括号多——这正是上文要求的"$s[1,i-1]$ 中左括号数量大于右括号数量"的等价条件（depth > 0表示后缀里右括号更多，即前缀里左括号更多）；
翻转后前缀"盈余"的左括号数为depth - 1，于是后缀中需要open = (n - i - 1 - depth) / 2个左括号和close = n - i - 1 - open个右括号，前者全部前置、后者全部后置，保证字典序最小；
构造新串next = s.substr(0,i) + ')' + string(open,'(') + string(close,')')并交换；
若整个序列已经是字典序最大的合法括号序列（形如(((...)))），函数返回false，表示不存在后继。

以 $n=3$ 的合法序列字典序枚举为例：

((())) (()()) (())() ()(()) ()()()

从(())()出发：扫描到下标 $i=2$ 处的(时，其后缀中右括号数更多（满足条件），将其翻转为)得到前缀())，此时盈余 $k=1$，因此最后 1 个字符放)，中间用(()填充，得到()(())，恰好是字典序中的下一个。

5. 字典序计算：求排名与反推序列

5.1 问题定义

给出合法括号序列 $s$，要求出它在"按字典序升序排列的长度为 $|s|$ 的所有合法括号序列"中的排名。OI-wiki 给出的方法不是直接数出比 $s$ 大的序列，而是数出所有字典序比 $s$ 小的括号序列 $p$ 的个数，排名即等于这个数目加 $1$。

5.2 转化为 DP 统计

设 $p_i < s_i$ 且 $\forall, 1\le j<i,\ p_j=s_j$。由于左括号字典序最小，$p_i$ 必为左括号而 $s_i$ 必为右括号。于是：

枚举 $i$（满足 $s_i$ 为右括号）；
假设 $p[1,i]$ 中左括号比右括号多 $k$ 个；
问题转化为：统计长度为 $|s|-i$、存在 $k$ 个未匹配的右括号、且不存在未匹配的左括号的括号序列的个数。

为此定义 DP 状态：$f(i,j)$ 表示长度为 $i$、存在 $j$ 个未匹配的右括号、且不存在未匹配的左括号的括号序列的个数。

5.3 转移方程

枚举括号序列的第一个字符是什么：

第一个字符是右括号：未匹配的右括号数从 $j-1$ 增加到 $j$，即来自 $f(i-1,j-1)$；
第一个字符是左括号：会与一个右括号"抵消"，未匹配的右括号数从 $j+1$ 减少到 $j$，即来自 $f(i-1,j+1)$。

因此转移为：

$$ f(i,j)=f(i-1,j-1)+f(i-1,j+1) $$

初始条件 $f(0,0)=1$，其余 $f(0,j)=0\ (j>0)$。这个三角形数表实际对应 OEIS 中的 A053121 序列（即所谓"卡特兰三角形"）。利用该数组，可以在 $O(|s|^2)$ 时间内完成字典序计算（$|s|$ 是序列长度，DP 表规模为 $O(|s|^2)$）。

5.4 变种括号序列的推广

对于变种括号序列，方法是类似的，唯一的区别在于：需要对每个 $s_i$ 枚举所有比它小的字符并分别累加。在原算法中，由于朴素情况下不存在比左括号更小的字符，所以只考虑了 $s_i$ 为右括号的情形；而在变种场景下（例如字符集存在<、[、(等多级优先级时），每个位置都可能有多于一个"更小但可配对"的选择，需要对它们逐一用 $f$ 数组统计。

5.5 由排名反推序列

利用同一张 $f$ 数组，我们也可以完成反向操作：求字典序排名为 $k$ 的合法括号序列。做法是逐位确定字符——在当前位尝试放(，若以(为前缀的合法序列总数（可预先用 $f$ 数组算得）不少于剩余需要跳过的排名 $k$，则确定放(；否则减去该数量、改放)，如此循环直至填满整个序列。这本质上是"数位 DP + 逐位构造"的标准技巧，与上述统计过程互为逆运算。

6. 小结与复杂度一览

问题	核心思想	时间复杂度
判定合法性	贪心 + 栈扫描	$O(n)$
合法序列计数	卡特兰数递推 / 通项公式	$O(n)$ 或 $O(n\log n)$（组合数）
字典序后继	反向扫描找翻转点 + 最小字典序重构	$O(n)$
字典序排名	DP 表 $f(i,j)$ 逐位统计	$O(	s	^2)$
由排名反推序列	利用 $f$ 数组逐位构造	$O(	s	^2)$

本文涉及的算法均可在仓库中对应文档继续深挖：括号序列计数的完整推导与多组合问题双射见 docs/math/combinatorics/catalan.md，生成函数解法见 docs/math/poly/ogf.md（"卡特兰数的生成函数"一节）。此外，括号序列思想在 OI-wiki 其他专题中也有广泛应用，例如伸展树维护括号序、动态树括号序维护以及 DFS 序与括号序的结合，可作为进一步学习的延伸方向。

页首声明：本页面核心内容主要译自博文 Balanced bracket sequences（俄文原文与英文翻译版），其中俄文版版权协议为 Public Domain + Leave a Link，英文版版权协议为 CC-BY-SA 4.0；OI-wiki 在此基础上按自身排版与示例风格进行了整理与扩充。

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考