括号序列专题

What · 是什么

括号序列问题围绕『合法括号序列（balanced bracket sequence）』展开：由 '(' 和 ')' 组成，满足任意前缀 '(' 数 ≥ ')' 数且总 '(' 数 = ')' 数（可递归定义：空串合法；s 合法则 (s) 合法；s,t 合法则 st 合法）。经典问题包括：① 判定合法性（栈，O(n)）；② 计数——长度为 2n 的合法序列数为卡特兰数 C_n = C(2n,n)/(n+1)（k 种括号则乘 k^n）；③ 字典序后继/字典序排名；④ 区间操作版——用线段树维护区间内『未匹配的 '(' 数』与『未匹配的 ')' 数』，支持括号序列的区间查询与修改（CF380C 模型：匹配括号对数）。

Why · 为什么

How · 实现

伪代码

# 判定合法（栈）
stack = []
for c in s:
    if c == '(' : stack.push(c)
    elif c == ')' and stack and stack.top == '(': stack.pop()
    else: stack.push(c)
return len(stack) == 0

# 线段树维护（区间匹配对数）
node = (open, close)  # 区间内未匹配的左右括号数
merge(a, b):
    match = min(a.open, b.close)
    return (a.open + b.open - match, a.close + b.close - match)

Python 实现

def is_balanced(s):
    st = []
    for c in s:
        if c == '(':
            st.append(c)
        elif c == ')' and st and st[-1] == '(':
            st.pop()
        else:
            st.append(c)
    return len(st) == 0

def count_catalan(n):
    # 长度为 2n 的合法括号序列个数 = 卡特兰数 C_n
    c = 1
    for k in range(n):
        c = c * (2 * n - k) // (k + 1)
    return c // (n + 1)

def next_balanced(s):
    """字典序后继；不存在返回 None（s 已是最后一个）"""
    s = list(s)
    n = len(s)
    depth = 0
    for i in range(n - 1, -1, -1):
        if s[i] == '(':
            depth -= 1
        else:
            depth += 1
        if s[i] == '(' and depth > 0:
            depth -= 1
            open_cnt = (n - i - 1 - depth) // 2
            close_cnt = n - i - 1 - open_cnt
            nxt = ''.join(s[:i]) + ')' + '(' * open_cnt + ')' * close_cnt
            return None if nxt == ''.join(s) else nxt
    return None

class BracketSeg:
    """线段树维护括号序列区间：查询区间内匹配括号对数"""
    def __init__(self, s):
        self.n = len(s)
        self.t = [(0, 0)] * (4 * self.n + 5)
        self._build(s, 1, 0, self.n - 1)

    def _build(self, s, p, l, r):
        if l == r:
            self.t[p] = (1, 0) if s[l] == '(' else (0, 1)
            return
        m = (l + r) // 2
        self._build(s, p * 2, l, m)
        self._build(s, p * 2 + 1, m + 1, r)
        self.t[p] = self._merge(self.t[p * 2], self.t[p * 2 + 1])

    def _merge(self, a, b):
        m = min(a[0], b[1])
        return (a[0] + b[0] - m, a[1] + b[1] - m)

    def query(self, ql, qr, p=1, l=0, r=None):
        if r is None:
            r = self.n - 1
        if ql <= l and r <= qr:
            return self.t[p]
        m = (l + r) // 2
        acc = (0, 0)
        if ql <= m:
            acc = self._merge(acc, self.query(ql, qr, p * 2, l, m))
        if qr > m:
            acc = self._merge(acc, self.query(ql, qr, p * 2 + 1, m + 1, r))
        return acc

if __name__ == '__main__':
    assert is_balanced('(())()') is True
    assert is_balanced(')()') is False
    assert is_balanced('') is True
    print('is_balanced OK')
    assert count_catalan(3) == 5  # C3 = 5
    assert count_catalan(4) == 14
    print('catalan OK')
    # 长度 6 的合法括号序列字典序：((())) < (()()) < (())() < ()(()) < ()()()
    assert next_balanced('((()))') == '(()())'
    assert next_balanced('(()())') == '(())()'
    assert next_balanced('(())()') == '()(())'
    assert next_balanced('()(())') == '()()()'
    assert next_balanced('()()()') is None
    print('next_balanced OK')
    seg = BracketSeg('(()())')
    op, cl = seg.query(0, 5)   # 全串合法
    assert op == 0 and cl == 0
    seg2 = BracketSeg('(())(()')
    op, cl = seg2.query(0, 6)
    assert (op, cl) == (1, 0)
    matched = (7 - op - cl) // 2
    assert matched == 3
    assert seg2.query(0, 3) == (0, 0)
    print('bracket seg OK (open=%d close=%d matched=%d)' % (op, cl, matched))

易错点

• 判定时把 ')' 压栈是常见错误——非匹配 ')' 压栈后栈永远不清空，需按『弹/压』规则严格区分
• 卡特兰数取模时要用模逆元或组合数递推，直接整除会错（n 大时）
• 线段树合并顺序不可交换（括号合并非交换），查询时左右顺序必须保持
• 区间翻转 '(' 与 ')' 后 open/close 需互换，漏换则结果全错
• 字典序后继中 depth 的符号约定（从右往左扫时 '(' 减 1、')' 加 1）容易写反

例题

信源

• OI Wiki✓ https://raw.githubusercontent.com/OI-wiki/OI-wiki/master/docs/topic/bracket.md
• CP-Algorithms✓ https://cp-algorithms.com/combinatorics/bracket_sequences.html