括号序列
定义一个合法括号序列（balanced bracket sequence）为仅由 ((
和 )) 构成的字符串且：
- 空串 𝜀ε 是一个合法括号序列．
- 如果 𝑠s 是合法括号序列，那么 (𝑠)(s) 也是合法括号序列．
- 如果 𝑠,𝑡s,t 都是合法括号序列，那么 𝑠𝑡st 也是合法括号序列．
例如 (())()(())() 是合法括号序列，而 )())() 不是．
有时候会有多种不同的括号，如 [()]{}[()]{}．这样的变种括号序列与朴素括号序列有相似的定义．
本文将会介绍与括号序列相关的经典问题．
注：英语中一般称左括号为 opening bracket，而右括号是 closing bracket．
判断是否合法
判断 𝑠s 是否为合法括号序列的经典方法是贪心思想．该算法同样适用于变种括号序列．
我们维护一个栈，对于 𝑖 =1,2,…,|𝑠|i=1,2,…,|s| 依次考虑：
- 如果 𝑠𝑖si 是右括号且栈非空且栈顶元素是 𝑠𝑖si 对应的左括号，就弹出栈顶元素．
- 若不满足上述条件，则将 𝑠𝑖si 压入栈中．
在遍历整个 𝑠s 后，若栈是空的，那么 𝑠s 就是合法括号序列，否则就不是．时间复杂度 𝑂(𝑛)O(n)．
合法括号序列计数
考虑求出长度为 2𝑛2n 的合法括号序列 𝑠s 的个数 𝑓𝑛fn．不妨枚举与 𝑠1s1 匹配的括号的位置，假设是 2𝑖 +22i+2．它将整个序列又分成了两个更短的合法括号序列．因此
𝑓𝑛=𝑛−1∑𝑖=0𝑓𝑖𝑓𝑛−𝑖−1fn=∑i=0n−1fifn−i−1
这同样是卡特兰数的递推式．也就是说 𝑓𝑛 =1𝑛+1(2𝑛𝑛)fn=1n+1(2nn)．
当然，对于变种合法括号序列的计数，方法是类似的．假设有 𝑘k 种不同类型的括号，那么有 𝑓′𝑛 =1𝑛+1(2𝑛𝑛)𝑘𝑛fn′=1n+1(2nn)kn．
字典序后继
给出合法的括号序列 𝑠s，我们要求出按字典序升序排序的长度为 |𝑠||s| 的所有合法括号序列中，序列 𝑠s 的下一个合法括号序列．在本问题中，我们认为左括号的字典序小于右括号，且不考虑变种括号序列．
我们需要找到一个最大的 𝑖i 使得 𝑠𝑖si 是左括号．然后，将其变成右括号，并将 𝑠[𝑖 +1,|𝑠|]s[i+1,|s|] 这部分重构一下．另外，𝑖i 必须满足：𝑠[1,𝑖 −1]s[1,i−1] 中左括号的数量 大于 右括号的数量．
不妨设当 𝑠𝑖si 变成右括号后，𝑠[1,𝑖]s[1,i] 中左括号比右括号多了 𝑘k 个．那么我们就让 𝑠s 的最后 𝑘k 个字符变成右括号，而 𝑠[𝑖 +1,|𝑠| −𝑘]s[i+1,|s|−k] 则用 ((…(())…))((…(())…)) 的形式填充即可，因为这样填充的字典序最小．
该算法的时间复杂度是 𝑂(𝑛)O(n)．
参考实现
---|---
## 字典序计算
给出合法的括号序列 𝑠s，我们要求出它的字典序排名．
考虑求出字典序比 𝑠s 小的括号序列 𝑝p 的个数．
不妨设 𝑝𝑖 <𝑠𝑖pi<si 且 ∀1 ≤𝑗 <𝑖,𝑝𝑗 =𝑠𝑖∀1≤j<i,pj=si．显然 𝑝𝑖pi 是左括号而 𝑠𝑖si 是右括号．枚举 𝑖i（满足 𝑠𝑖si 为右括号），假设 𝑝[1,𝑖]p[1,i] 中左括号比右括号多 𝑘k 个，那么相当于我们要统计长度为 |𝑠| −𝑖|s|−i 且存在 𝑘k 个未匹配的右括号且不存在未匹配的左括号的括号序列的个数．
不妨设 𝑓(𝑖,𝑗)f(i,j) 表示长度为 𝑖i 且存在 𝑗j 个未匹配的右括号且不存在未匹配的左括号的括号序列的个数．
通过枚举括号序列第一个字符是什么，可以得到 𝑓f 的转移：𝑓(𝑖,𝑗) =𝑓(𝑖 −1,𝑗 −1) +𝑓(𝑖 −1,𝑗 +1)f(i,j)=f(i−1,j−1)+f(i−1,j+1)．初始时 𝑓(0,0) =1f(0,0)=1．其实 𝑓f 是 [OEIS - A053121](http://oeis.org/A053121)．
这样我们就可以 𝑂(|𝑠|2)O(|s|2) 计算字典序了．
对于变种括号序列，方法是类似的，只不过我们需要对每个 𝑠𝑖si 考虑比它小的那些字符进行计算（在上述算法中因为不存在比左括号小的字符，所以我们只考虑了 𝑠𝑖si 为右括号的情况）．
另外，利用 𝑓f 数组，我们同样可以求出字典序排名为 𝑘k 的合法括号序列．
**本页面主要译自博文<http://e-maxx.ru/algo/bracket_sequences> 与其英文翻译版 [Balanced bracket sequences](https://cp-algorithms.com/combinatorics/bracket_sequences.html)．其中俄文版版权协议为 Public Domain + Leave a Link；英文版版权协议为 CC-BY-SA 4.0．**
* * *
> __本页面最近更新： 2026/1/7 08:56:54，[更新历史](https://github.com/OI-wiki/OI-wiki/commits/master/docs/topic/bracket.md)
> __发现错误？想一起完善？[在 GitHub 上编辑此页！](https://oi-wiki.org/edit-landing/?ref=/topic/bracket.md "edit.link.title")
> __本页面贡献者：[mgt](mailto:i@margatroid.xyz), [ksyx](https://github.com/ksyx), [sshwy](https://github.com/sshwy), [diauweb](https://github.com/diauweb), [Enter-tainer](https://github.com/Enter-tainer), [Tiphereth-A](https://github.com/Tiphereth-A), [Xeonacid](https://github.com/Xeonacid)
> __本页面的全部内容在**[CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/deed.zh) 和 [SATA](https://github.com/zTrix/sata-license)** 协议之条款下提供，附加条款亦可能应用