如何在Python中基于含begin/end标记的列表构建嵌套列表？

需要解析一个包含嵌套结构的数据，嵌套深度不固定，每层嵌套由begin和end标记，目标是构建保留原嵌套结构的列表。

示例输入：

input_list = [0, 'begin', 1, 2, 'begin', 3, 4, 'end', 5, 'end', 6]

期望输出：

[0, [1, 2, [3, 4], 5], 6]

尝试的递归代码：

input = [0, 'begin', 1, 2, 'begin', 3, 4, 'end', 5, 'end', 6]

def create_nest(items, nest):
    for i, item in enumerate(items):
        if item == 'begin':
            nest.append(create_nest(items[i+1:], []))
        elif item == 'end':
            return nest
        else:
            nest.append(item)

nested_list = []
create_nest(input, nested_list)

实际错误输出：

[0, [1, 2, [3, 4], 3, 4], 1, 2, [3, 4], 3, 4]

原递归函数的核心问题是：遇到begin触发递归后，外层的for循环不会停止，会继续遍历原列表中i+1位置的元素——但这些元素已经被递归函数处理过，导致重复添加。比如第一次递归返回子列表后，外层循环还会再次处理1、2等元素，最终造成数据重复。

方案1：改进递归（返回处理索引） #

让递归函数同时返回构建好的嵌套列表和已处理的索引位置，外层通过索引跳过已处理元素，避免重复遍历：

input_list = [0, 'begin', 1, 2, 'begin', 3, 4, 'end', 5, 'end', 6]

def create_nest(items):
    nest = []
    i = 0
    while i < len(items):
        item = items[i]
        if item == 'begin':
            # 递归获取子嵌套列表和子列表处理的元素个数
            sub_nest, idx = create_nest(items[i+1:])
            nest.append(sub_nest)
            # 跳过已处理的元素（包括当前begin和子列表所有元素）
            i += idx + 1
        elif item == 'end':
            # 返回当前嵌套列表和已处理的索引
            return nest, i
        else:
            nest.append(item)
            i += 1
    # 遍历完所有元素，返回最终结果
    return nest, len(items)

nested_list, _ = create_nest(input_list)
print(nested_list)

输出结果：

[0, [1, 2, [3, 4], 5], 6]

方案2：栈实现（迭代方式） #

用栈结构管理嵌套层级，逻辑更直观：

input_list = [0, 'begin', 1, 2, 'begin', 3, 4, 'end', 5, 'end', 6]

def create_nest(items):
    stack = []
    current = []
    for item in items:
        if item == 'begin':
            # 将当前层存入栈，新建空列表作为当前嵌套层
            stack.append(current)
            current = []
        elif item == 'end':
            # 将当前嵌套层加入父层，切换回父层继续处理
            parent = stack.pop()
            parent.append(current)
            current = parent
        else:
            current.append(item)
    return current

nested_list = create_nest(input_list)
print(nested_list)

输出结果：

[0, [1, 2, [3, 4], 5], 6]

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