欢迎来到逆波兰表示法的世界！

你好！今天我们要探讨一个听起来有点吓人，但实际上是计算机界非常巧妙的“捷径”的课题。我们要学习的是逆波兰表示法 (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)。