如何选择合适的数据结构存储可返回布尔值的逻辑表达式

针对你转换后的布尔表达式（term1 or (term2 and term3) and not (term4 and term5)），以下几种数据结构都能满足存储并返回布尔值的需求，各有适用场景：

1. 抽象语法树（AST） #

这是处理逻辑/算术表达式最常用的结构，完全贴合表达式的层级逻辑。

• 结构设计：
  • 每个节点分为两类：操作数节点（比如term1，存储该term对应的布尔值，或者指向其值的引用）和操作符节点（or/and/not，其中and/or有左右两个子节点，not只有一个子节点）。
  • 以你的表达式为例，AST的结构大概是：
    • 根节点：and
    • 左子节点：or（左子是term1，右子是and节点，对应term2和term3）
    • 右子节点：not（子节点是and节点，对应term4和term5）
• 求值方式：递归遍历树，叶子节点返回自身的布尔值，内部节点根据操作符对其子节点的结果进行计算（比如and节点返回左子结果 && 右子结果）。
• 优点：直观对应表达式结构，容易扩展新的操作符，方便做表达式的修改、分析。

2. 后缀表达式（逆波兰表达式） #

适合快速求值的线性结构，用栈就能完成计算。

• 结构设计：把表达式转换成空格分隔的线性列表（数组/链表），比如你的表达式转成后缀是：term1 term2 term3 and or term4 term5 and not and。每个元素要么是操作数，要么是操作符。
• 求值方式：用一个栈处理：
  1. 遍历每个元素，遇到操作数就压入栈；
  2. 遇到操作符时，弹出对应数量的元素（not弹1个，and/or弹2个），用操作符计算结果，再把结果压回栈；
  3. 遍历结束后，栈顶元素就是最终布尔值。
• 优点：结构简单，求值逻辑无递归，性能高，适合对性能敏感的场景。

3. 面向对象的节点类模型 #

本质是AST的面向对象实现，可读性和可维护性更强。

• 结构设计：定义不同的类来表示不同类型的节点：
  • OperandNode：存储term的标识和对应的布尔值，提供evaluate()方法直接返回该值；
  • AndNode/OrNode：包含两个子节点（left和right），evaluate()方法返回left.evaluate() && right.evaluate()（或||）；
  • NotNode：包含一个子节点，evaluate()方法返回!child.evaluate()。
• 求值方式：直接调用根节点的evaluate()方法，自动递归计算所有子节点的结果。
• 优点：代码可读性高，符合面向对象设计，方便后续扩展和维护。

4. 嵌套列表（简单场景快速实现） #

如果表达式复杂度不高，也可以用嵌套列表来快速表示，比如你的表达式可以写成：

["and", ["or", "term1", ["and", "term2", "term3"]], ["not", ["and", "term4", "term5"]]]

• 求值方式：写一个递归函数，遍历列表：如果是操作数就返回对应布尔值，如果是操作符就取后面的元素作为子表达式计算。
• 优点：实现成本极低，不需要定义额外结构，适合简单、临时的场景；缺点是可读性差，复杂表达式容易出错。

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