(二) 使用「stack」的兩個實際應用案例
案例 1：表達式求值
在計算機科學中，堆疊常用於計算算術表達式，特別是中綴（infix）、前綴（prefix）和後綴（postfix）表達式的轉換和求值。這裡以後綴表達式求值為例。
後綴表達式求值：
- 後綴表達式是一種表示方式，操作符在操作數之後。例如，中綴表達式 3 + 4 * 2 / (1 - 5) 可以表示為後綴表達式 3 4 2 * 1 5 - / +。
- 求值方法：
- 從左到右掃描後綴表達式。
- 遇到操作數，將其壓入堆疊。
- 遇到操作符，彈出堆疊頂端的兩個操作數，進行相應的運算，並將結果壓回堆疊。
- 最終堆疊中剩下的唯一一個數即為表達式的值。
示例： 假設有後綴表達式 3 4 2 * 1 5 - / +，求值過程如下：
- 初始：堆疊空。
- 讀到 3，壓入堆疊：[3]
- 讀到 4，壓入堆疊：[3, 4]
- 讀到 2，壓入堆疊：[3, 4, 2]
- 讀到 *，彈出 2 和 4，計算 4 * 2 = 8，壓入堆疊：[3, 8]
- 讀到 1，壓入堆疊：[3, 8, 1]
- 讀到 5，壓入堆疊：[3, 8, 1, 5]
- 讀到 -，彈出 5 和 1，計算 1 - 5 = -4，壓入堆疊：[3, 8, -4]
- 讀到 /，彈出 -4 和 8，計算 8 / -4 = -2，壓入堆疊：[3, -2]
- 讀到 +，彈出 -2 和 3，計算 3 + -2 = 1，壓入堆疊：[1]
- 最終結果：堆疊中剩下的數字 1 即為表達式的值。
案例 2：括號匹配
括號匹配是另一個使用堆疊的典型應用，用於檢查程式碼中括號是否正確配對，特別是在編譯器和語法分析器中。
括號匹配：
- 算法描述：
- 從左到右掃描字符串。
- 遇到開括號（(, [, {），將其壓入堆疊。
- 遇到閉括號（), ], }），檢查堆疊頂端是否為對應的開括號：
- 若是，彈出堆疊頂端的開括號，繼續掃描。
- 若否或堆疊為空，則括號不匹配。
- 最終檢查堆疊是否為空，若是，則所有括號匹配；若否，則括號不匹配。
示例： 假設有字符串 "{[()()]}"，檢查括號匹配過程如下：
- 初始：堆疊空。
- 讀到 {，壓入堆疊：[{]
- 讀到 [，壓入堆疊：[{, []
- 讀到 (，壓入堆疊：[{, [, (]
- 讀到 )，彈出堆疊頂端 (，匹配，堆疊：[{, []
- 讀到 (，壓入堆疊：[{, [, (]
- 讀到 )，彈出堆疊頂端 (，匹配，堆疊：[{, []
- 讀到 ]，彈出堆疊頂端 [，匹配，堆疊：[{]
- 讀到 }，彈出堆疊頂端 {，匹配，堆疊空。
- 結束：堆疊空，所有括號匹配。
這兩個案例展示了堆疊在處理表達式求值和括號匹配中的應用，說明了堆疊在管理後進先出（LIFO）資料上的便利性和有效性。
阿摩線上測驗
登入