根据左括号位置生成合法括号配对编码的实现问题

给定有效括号序列中所有左括号的索引列表（例如输入[0,1,2,5]），需要生成每个括号对应的配对编号序列（例如输出[0,1,2,2,1,3,3,0]）。

实现思路 #

要搞定这个问题，我们可以利用栈的后进先出特性来匹配最近的未配对左括号，具体步骤如下：

• 确定结果列表总长度：左括号数量为n，则总长度为2n（有效括号序列左右括号数量相等）。
• 先给所有左括号位置填充对应的编号（从0开始依次递增）。
• 用栈跟踪未匹配的左括号编号：遍历序列时，左括号编号压栈；遇到右括号时，弹出栈顶编号（对应最近未匹配的左括号），将该编号填充到当前右括号位置。

完整代码实现 #

def arc_representation(left_paren_indices):
    left_count = len(left_paren_indices)
    total_length = 2 * left_count
    result = [0] * total_length
    
    # 先填充左括号的对应编号
    for num, pos in enumerate(left_paren_indices):
        result[pos] = num
    
    stack = []
    # 遍历每个位置，处理右括号的配对编号
    for i in range(total_length):
        if i in left_paren_indices:
            # 当前是左括号，把编号压入栈
            stack.append(result[i])
        else:
            # 当前是右括号，弹出最近未匹配的左括号编号并填充
            matching_num = stack.pop()
            result[i] = matching_num
    
    return result

# 测试示例
print(arc_representation([0,1,2,5]))  # 输出: [0,1,2,2,1,3,3,0]

代码说明 #

• 初始化阶段：先遍历左括号索引列表，给每个左括号位置分配递增的编号。
• 栈的使用：栈完美适配“匹配最近未配对左括号”的需求，每次遇到右括号时，栈顶元素就是它对应的左括号编号，弹出后填充到当前位置即可。
• 测试示例验证：输入[0,1,2,5]对应的括号序列是((()))()，每个括号的配对编号和示例输出完全一致。

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