如何递归构建并操作任意深度的 n 叉表达式树

本文介绍一种基于迭代器与递归下降解析的通用方法，将嵌套括号表达式（如 `["(", "a", "&", "b", ")", "|", "c"]`）准确转换为 n 叉树结构，并支持任意深度的节点访问与子节点动态添加。

在处理复杂逻辑表达式（如 ["(", "MORE", "&", "(", "COMPLICATED", "|", "(", "EXPRESSION", "&", "PRESENTING", ")", "|", "MANY", ")", ")", "|", "(", "DEEPER", "&", "(", "LEVELS", "|", "FOR", "|", "TREE", ")", ")"]）时，传统手动链式访问（如 tree.nodes[0].nodes[1].nodes[2].add_node(...)）极易出错且无法扩展。根本解法不是“拼接字符串形式的 .nodes[x]”，而是放弃硬编码路径，改用递归遍历 + 上下文感知的节点构造。

以下是一个精简、健壮且可读性强的实现方案：

✅ 核心设计原则

• 单次线性扫描：使用 iter() 创建消耗型迭代器，避免索引管理与重复遍历；
• 递归下降解析（Recursive Descent Parsing）：遇到 "(" 进入子表达式递归，遇到 ")" 或运算符边界自然回溯；
• 运算符提升为父节点：同级连续的 & 或 | 操作数均作为其子节点，天然形成 n 叉结构；
• 无状态、无副作用：每个递归调用只负责解析一段合法子表达式，返回对应子树根节点。

? 重构后的树节点类（极简可靠）

class Node:
    def __init__(self, val, nodes=None):
        self.val = val
        self.nodes = nodes or []  # 子节点列表，支持 0~n 个

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

⚠️ 注意：原 NonBinTree.add_child_node、make_parent_node 等方法在递归构建中完全冗余——构建即结构化，无需后期“打洞”修改。若需后续动态插入，应提供独立的 find_by_path() 或 traverse_with_context() 辅助函数（见文末扩展）。

? 表达式到树的递归解析器

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:
            next_token = next(it, None)
            if next_token == terminal or next_token in ("&", "|"):
                # 遇到终止符或新运算符，结束当前层级
                if next_token != terminal and next_token != op:
                    # 新运算符 ≠ 当前运算符 → 语法错误（如 A & B | C 不被允许，需括号明确）
                    raise ValueError(f"Mixed operators: {op} followed by {next_token}")
                # 将 next_token “推回”给上层处理（通过重新构造迭代器不可行，故用异常/返回值协调）
                # 更佳做法：此处直接返回 root，并让调用方处理 next_token
                # → 改用带返回值的解析器（见下方改进版）
                break
            elif next_token == ")":
                if terminal != ")":
                    raise ValueError("Unmatched closing parenthesis")
                break
            else:
                # 原子操作数
                root.nodes.append(Node(next_token))
        return root

    # 主入口：解析整个表达式，无预设终止符
    return get_expr()

但上述版本在运算符切换处略显笨重。更优雅的工业级写法如下（推荐）：

✅ 推荐实现：清晰分层 + 运算符统一处理

def expr_to_tree(expr):
    it = iter(expr)

    def parse_atom():
        tok = next(it, None)
        if tok == "(":
            node = parse_expr()
            if next(it, None) != ")":
                raise ValueError("Missing closing ')'")
            return node
        elif tok in ("&", "|", ")", None):
            raise ValueError(f"Unexpected token {repr(tok)} in atom position")
        return Node(tok)

    def parse_expr():
        # 至少一个操作数
        children = [parse_atom()]
        # 尝试读取运算符
        op_tok = next(it, None)
        if op_tok not in ("&", "|"):
            # 无运算符 → 返回单节点
            return children[0] if len(children) == 1 else Node("ERROR", children)

        # 有运算符 → 构建 n 叉根节点
        root = Node(op_tok)
        # 添加已解析的第一个操作数
        root.nodes.append(children[0])
        # 继续解析后续操作数（同级）
        while True:
            try:
                next_tok = next(it, None)
                if next_tok == ")":
                    # 结束当前子表达式
                    return root
                elif next_tok in ("&", "|"):
                    if next_tok != op_tok:
                        raise ValueError(f"Mixed operators: {op_tok} then {next_tok}")
                    # 同运算符，继续添加操作数
                    root.nodes.append(parse_atom())
                else:
                    # 原子值，直接加入
                    root.nodes.append(Node(next_tok))
            except StopIteration:
                return root

    return parse_expr()

▶ 使用示例

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

tree = expr_to_tree(complicated_expr)
print(tree)

输出结构清晰反映嵌套逻辑：

Node(|): [
  Node(&): [
    Node(MORE): [],
    Node(|): [
      Node(COMPLICATED): [],
      Node(&): [Node(EXPRESSION): [], Node(PRESENTING): []],
      Node(MANY): []
    ]
  ],
  Node(&): [
    Node(DEEPER): [],
    Node(|): [Node(LEVELS): [], Node(FOR): [], Node(TREE): []]
  ]
]

? 关键总结与建议

• 拒绝“拼路径字符串”：.nodes[0].nodes[1]... 是反模式；深度应由递归自然承载，而非手动展开。

• 运算符决定树形：& 和 | 天然对应 n 叉内节点，无需二叉化或额外标记。

• 括号即递归边界：( 触发子调用，) 触发返回，完美映射语法层级。

• 后续动态操作？ 若需运行时向某节点插入子节点，应实现路径定位函数：

  def find_node_by_path(root, path):
      # path: e.g., [0, 1, 2] → root.nodes[0].nodes[1].nodes[2]
      node = root
      for idx in path:
          if not (0 <= idx < len(node.nodes)):
              raise IndexError(f"Path {path} out of bounds at index {idx}")
          node = node.nodes[idx]
      return node
  
  # 示例：向第 0 个子节点的第 1 个子节点添加新叶子
  target = find_node_by_path(tree, [0, 1])
  target.nodes.append(Node("DYNAMIC_CHILD"))

此方法彻底解耦“构建”与“操作”，兼顾表达力、可维护性与任意深度支持，是处理嵌套表达式树的工程优选方案。