了解 Shunting-Yard 演算法：從中序到後序
將數學表達式從人類偏好的格式——中序表示法——轉換為機器能高效處理的格式，是計算機科學中的一項基本挑戰。Shunting-Yard 演算法提供了一個優雅且迭代的解決方案，將表達式轉換為逆波蘭表示法（RPN），亦稱為後序表示法。
此轉換至關重要，因為它使得簡單的基於堆疊的機器能在一次前向遍歷中計算公式的結果，省去對括號進行複雜回溯或遞迴下降解析的需求。
Shunting-Yard 演算法的工作原理
該演算法的運作類似鐵路調車場，將代碼（數字、運算子與括號）從輸入流移動到輸出流，並使用堆疊作為暫時的暫存區（即「調車場」）。
步驟說明
- 處理代碼：演算法逐一讀取輸入中的代碼。
- 運算元：當遇到數字或變數時，直接推入輸出。
- 運算子：當遇到運算子 $o_1$ 時，演算法檢查堆疊頂部目前的運算子 $o_2$。只要 $o_2$ 具有更高的優先權，或優先權相等且 $o_1$ 為左結合，則將 $o_2$ 從堆疊彈出並推入輸出。然後，將 $o_1$ 推入堆疊。
- 括號：
- 左括號：直接推入堆疊。
- 右括號：演算法從堆疊彈出運算子至輸出，直到遇到左括號。左、右括號隨後被丟棄。
- 完成：當所有輸入代碼處理完畢後，堆疊中剩餘的運算子全部推入輸出。
技術細節與實作挑戰
雖然 Shunting-Yard 演算法的核心邏輯相當直接，實務上的實作常會遇到特定的邊緣案例與技術挑戰。
斷詞與分界
基本實作中常見的陷阱是多位數字的處理。如社群成員所指出，有些示範將每個數字視為獨立的代碼（例如把 13 當作 1, 3）。在可投入生產的解析器中，需要一個適當的詞彙分析器（lexer）將數字串合併為單一的數值運算元，以避免在輸入為 100+88/4 時產生如 100884+/ 之類的模糊輸出。
錯誤處理與驗證
預設情況下，標準的 Shunting-Yard 演算法不會執行嚴格的錯誤檢查。它常會接受語法上無效的輸入而不拋出錯誤。然而，這並非演算法本身的限制，而是實作上的選擇。加入驗證邏輯——例如檢查括號不匹配或連續運算子——是構建穩健表達式求值器的必要步驟。
與其他解析技術的關係
從技術上看，Shunting-Yard 演算法可視為遞迴解析方法的迭代替代方案。它與 Pratt parsing 與 precedence climbing 密切相關，兩者皆用於在更複雜的語言文法中處理運算子優先權與結合性。
理論觀點
除了實務上的解析應用外，該演算法亦引發有趣的理論問題。有觀察者指出標準計算與 reversible computing（可逆計算）之間的差異，在可逆計算中，計算過程產生的「垃圾」（例如被丟棄的括號）不能簡單刪除，必須保留以允許過程被逆轉。
總之，Shunting-Yard 演算法仍是編譯器設計與表達式求值的基石，彌合了人類可讀的數學表示法與堆疊可執行邏輯之間的鴻溝。