括號序列

定義一個合法括號序列（balanced bracket sequence）為僅由 \((\) 和 \()\) 構成的字符串且：

空串 \(\varepsilon\) 是一個合法括號序列。
如果 \(s\) 是合法括號序列，那麼 \((s)\) 也是合法括號序列。
如果 \(s,t\) 都是合法括號序列，那麼 \(st\) 也是合法括號序列。

例如 \((())()\) 是合法括號序列，而 \()()\) 不是。

有時候會有多種不同的括號，如 \([()]\{\}\)。這樣的變種括號序列與樸素括號序列有相似的定義。

本文將會介紹與括號序列相關的經典問題。

注：英語中一般稱左括號為 opening bracket，而右括號是 closing bracket。

判斷是否合法

判斷 \(s\) 是否為合法括號序列的經典方法是貪心思想。該算法同樣適用於變種括號序列。

我們維護一個棧，對於 \(i=1,2,\ldots,|s|\) 依次考慮：

如果 \(s_i\) 是右括號且棧非空且棧頂元素是 \(s_i\) 對應的左括號，就彈出棧頂元素。
若不滿足上述條件，則將 \(s_i\) 壓入棧中。

在遍歷整個 \(s\) 後，若棧是空的，那麼 \(s\) 就是合法括號序列，否則就不是。時間複雜度 \(O(n)\)。

合法括號序列計數

考慮求出長度為 \(2n\) 的合法括號序列 \(s\) 的個數 \(f_n\)。不妨枚舉與 \(s_1\) 匹配的括號的位置，假設是 \(2i+2\)。它將整個序列又分成了兩個更短的合法括號序列。因此

\[ f_n=\sum_{i=0}^{n-1}f_if_{n-i-1} \]

這同樣是卡特蘭數的遞推式。也就是説 \(f_n=\frac{1}{n+1}\binom{2n}{n}\)。

當然，對於變種合法括號序列的計數，方法是類似的。假設有 \(k\) 種不同類型的括號，那麼有 \(f'_n=\frac{1}{n+1}\binom{2n}{n}k^n\)。

字典序後繼

給出合法的括號序列 \(s\)，我們要求出按字典序升序排序的長度為 \(|s|\) 的所有合法括號序列中，序列 \(s\) 的下一個合法括號序列。在本問題中，我們認為左括號的字典序小於右括號，且不考慮變種括號序列。

我們需要找到一個最大的 \(i\) 使得 \(s_i\) 是左括號。然後，將其變成右括號，並將 \(s[i+1,|s|]\) 這部分重構一下。另外，\(i\) 必須滿足：\(s[1,i-1]\) 中左括號的數量大於右括號的數量。

不妨設當 \(s_i\) 變成右括號後，\(s[1,i]\) 中左括號比右括號多了 \(k\) 個。那麼我們就讓 \(s\) 的最後 \(k\) 個字符變成右括號，而 \(s[i+1,|s|-k]\) 則用 \(((\dots(())\dots))\) 的形式填充即可，因為這樣填充的字典序最小。

該算法的時間複雜度是 \(O(n)\)。

參考實現

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\) 且 \(\forall 1\le j<i,p_j=s_i\)。顯然 \(p_i\) 是左括號而 \(s_i\) 是右括號。枚舉 \(i\)（滿足 \(s_i\) 為右括號），假設 \(p[1,i]\) 中左括號比右括號多 \(k\) 個，那麼相當於我們要統計長度為 \(|s|-i\) 且存在 \(k\) 個未匹配的右括號且不存在未匹配的左括號的括號序列的個數。

不妨設 \(f(i,j)\) 表示長度為 \(i\) 且存在 \(j\) 個未匹配的右括號且不存在未匹配的左括號的括號序列的個數。

通過枚舉括號序列第一個字符是什麼，可以得到 \(f\) 的轉移：\(f(i,j) = f(i-1,j-1)+f(i-1,j+1)\)。初始時 \(f(0,0)=1\)。其實 \(f\) 是 OEIS - A053121。

這樣我們就可以 \(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。

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：sshwy
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用