构建支持任意深度递归解析的 n 叉表达式树

本文介绍如何通过递归下降解析器将嵌套括号表达式（如 `"(", "a", "&", "b", ")", "|", "c"`）准确构建成多叉树结构，自动处理 5 层甚至更深的嵌套，并避免手动拼接 `.nodes[x].nodes[y]` 等易错路径。

在构建逻辑表达式树（如 & 表示 AND、| 表示 OR）时，核心挑战并非节点存储本身，而是如何让程序自动“感知”当前解析深度，并在正确层级上创建/插入子节点。手动用 a.nodes[0].nodes[1].add_node(...) 显式访问多级路径不仅脆弱（索引越界、结构变更即崩溃），更违背树的抽象本质——树的结构应由语义驱动，而非硬编码路径。

解决方案是采用递归下降解析（Recursive Descent Parsing）：将每个括号对 (...) 视为一个独立子表达式单元，其内部结构由递归调用自身完成；运算符（& / |）则自然升格为当前子树的根节点，其操作数成为子节点。该方法天然支持任意嵌套深度，无需预判层级数。

以下是一个精简、健壮的实现：

class Node:
    def __init__(self, val, nodes=None):
        self.val = val
        self.nodes = nodes or []

    def __repr__(self):
        return f"Node({self.val}): {self.nodes}"

def expr_to_tree(expr):
    it = iter(expr)  # 使用迭代器避免索引管理

    def get_operand():
        token = next(it, None)
        if token in (")", "&", "|", None):
            raise ValueError(f"Expected operand, got {repr(token)}")
        return expr_to_tree(expr) if token == "(" else Node(token)

    def get_expr(terminal=None):
        # 解析首个操作数（可能是原子值或子表达式）
        left = get_operand()

        # 尝试读取后续运算符
        op = next(it, None)
        if op not in ("&", "|"):
            # 无运算符：单节点表达式，直接返回
            if op != terminal:
                raise ValueError(f"Unexpected token {repr(op)}, expected {repr(terminal)}")
            return left

        # 有运算符：构造以该运算符为根的子树
        root = Node(op, [left])
        # 持续追加右侧操作数，直到遇到终止符（如 ')' 或结束）
        while True:
            right = get_operand()
            root.nodes.append(right)
            next_token = next(it, None)
            if next_token == terminal or next_token is None:
                return root
            elif next_token in ("&", "|"):
                if next_token != op:
                    raise ValueError(f"Mixed operators '{op}' and '{next_token}' not allowed")
                # 继续同级追加
                continue
            else:
                raise ValueError(f"Unexpected token {repr(next_token)} after operand")

    return get_expr()

✅ 关键设计说明：get_operand() 处理两种情况：遇到 "(" 则递归调用 expr_to_tree() 构建子树；否则创建叶子节点。get_expr() 负责识别运算符并聚合同级操作数，自动形成 Node('&'): [Node(A), Node(B), ...] 结构。迭代器 it 全局共享，确保每个递归层级按序消费输入，无需传递索引或手动切片。

使用示例：

complicated_expr = ["(", "MORE", "&", "(", "COMPLICATED", "|","(","EXPRESSION","&","PRESENTING",")","|", "MANY", ")", ")", "|", "(", "DEEPER", "&", "(", "LEVELS", "|", "FOR", "|", "TREE", ")",")"]

tree = expr_to_tree(complicated_expr)
print(tree)
# 输出结构清晰，自动嵌套，无需任何 .nodes[0].nodes[1]... 手动寻址

⚠️ 注意事项：

• 此解析器要求表达式语法合法（括号匹配、运算符不混用），生产环境建议增加语法校验或错误恢复逻辑；
• 若需支持优先级（如 & 优先于 |），需扩展为多层 get_expr()（如 get_or_expr() → get_and_expr() → get_operand()）；
• 树节点未提供查找/修改接口，如需动态增删，应在 Node 类中补充 find() 或 insert_at_path() 方法（路径可用元组 (0,1,2) 表示）。

总结：面对深度不确定的 n 叉树构建，放弃“路径拼接”思维，拥抱递归解析——它让代码与问题结构对齐，将复杂度从开发者转移给调用栈，是处理嵌套语法的通用范式。