歡迎來到逆波蘭表示法的世界！

你好！今天我們要探討一個聽起來有點嚇人，但實際上是電腦界非常巧妙的「捷徑」的課題。我們要學習的是逆波蘭表示法 (Reverse Polish Notation, RPN)，也稱為後序表示法 (Postfix Notation)。

看完這份筆記，你就會明白為什麼電腦比起我們在學校學的數學運算更偏好這種方式，而且你還能像專家一樣輕鬆進行兩者之間的轉換。如果起初覺得看起來有點「反過來了」，不用擔心——這正是它的精髓所在！

1. 什麼是逆波蘭表示法？

在日常生活中，我們使用中序表示法 (Infix Notation)。這意味著運算符（如 +, -, 或 *）放在數字的中間。
例子：\( 3 + 4 \)

而在逆波蘭表示法 (RPN) 中，運算符則是放在數字的後面。
例子：\( 3 \ 4 \ + \)

為什麼我們要用它？

電腦喜歡 RPN 主要有三個原因：

  • 無需括號：在 RPN 中，數字和運算符的順序精確地告訴電腦該做什麼。根本不需要括號！
  • 標準順序：它消除了關於 BIDMAS/BODMAS（運算優先次序）的任何混淆。運算順序直接寫在字串中了。
  • 對堆疊（Stack）友好：電腦使用堆疊 (Stack) 資料結構（我們稍後會講到）來運算它非常簡單。

快速回顧：
中序 (Infix)：運算符在中間 (\( A + B \))。
後序 (Postfix/RPN)：運算符在最後 (\( A \ B \ + \))。

2. 如何轉換：中序轉為 RPN

轉換看起來可能有點棘手，但有一個簡單的「括號技巧」，能讓你每次都準確無誤。

「括號與移動」法

  1. 寫下你的中序表達式：\( (3 + 4) * 5 \)
  2. 根據 BIDMAS 確保它完全加上括號：\( ((3 + 4) * 5) \)
  3. 將每個運算符向右移動，移到對應的右括號內：\( ((3 \ 4 + ) \ 5 * ) \)
  4. 刪除所有括號：\( 3 \ 4 \ + \ 5 \ * \)

類比：想像一位廚師。在中序法中，食譜寫著「加入麵粉和糖，然後烘焙」。在 RPN 中，廚師先拿到原料：「麵粉，糖，加入，烘焙」。動作（運算符）永遠在物品（運算元）之後。

3. 如何轉換：RPN 轉回中序

如果你看到一個 RPN 表達式並需要將其轉回「人類可讀」的數學式，請遵循以下步驟：

  1. 由左至右閱讀表達式。
  2. 當你看到一個運算符，將其應用到緊鄰其左側的兩個數字。
  3. 給這個新的「組合」加上括號，並將其視為一個數字。

例子： \( 5 \ 3 \ 2 \ * \ + \)
1. 我們看到 \( 3 \ 2 \ * \)。將其轉為 \( (3 * 2) \)。
2. 現在我們有了 \( 5 \ (3 * 2) \ + \)。
3. \( + \) 應用於 \( 5 \) 和 \( (3 * 2) \)。
4. 最終中序：\( 5 + (3 * 2) \)

重點總結：轉換到 RPN 時，將運算符向右移。轉換回來時，將它們移到左側兩個數字的中間。

4. 使用堆疊（Stack）評估 RPN

這是考試中的熱門考點！電腦使用堆疊（Stack，一種「後進先出」Last-In, First-Out 的資料結構）來解開 RPN 表達式。

逐步運算

讓我們來運算：\( 6 \ 2 \ / \ 3 \ + \)

  • 掃描第一個項目 (\( 6 \))：它是個數字，所以壓入 (Push) 堆疊。 [堆疊: 6]
  • 掃描下一個項目 (\( 2 \))：它是個數字，所以壓入 (Push)。 [堆疊: 6, 2]
  • 掃描下一個項目 (\( / \))：它是個運算符！
    • 彈出 (Pop) 最上面的數字 (\( 2 \))。這是你的第二個運算元。
    • 彈出 (Pop) 下一個數字 (\( 6 \))。這是你的第一個運算元。
    • 計算 \( 6 / 2 = 3 \)。
    • 將結果 (\( 3 \)) 壓入 (Push) 回堆疊。 [堆疊: 3]
  • 掃描下一個項目 (\( 3 \))：它是個數字，所以壓入 (Push)。 [堆疊: 3, 3]
  • 掃描下一個項目 (\( + \))：它是個運算符！
    • 彈出 (Pop) (\( 3 \)), 彈出 (Pop) (\( 3 \))。
    • 計算 \( 3 + 3 = 6 \)。
    • 將結果 (\( 6 \)) 壓入 (Push) 回堆疊。 [堆疊: 6]

堆疊中剩下的最後一個數字就是你的答案！

常見錯誤警告！
當進行減法或除法時，你第一個彈出的數字是減號/除號右側的那個數。
例子：如果堆疊是 [10, 2] 而你看到 \( - \)，計算應該是 \( 10 - 2 \)，而不是 \( 2 - 10 \)！

5. 現實世界的應用

你可能會問：「真的有人用這個嗎？」有的！RPN 被用於速度和簡潔性至關重要的地方：

  • 直譯器：許多程式語言的直譯器（例如 Postscript 或 Java Bytecode）都使用堆疊和 RPN，因為這比處理複雜的中序字串對電腦來說更快。
  • 計算機：早期的 Hewlett-Packard (HP) 計算機使用 RPN。一些工程師今天仍然偏好它們，因為他們可以進行長串計算而完全不需要用到括號！

你知道嗎？Postscript 是一種印表機使用的語言。當你列印 PDF 時，你的電腦通常就是傳送一長串 RPN 風格的指令給印表機！

總結：快速回顧框

定義：RPN（後序）將運算符置於運算元之後 (\( 3 \ 4 \ + \))。
優點 1：無需括號。
優點 2：無運算優先次序 (BIDMAS) 的歧義。
機制：使用堆疊 (Stack) 評估（壓入數字，遇到運算符則彈出計算）。
用途：基於堆疊的直譯器、Postscript 以及電腦位元組碼 (Bytecode)。