将表达式转换为带有扭曲的合取范式

Question

我有一个必须与之交互的库，它基本上充当数据源。 检索数据时，我可以将特殊的“过滤表达式”传递给该库，稍后将其转换为 SQL WHERE 部分。 这些表达方式非常有限。 它们必须是合取范式。 喜欢：

(A or B or C) and (D or E or F) and ...

这对于编程来说当然不太舒服。 所以我想制作一个小包装器，它可以解析任意表达式并将它们转换为这种正常形式。 Like:

(A and (B or C) and D) or E

会被翻译成类似的东西：

(A or E) and (B or C or E) and (D or E)

我可以使用 Irony 库将表达式解析为树。 现在我需要对其进行标准化，但我不知道如何...哦，还有一个问题：

• 最终的表达式可能不包含 NOT 运算符。 但是，我可以通过用逆运算符替换运算符来反转各个项。 所以，这是可以的：
  
  （不是 A 或不是 B）AND（不是 C 或不是 D）
  
  但这不是：
  
  not (A or B) and not (C or D)
  
  
• 我想让表达式尽可能简单，因为它将被转换为几乎相同的 SQL WHERE 语句，因此复杂的语句很可能会降低执行速度。

Answer 1

我会在树上使用两次迭代，尽管一次迭代可能是可能的。

第一次迭代：通过遍历树并使用德摩根定律来消除 NOT 节点 (维基百科链接）并删除适用的双重否定。

第二次迭代（NOT 现在仅直接位于叶节点之前）
遍历你的树：

Case "AND NODE":
    fine, inspect the children
Case "OR NODE":
    if there is a child which is neither a Leaf nor a NOT node
        apply the distributive law.
        start from parent of current node again
    else
        fine, inspect children

之后你就应该完成了。