算法從布爾表達式中刪除多餘的括號

Question

我有一個前綴表示法的布爾表達式。可以說它是or and A B or or C D E。當我將它轉換爲中綴符號時，我會以 ((A and B) or ((C or D) or E))結束。我想把它縮小到(A and B) or C or D or E。我應該減少中綴表示還是實際上從前綴表示法中減去等式更容易？我應該使用什麼算法？

Answer 1

可以在表達式X % (X1 ? X2 ? .. ? Xn) % X(n+1)中刪除候選項，其中Xi是加括號的表達式或布爾值「？」和「％」是運算符當且僅當每個「？」運算符優先級高於或等於「％」運算符。

對於中綴記法，您會發現內層表達式，檢查是否可以刪除括號，保存結果，處理父表達式並繼續，直到完成所有括號檢查。

這變成了映射問題。後綴表示法使括號清除變得容易。前綴，中綴和後綴符號之間的轉換很簡單。