expression - 使用扭曲将表达式转换为合取范式

Question

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

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

这对于编程当然不是很舒服。所以我想做一个可以解析任意表达式并将它们转换为这种正常形式的小包装器。喜欢:

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

会被翻译成类似的东西:

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

我可以使用 Irony 将表达式解析为树图书馆。现在我需要对其进行标准化，但我不知道如何......哦，还有，这里有一个转折点:

最后的表达式可能不包含 不是 运算符(operator)。但是，我可以通过用逆运算符替换运算符来对单个项进行逆运算。所以，这是可以的:(not A or not B) AND (not C or not D)但这不是:not (A or B) and not (C or D)

我想让表达式尽可能简单，因为它会被翻译成一个几乎完全相同的 SQL WHERE 语句，所以一个复杂的语句很可能会降低执行速度。

Answer 1

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

第一次迭代:通过遍历树并使用德摩根定律 (wikipedia link) 去除您的 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

之后你应该完成。