跳转至

# 括号序列

定义一个合法括号序列（balanced bracket sequence）为仅由 (( 和 )) 构成的字符串且：

- 空串 𝜀 ε 是一个合法括号序列．
- 如果 𝑠 s 是合法括号序列，那么 (𝑠)(s) 也是合法括号序列．
- 如果 𝑠,𝑡 s,t 都是合法括号序列，那么 𝑠 𝑡 s t 也是合法括号序列．

例如 (())()(())() 是合法括号序列，而 )())() 不是．

有时候会有多种不同的括号，如 [()]{}[()]{}．这样的变种括号序列与朴素括号序列有相似的定义．

本文将会介绍与括号序列相关的经典问题．

注：英语中一般称左括号为 opening bracket，而右括号是 closing bracket．

## 判断是否合法

判断 𝑠 s 是否为合法括号序列的经典方法是贪心思想．该算法同样适用于变种括号序列．

我们维护一个栈，对于 𝑖 =1,2,…,|𝑠|i=1,2,…,|s| 依次考虑：

- 如果 𝑠 𝑖 s i 是右括号且栈非空且栈顶元素是 𝑠 𝑖 s i 对应的左括号，就弹出栈顶元素．
- 若不满足上述条件，则将 𝑠 𝑖 s i 压入栈中．

在遍历整个 𝑠 s 后，若栈是空的，那么 𝑠 s 就是合法括号序列，否则就不是．时间复杂度 𝑂(𝑛)O(n)．

## 合法括号序列计数

考虑求出长度为 2 𝑛 2 n 的合法括号序列 𝑠 s 的个数 𝑓 𝑛 f n．不妨枚举与 𝑠 1 s 1 匹配的括号的位置，假设是 2 𝑖 +2 2 i+2．它将整个序列又分成了两个更短的合法括号序列．因此

𝑓 𝑛=𝑛−1∑𝑖=0 𝑓 𝑖 𝑓 𝑛−𝑖−1 f n=∑i=0 n−1 f i f n−i−1

这同样是卡特兰数的递推式．也就是说 𝑓 𝑛 =1 𝑛+1(2 𝑛 𝑛)f n=1 n+1(2 n n)．

当然，对于变种合法括号序列的计数，方法是类似的．假设有 𝑘 k 种不同类型的括号，那么有 𝑓′𝑛 =1 𝑛+1(2 𝑛 𝑛)𝑘 𝑛 f n′=1 n+1(2 n n)k n．

## 字典序后继

给出合法的括号序列 𝑠 s，我们要求出按字典序升序排序的长度为 |𝑠||s| 的所有合法括号序列中，序列 𝑠 s 的下一个合法括号序列．在本问题中，我们认为左括号的字典序小于右括号，且不考虑变种括号序列．

我们需要找到一个最大的 𝑖 i 使得 𝑠 𝑖 s i 是左括号．然后，将其变成右括号，并将 𝑠[𝑖 +1,|𝑠|]s[i+1,|s|] 这部分重构一下．另外，𝑖 i 必须满足：𝑠[1,𝑖 −1]s[1,i−1] 中左括号的数量 大于 右括号的数量．

不妨设当 𝑠 𝑖 s i 变成右括号后，𝑠[1,𝑖]s[1,i] 中左括号比右括号多了 𝑘 k 个．那么我们就让 𝑠 s 的最后 𝑘 k 个字符变成右括号，而 𝑠[𝑖 +1,|𝑠| −𝑘]s[i+1,|s|−k] 则用 ((…(())…))((…(())…)) 的形式填充即可，因为这样填充的字典序最小．

该算法的时间复杂度是 𝑂(𝑛)O(n)．

参考实现

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    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;
    }

## 字典序计算

给出合法的括号序列 𝑠 s，我们要求出它的字典序排名．

考虑求出字典序比 𝑠 s 小的括号序列 𝑝 p 的个数．

不妨设 𝑝 𝑖 <𝑠 𝑖 p i<s i 且 ∀1 ≤𝑗 <𝑖,𝑝 𝑗 =𝑠 𝑖∀1≤j<i,p j=s i．显然 𝑝 𝑖 p i 是左括号而 𝑠 𝑖 s i 是右括号．枚举 𝑖 i（满足 𝑠 𝑖 s i 为右括号），假设 𝑝[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) =1 f(0,0)=1．其实 𝑓 f 是 OEIS - A053121．

这样我们就可以 𝑂(|𝑠|2)O(|s|2) 计算字典序了．

对于变种括号序列，方法是类似的，只不过我们需要对每个 𝑠 𝑖 s i 考虑比它小的那些字符进行计算（在上述算法中因为不存在比左括号小的字符，所以我们只考虑了 𝑠 𝑖 s i 为右括号的情况）．

另外，利用 𝑓 f 数组，我们同样可以求出字典序排名为 𝑘 k 的合法括号序列．

本页面主要译自博文 http://e-maxx.ru/algo/bracket_sequences 与其英文翻译版 Balanced bracket sequences．其中俄文版版权协议为 Public Domain + Leave a Link；英文版版权协议为 CC-BY-SA 4.0．

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：mgt, ksyx, sshwy, diauweb, Enter-tainer, Tiphereth-A, Xeonacid
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用