主題
題目連結：
題目意譯：
你被給定一個合法的布林表達式 expression 其為一字串由字元 '1' 、 '0' 、 '&'（按位元（Bitwise） AND 運算）、 '|'（按位元 OR 運算）、 '(' 和 ')' 所組成。
例如， "()1|1" 和 "(1)&()" 不是合法的，而 "1" 、 "(((1))|(0))" 和 "1|(0&(1))" 為合法表達式。
回傳改變表達式之最終值所需最小成本。
例如，如果 expression = "1|1|(0&0)&1"，其值為 1|1|(0&0)&1 = 1|1|0&1 = 1|0&1 = 1&1 = 1。我們想要執行一些操作使得新的表達式之值為 0。
改變一表達式的最終值之成本為執行於表達式之操作數。操作種類描述為以下：
將一個 '1' 變為一個 '0'。
將一個 '0' 變為一個 '1'。
將一個 '&' 變為一個 '|'。
將一個 '|' 變為一個 '&'。
注：'&' 運算順序並沒有優先於 '|'。這裡是先運算括號內容，然後再由左至右計算。
限制：
1 ≦ expression.length ≦ 10 ^ 5
expression 只包含 '1' 、 '0' 、 '&' 、 '|' 、 '(' 和 ')'
所有括號皆正確地配對。
不會有空括號（即："()" 不是 expression 的一個子字串）。
範例測資：
範例 1：
輸入： expression = "1&(0|1)"
輸出： 1
解釋： 我們可以執行 1 次操作使 "1&(0|1)" 變為 "1&(0&1)" ，藉由著將一個 '|' 改為一個 '&'。
新的表達式之值為 0。
範例 2：
輸入： expression = "(0&0)&(0&0&0)"
輸出： 3
解釋： 我們可以執行 3 次操作使 "(0&0)&(0&0&0)" 變為 "(0|1)|(0&0&0)"。
新的表達式之值為 1。
範例 3：
輸入： expression = "(0|(1|0&1))"
輸出： 1
解釋： 我們可以執行 1 次操作使 "(0|(1|0&1))" 變為 "(0|(0|0&1))"。
新的表達式之值為 0。
解題思維：
先將原本的布林表達式從中序運算式轉為後序運算式（如這題之作法），然後在邊轉換的時候順便求其值以及執行動態規劃（Dynamic Programming）的遞推之動作（少數需要把 DP 的操作直接套用在堆疊本身上的情況）。
而我們的 DP 用堆疊之每個位置儲存的是一數對 (C0, C1) ，其中 C0 代表著將現在的位置之值要轉成 0 需要多少次操作、C1 同理，為當前位置轉成 1 所需操作數。而當我們遇到 expression 中的數字時，如果 '1' 我們就推 (1, 0) 到堆疊頂端；如果是 '0' 則推 (0, 1) 到堆疊頂端。
因此當我們在計算例如 0 & 1 之值時，此時會將堆疊最頂端的兩個元素合併成一個元素，因此我們按照平常求得運算式值之後便可以得到整體要轉成 0 和整體要轉成 1 的最少操作數（假設最終數對為 (C0', C1')）。如果原本的運算式值為 0 ，而我們要將其反轉，因此所求為 C1'；反之，所求應為 C0'。
令 A 、 B 依序為堆疊頂端第二個元素以及頂端元素。因此我們可以得到兩個數對 (AC0, AC1) 以及 (BC0, BC1) ，前者代表運算式 A 要轉成 0 和轉成 1 所需最少操作數，後者也是同理。
因此當現在碰到的是 A | B 時，則對於這個運算式本身其 (C0, C1) 數對之值應是
C0 = min(AC0 + BC0, AC0 + BC1 + 1, AC1 + BC0 + 1)
（代表要在 0 | 0 、 0 & 1 、 1 & 0 之中選擇操作數最小的）
C1 = min(AC1 + BC1, AC0 + BC1, AC1 + BC0)
（代表要在 1 & 1 、 0 | 1 、 1 | 0 之中選擇操作數最小的）
而當是碰到 A & B 時，則對於這個運算式本身其 (C0, C1) 數對之值應是
C0 = min(AC0 + BC0, AC0 + BC1, AC1 + BC0)
（代表要在 0 | 0 、 0 & 1 、 1 & 0 之中選擇操作數最小的）
C1 = min(AC1 + BC1, AC0 + BC1 + 1, AC1 + BC0 + 1)
（代表要在 1 & 1 、 0 | 1 、 1 | 0 之中選擇操作數最小的）
計算完之後就將 (C0, C1) 推到堆疊頂端，繼續著分析運算式的旅程。當分析結束後，就按照上面的方式去回傳 C0' 或是 C1' 即可得到所求最小操作數。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
