本文介绍如何通过递归下降解析器将嵌套括号表达式（如 `"(", "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 叉树构建，放弃“路径拼接”思维，拥抱递归解析——它让代码与问题结构对齐，将复杂度从开发者转移给调用栈，是处理嵌套语法的通用范式。
