我有一个必须与之交互的库,它基本上充当数据源。检索数据时,我可以将特殊的“过滤表达式”传递给该库,稍后将其转换为 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 http://www.codeplex.com/irony图书馆。现在我需要将其标准化,但我不知道如何......哦,还有,这是一个转折点:
- 最终的表达式可能不包含NOT操作员。但是,我可以通过用逆运算符替换运算符来反转各个项。所以,这是可以的:
(not A or not B) AND (not C or not D)
但这不是:
not (A or B) and not (C or D)
- 我希望表达式尽可能简单,因为它将被转换为几乎相同的 SQL WHERE 语句,因此复杂的语句很可能会降低执行速度。
我会在树上使用两次迭代,尽管一次迭代可能是可能的。
第一次迭代:通过遍历树并使用德摩根定律来消除 NOT 节点(维基百科链接 http://en.wikipedia.org/wiki/De_Morgan%27s_laws) 并在适用的情况下删除双重否定。
第二次迭代(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
之后你就应该完成了。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)