將表達式轉換爲具有扭曲的連接正常形式

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庫樹。現在我需要正常化，但我不知道怎麼......哦，還有，這裏的扭曲：

• 最終的表達可能不包含NOT運營商。但是，我可以通過用逆運算符替換運算符來反轉各個項。所以，這是確定：
  
  (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）並在任何適用的情況下移除雙重否定來消除您的非節點。

第二次迭代（在現在不只是直接葉節點之前） 通過你的樹：

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 

之後，你應該做的。