括号加次数解压：递归grammar与输出上限

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练grammar以括号包重复段，右括号后紧跟{2..99}；普通字符不含(){}，无转义。
• 缺左/右括号、额外右括号示例排版有冲突，正式合同待确认。本文验证完整合法grammar并拒绝不合法输入，不照错样例强行输出。

解题路线

1. 递归sequence消费到对应右括号，读{count}后复制内部段。根调用结束必须恰到text尾，不允许静默忽略额外)。
2. 字符串重复指数扩展，复制前检验len(part)×count是否超过剩余max_output；内层也限制。错误位置/输出超限明确报错。
3. 生产实现可先构建紧凑AST并计算展开长度，再以generator输出，避免中间层大量字符串复制。只读压缩长并不能代表工作量，因为输出本身需Ω(L)。

手动走一遍

a(abc){3}→aabcabcabc；a(b(c){2}){3}d→abccbccbccd。((x){99}){99}展开9801个x；继续嵌套会很快越限，应在复制前拒绝。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def decompress(text,max_output=1000000):
    i=0
    def sequence(nested=False):
        nonlocal i
        chunks=[];size=0
        while i<len(text) and text[i]!=')':
            if text[i]=='(':
                i+=1;part=sequence(True)
                if i>=len(text) or text[i]!=')':raise ValueError("missing close")
                i+=1
                if i>=len(text) or text[i]!='{':raise ValueError("missing repeat")
                i+=1;start=i
                while i<len(text) and text[i] in '0123456789':i+=1
                if i==start or i>=len(text) or text[i]!='}':raise ValueError("invalid repeat")
                count=int(text[start:i]);i+=1
                if not 2<=count<=99:raise ValueError("repeat must be 2..99")
                if len(part)*count>max_output-size:raise ValueError("output limit")
                part=part*count
            else:
                if text[i] in '{}':raise ValueError("unexpected repeat syntax")
                part=text[i];i+=1
            size+=len(part)
            if size>max_output:raise ValueError("output limit")
            chunks.append(part)
        return ''.join(chunks)
    result=sequence()
    if i!=len(text):raise ValueError("unexpected close")
    return result

复杂度

输入C、展开L、深度h；当前中间字符串可能被每层重建，保守O(C+hL)时间与O(hL)临时存储上界。AST流式可接近O(C+L)，仍需O(h)解析状态。

易错点与追问

容易失分的边界

• 把{3}乘到整个已读前缀会重复外部a。
• 有输出上限不自动限制解析递归深度，需要另加深度上限或显式栈。

继续深挖

• 支持数字普通字符时，怎样明确只在{}内解析次数？
• 解压iterator如何用重复栈按需输出、不一次存L？