嵌套括号压缩字符串解析咨询：寻求可行的解压算法

给定以下压缩格式的代码字符串：

GMZDCOR[R[G[A5D[C,E,K,M,O],E5D[K,M,O],I5D[C,E,K,M,O]],HI[4Q,YT[A,C]]],SHI[2[A,Q],3[A,Q],4A,Y[Q,T[G,I]],Z[A,Q]],THI[2A,3Q,4[A,Q],Y[Q,TA],Z[A,Q]],UHI[YQ,ZA],VHI[2A,3Q,4[A,Q],Y[Q,T[A,C]],Z[A,Q]],WHI[3Q,4A,Y[Q,T[C,E]],ZA],XHI[2[A,Q],ZQ],YHI[2[A,Q],YQ,Z[A,Q]],ZHI[2Q,3[A,Q],YQ,ZA]]

需要将其解压为如下形式的数组：

[GMZDCORRGA5DC, GMZDCORRGA5DE, GMZDCORRGA5DK, GMZDCORRGA5DM, ...etc]

尝试过基础拆分方法，但因存在嵌套括号无法处理，请问是否有成熟算法可解决此类问题？

成熟解决方案：递归解析/栈模拟递归 #

这类带嵌套括号的组合压缩，最可靠的处理方式是通过递归解析或者栈模拟递归逻辑，核心是管理嵌套层级，逐层拆解子结构并拼接前缀，最终生成所有组合项。

具体处理逻辑 #

1. 层级上下文管理

   • 遇到[时，把当前已拼接的前缀字符串和当前收集的子项列表存入栈，重置当前前缀和子项列表，开始处理括号内的内容；
   • 遇到]时，弹出栈顶的上下文（上层前缀+上层子项列表），将当前括号内拆解出的所有子项分别与上层前缀拼接，生成新的子项列表，作为当前层级的结果返回给上层；
   • 遇到,时，把当前已收集的字符串作为独立子项存入当前层级的子项列表，重置当前字符串；
   • 普通字符直接追加到当前字符串。

2. 组合展开规则
   比如处理A5D[C,E,K]时，先将括号内的C、E、K分别与前缀A5D拼接，得到A5DC、A5DE、A5DK；再将这些结果与更上层的前缀（如GMZDCORRG）拼接，得到最终的GMZDCORRGA5DC这类完整项。

示例实现代码（Python） #

def decompress_compressed_str(s):
    stack = []
    current_prefix = ""
    current_items = []
    
    for char in s:
        if char == '[':
            # 保存当前上下文到栈
            stack.append((current_prefix, current_items))
            current_prefix = ""
            current_items = []
        elif char == ']':
            # 弹出上层上下文，拼接生成新项
            prev_prefix, prev_items = stack.pop()
            # 把剩余的当前前缀加入子项
            if current_prefix:
                current_items.append(current_prefix)
                current_prefix = ""
            # 所有子项和上层前缀拼接
            combined_items = [prev_prefix + item for item in current_items]
            current_items = combined_items
            current_prefix = ""
        elif char == ',':
            # 保存当前前缀为子项
            if current_prefix:
                current_items.append(current_prefix)
                current_prefix = ""
        else:
            # 追加普通字符到当前前缀
            current_prefix += char
    # 处理最后剩余的内容
    if current_prefix:
        current_items.append(current_prefix)
    
    return current_items

# 测试示例
compressed_str = "GMZDCOR[R[G[A5D[C,E,K,M,O],E5D[K,M,O],I5D[C,E,K,M,O]],HI[4Q,YT[A,C]]],SHI[2[A,Q],3[A,Q],4A,Y[Q,T[G,I]],Z[A,Q]],THI[2A,3Q,4[A,Q],Y[Q,TA],Z[A,Q]],UHI[YQ,ZA],VHI[2A,3Q,4[A,Q],Y[Q,T[A,C]],Z[A,Q]],WHI[3Q,4A,Y[Q,T[C,E]],ZA],XHI[2[A,Q],ZQ],YHI[2[A,Q],YQ,Z[A,Q]],ZHI[2Q,3[A,Q],YQ,ZA]]"
result = decompress_compressed_str(compressed_str)
print(result[:5])  # 输出前5个项：['GMZDCORRGA5DC', 'GMZDCORRGA5DE', 'GMZDCORRGA5DK', 'GMZDCORRGA5DM', 'GMZDCORRGA5DO']

关键注意点 #

• 确保栈的状态正确保存和恢复，避免嵌套层级混乱；
• 处理无括号的纯字符串项（如4A），直接作为独立子项；
• 逗号分隔符的处理要及时，避免子项遗漏或合并错误。

内容的提问来源于stack exchange，提问作者Hazem Mohamed