带谓词的布尔表达式树？

Question

我正在尝试设计一个表达式树构建器，它可用于构建一个表达式树，该表达式树可以使用提供的上下文（哈希映射）进行惰性评估。所需的运算符集是 AND/OR/NOT、<、<=、>、>=、=,!=,in_range（含或不含）。表达式树必须支持短路（不计算超过最终结果所需的数量）。评估结果为真或假。在我的例子中，哪些节点必须是中间节点，哪些是叶子节点？我想 AND/OR/NOT是中间词和谓词(<,<=,>,>=,=,!=,in_range) 会是叶节点吗？或者每个谓词将表示为一个子树？

Answer 1

我最近为我的雇主做了这件事。不过，我还没有和他们谈过开源的问题，所以我不能给你看任何代码。不过我可以给你一些建议。

• 如果你有量级比较，那么一些子表达式不能有布尔结果：如果你写a <= b，那么a和b是数字或字符串。你可能还需要数学，所以你可以写 a <= b+1，等等。我的解决方案是：
  • 只有原子是叶子（a、b、1 等）
  • 解析表达式或子表达式会生成一个typed 编译表达式对象。它要么已知会产生布尔值、字符串或数字结果，要么可能会产生任何结果。例如，a < b 会产生布尔结果。
  • 用作谓词的表达式是无效的，除非已知它会产生布尔结果。
• 由于您将任意哈希图作为输入，因此您需要考虑如何处理空值。我建议你按照 SQL 的方式去做（艰苦的思考已经完成），并在你的语言中添加 IS NULL 和 IS NOT NULL。