將括號轉換爲不帶圓括號的等價條件

Question

我正在開發一個應用程序，用戶可以在其中添加條件到某些任務。

例如，他可以有條件的a，b，c，d和在最後它看起來方式將它們組合，如：

(a AND b) OR (c AND d)
OR
(a AND b AND c) or d
OR
(a AND !b) AND c OR !d

等

如何將這些條件轉換爲等價物，通過removi ng括號？

Answer 1

在布爾代數表達式的每個可以被轉換成等效的表達，沒有括號，僅使用AND，OR，和!（一元NOT）。

下面是一個簡單但低效的算法：

使用例如表達(a OR !b) AND c，

1. 建立一個真值表爲變量的真值的每一種組合：

   | a | b | c | (a OR !b) AND c | 
   | 0 0 0 | 0    | 
   | 0 0 1 | 1    | 
   | 0 1 0 | 0    | 
   | 0 1 1 | 0    | 
   | 1 0 0 | 0    | 
   | 1 0 1 | 1    | 
   | 1 1 0 | 0    | 
   | 1 1 1 | 1    | 
   

2. 對於表達式爲真的每個值集（最右邊一列中有1的每行），創建使用AND s和!的表達式僅針對該特定值集計算爲真。

   | a | b | c | (a OR !b) AND c | 
   | 0 0 0 | 0    | 
   | 0 0 1 | 1    | (!a AND !b AND c) 
   | 0 1 0 | 0    | 
   | 0 1 1 | 0    | 
   | 1 0 0 | 0    | 
   | 1 0 1 | 1    | (a AND !b AND c) 
   | 1 1 0 | 0    | 
   | 1 1 1 | 1    | (a AND b AND c) 
   

3. 用OR加入表達式。

   (!a AND !b AND c) OR (a AND !b AND c) OR (a AND b AND c) 
   

4. 由此產生的表達式很少最小化，所以您可能想在之後應用一些最小化技術。

   (!a AND !b AND c) OR (a AND !b AND c) OR (a AND b AND c) 
   = 
   (!a AND !b AND c) OR (a AND c) 
   = 
   (!b AND c) OR (a AND c) 
   

噹噹！

重要的是要注意，在步驟1中建立真值表是一個O（2^n）操作（以變量數目），這是非常糟糕的。對於非平凡數量的變量，您可能會想要使用不同的技術。這種算法的主要優點在於它能夠非常明顯地將任何表達式轉換成您想要的形式。

編輯：要清楚，如果您使用正常優先規則，則可以在最終表達式中刪除括號。

Answer 2

您可以使用布爾代數的各種properties來幫助簡化表達式，但是您可能無法擺脫所有括號。括號對於某些表達式是必需的，因爲NOT，AND和OR沒有操作順序。因此，如果您無法重新排列表達式以從左向右閱讀，則需要使用括號。

Answer 3

不完全確定轉換爲非括號的等價物的動機是什麼，所以我認爲它意味着您正試圖爲用戶建立表達能力（即表達式語言），以便用戶溝通其期望的任務條件到您的應用程序。

您不能刪除括號的需要，並且仍然支持具有正常運算符優先規則的正常中綴表達式語言中的任意複雜表達式。

你有幾個選擇，我想：

1. 支持括號。 （他們並不真的很難解析。）

2. 使用另一種相對標準或衆所周知的不使用括號的表達式語言，如Reverse Polish Notation，又名RPN。見http://en.wikipedia.org/wiki/Reverse_Polish_notation。 RPN使用後綴符號，允許用戶通過定位和疊加而不是使用圓括號完全控制運算符優先級。這需要仔細（重新）訂購操作數和操作。 （沒有免費的午餐。）

3. 將語言的表現力限制爲某些不需要更正常（中綴）語言（具有運算符優先級）語言的括號的特定模式。

最後，如果你有一個用戶界面，幫助用戶編寫自己的表達式（而不是文本語言），你可以這樣做＃2上方，然後使用用戶定義的子表達式來表示運營商訂單優先順序不需要括號。基本上你的用戶界面將幫助他們建立一個表達樹。

最後，如果您的問題是如何去除括號以執行表達式，這更像是代碼生成問題。再次，RPN的堆棧可能很有用。或者，您可以將（可能包含括號的）表達式轉換爲通過附加（在編譯器術語，臨時）變量中明確連接的單個迷你（例如三個操作數）語句。例如，(a + b) * c變爲t1 = a + b，然後是final-result = t1 * c。