Learning Objectives
- 用堆疊檢查三種括號是否配對，並找出還缺少哪些右括號
- 說明中序、後序運算式的差別，以及後序運算式為什麼不需要括號
- 用調度場演算法把中序運算式轉成後序，說明運算子優先順序、左結合與括號怎麼處理
- 用堆疊計算後序運算式，分清楚先 pop 的是右邊的運算元，並偵測錯誤的運算式
- 用一個數字堆疊和一個運算子堆疊直接計算中序運算式
「最後放進去的最先處理」的問題
堆疊（stack）只能從一端（頂端，top）放入和取出：最後 push 的元素最先被 pop，叫做後進先出（LIFO）。它的實作很簡單，用動態陣列的尾端當頂端就好，push 和 pop 都是 O(1)：
| 語言 | 這一課的寫法 | push | pop | 看頂端 |
|---|---|---|---|---|
| Python | list |
st.append(x) |
st.pop() |
st[-1] |
| C++ | vector |
st.push_back(x) |
st.pop_back() |
st.back() |
| Java | ArrayList |
st.add(x) |
st.remove(st.size() - 1) |
st.get(st.size() - 1) |
C++ 另有 std::stack，Java 常用 ArrayDeque 的 push／pop；這一課用動態陣列，是為了讓動畫裡的堆疊都畫成「右邊是頂端」。
什麼時候需要堆疊？當問題有巢狀結構，越晚開始的部分要越早結束：括號 { [ ( ) ] }、函式呼叫（最後呼叫的函式最先回傳）、編輯器的「復原」。這一課看三個經典應用：括號配對、把運算式轉成後序、計算運算式。它們都是編譯器與計算機程式裡實際在用的做法。
這一課的每個範例都有 Python、C++、Java 三種寫法，可以用動畫上方的按鈕切換；三種寫法的輸出完全相同。
括號配對：遇到右括號時，該配的是最近的左括號
程式碼編輯器會在你少打一個右括號時提醒你，還能告訴你缺的是什麼。規則是：
- 從左到右讀，不是括號的字元跳過
- 左括號
( [ {就 push - 右括號
) ] }：堆疊頂端必須是同一種左括號，是就 pop（配成一對）；堆疊是空的或種類不同就是錯誤 - 讀完時堆疊裡剩下的左括號都沒有關上；從頂端開始，依序補上對應的右括號，就是缺少的部分
範例用一個字串 P = "()[]{}" 記住括號的對應：在 P 裡的位置是偶數就是左括號，它的下一個字元是對應的右括號；是奇數就是右括號，前一個字元是對應的左括號。
找不到（位置是 -1）表示不是括號。
括號配對：找出缺少的右括號
第一個字串配對正確，讀完時堆疊是空的。第二個字串讀到 ) 時，頂端是 [，種類不同，所以位置 5 的 ) 配不上。第三個字串讀完時堆疊裡還有 { [ (，從頂端開始補，缺的是 )]}：補的順序和左括號出現的順序剛好相反。
中序與後序運算式
我們平常寫的 3 + 4 * 2 叫中序（infix）運算式：運算子放在兩個運算元中間。中序要靠兩件事才能確定計算順序：
- 優先順序：
*、/比+、-先算，所以3 + 4 * 2是 3 + 8 - 結合性：同一級的運算子由左往右算（左結合），所以
8 - 3 - 2是 (8 - 3) - 2 = 3，不是 8 - (3 - 2) = 7 - 想改變順序就要加括號：
(3 + 4) * 2
後序（postfix）運算式把運算子放在兩個運算元後面，也叫逆波蘭表示法（Reverse Polish Notation）：
| 中序 | 後序 |
|---|---|
3 + 4 * 2 |
3 4 2 * + |
(3 + 4) * 2 |
3 4 + 2 * |
8 - 3 - 2 |
8 3 - 2 - |
後序運算式不需要括號、也不需要優先順序：從左到右讀，每遇到一個運算子，就拿它前面最近的兩個值來算。這個性質讓電腦很好計算，許多編譯器與虛擬機器（例如 Java 的位元組碼）執行運算式時，就是這種「先放運算元、再做運算」的順序。
所以計算一個中序運算式通常分兩步：先轉成後序，再計算後序。兩步都用堆疊。
中序轉後序：運算子先在堆疊裡等
轉換的方法叫調度場演算法（shunting-yard algorithm），由 Edsger Dijkstra 在 1961 年發表，名稱來自鐵路調車場：數字直接開到輸出，運算子先開進側線（堆疊）等候。
從左到右讀每個符號：
| 讀到 | 動作 |
|---|---|
| 數字 | 直接輸出 |
運算子 op |
只要頂端是運算子、而且優先順序大於或等於 op，就 pop 出來輸出；最後把 op push |
( |
push |
) |
一直 pop 並輸出，直到遇到 (；把 ( 丟掉 |
| 讀完 | 堆疊裡剩下的運算子依序 pop 並輸出 |
為什麼是「大於或等於」？
- 大於：頂端的
*比新來的+優先，*必須先算，所以先輸出 - 等於：
8 - 3 - 2讀到第二個-時，頂端是第一個-。左結合表示左邊的先算，所以先輸出第一個-。如果條件寫成「大於」，第一個-會留在堆疊裡比較晚輸出，算出來變成 8 - (3 - 2)
範例只處理一位數的數字，讓程式專注在堆疊上；多位數的數字只要把連續的數字字元讀成一個數。
中序轉後序：優先順序與左結合
3+4*2-1：讀到 * 時頂端是 +，* 比較優先，所以 * 直接 push 疊在 + 上面；讀到 - 時，頂端的 * 和下面的 + 都比 - 優先或相同，依序被 pop 出來輸出。8-3-2：讀到第二個 - 時，頂端是同一級的 -，左結合讓它先輸出。（C++、Java 的函式名稱是 toPostfix。）
中序轉後序：括號
同一個函式，換成有括號的運算式。左括號 push 之後就像一道牆：(1+2)*(9-3) 讀到第二組括號裡的 - 時，下面的 * 被 ( 擋住，不會被比較。讀到右括號，括號裡的運算子全部輸出。8/(4-2)*3 的結果是 8 4 2 - / 3 *：括號讓 - 先算，接著 / 和 * 同一級，由左往右。
想一想：括號與中序轉後序
中序運算式 5*(2+3)-4 轉成後序是哪一個？
把轉換規則的「頂端優先順序大於或等於新的運算子就 pop」改成只有「大於」才 pop。8-3-2 轉出來的後序再拿去計算，會得到多少？
下面的程式會印出什麼？（check 是本課括號配對範例的函式）
計算後序運算式：注意運算元的順序
後序運算式從左到右讀：
- 數字：push
- 運算子：pop 兩個數，計算，再把結果 push 回去
- 讀完時，堆疊裡應該剛好剩一個數，就是答案
要注意 pop 出來的順序：先 pop 的是右邊的運算元。20 4 / 是 20 / 4，堆疊裡 4 在上面，所以先 pop 出 4（right），再 pop 出 20（left），計算 left / right。
加法和乘法順序不影響結果，減法與除法寫反就錯了。
堆疊也能順便檢查運算式是否正確：
- 遇到運算子時堆疊裡不到兩個數：運算元不夠，例如
5 + 2（中序的寫法，不是後序） - 讀完時堆疊裡不只一個數：運算子不夠，例如
1 2 3 +
除法的提醒：負數除法與不整除時，Python 的 // 往負無限大取整，C++、Java 的 / 往 0 取整，結果可能不同（例如 -7 除以 2，Python 得 -4，C++、Java 得 -3）。本課的例子都只用能整除的非負數。
用堆疊計算後序運算式
第一個運算式 20 4 / 3 1 - * 等於 (20 / 4) * (3 - 1) = 10。讀到 / 時看清楚：先 pop 出來的 4 是右邊。第二個 5 + 2 讀到 + 時堆疊裡只有一個數；第三個 1 2 3 + 讀完時堆疊裡還有兩個數。（C++、Java 的函式名稱是 evalPostfix。）
兩個堆疊：不產生後序，直接算
轉換與計算可以合成一步。觀察調度場演算法：每當一個運算子被「輸出」到後序運算式，下一階段計算時就是在那個時候用到它。 所以不必真的把後序運算式寫下來，改成在「輸出」的那一刻直接計算：
- 數字堆疊
nums：放運算元與中間結果 - 運算子堆疊
ops：和調度場演算法一樣
原本「pop 一個運算子輸出」的地方，改成呼叫 apply：從 ops pop 一個運算子、從 nums pop 兩個數，算完把結果 push 回 nums。
讀完時 nums 只剩一個數，就是答案。每個符號最多 push、pop 各一次，整個計算是 O(n)。
很多計算機程式與直譯器在計算運算式時，都是這種思路的變形。
兩個堆疊直接計算 2*(3+4)-6/2
讀到 ) 時算出 3 + 4 = 7；讀到 - 時，頂端的 * 比較優先，先算 2 * 7 = 14。/ 比 - 優先，所以 / 疊在 - 上面等待；讀完之後先算 6 / 2 = 3，再算 14 - 3 = 11。
想一想：後序求值
下面的程式會印出什麼？
有人寫計算後序的程式時，把 pop 的順序寫反了：先 pop 的當成左邊。計算 8 2 / 會得到多少（用整數除法）？
中序運算式有 n 個符號。用調度場演算法轉成後序（或用兩個堆疊直接計算），時間複雜度是多少？
實作：把後序運算式轉回加了括號的中序
後序求值的堆疊裡放的是數字；如果改放字串，就能把後序運算式轉回中序。請完成 to_infix（C++、Java 是 toInfix）的運算子部分：pop 出右邊和左邊的字串，組成 "(" + left + " " + 運算子 + " " + right + ")" 再 push 回去。預期輸出在右邊。
重點整理
- 堆疊後進先出，適合處理巢狀結構：越晚打開的越早關上
- 括號配對：左括號 push；右括號要和頂端同種類才 pop；讀完時剩下的左括號從頂端開始補上右括號
- 後序運算式不需要括號與優先順序，從左到右讀、遇到運算子就算，適合電腦計算
- 調度場演算法：數字直接輸出；運算子先把頂端優先順序大於或等於它的運算子輸出，再 push；
(push，)輸出到(為止 - 後序求值：數字 push，運算子 pop 兩個數；先 pop 的是右邊；讀完剩一個數才是正確的運算式
- 兩個堆疊（數字、運算子）可以不產生後序，直接計算中序運算式，O(n)
下一課：鏈結串列。陣列裡的元素緊緊相鄰，鏈結串列的節點散在記憶體各處，靠指標串起來。