中缀表达式 (Infix Notation)

这是我们人类最习惯的数学表达式写法。操作符（如 +, -, *, /）放在两个操作数（数字）之间。例如：3 + 4, (10 - 2) * 5。

  • 优点：符合我们的阅读和书写习惯。
  • 缺点：计算机在解析时需要处理运算符优先级和括号，比较复杂。

后缀表达式 (Postfix Notation / Reverse Polish Notation - RPN)

在这种表示法中，操作符放在它的操作数之后。例如：3 4 + 表示 3 + 4。(10 - 2) * 5 会写成 10 2 - 5 *。

  • 优点：
    1. 没有括号：运算顺序完全由操作符和操作数的位置决定。
    2. 无歧义：表达式只有一个明确的含义。
    3. 易于计算机求值：只需要一个栈即可轻松计算结果。算法如下：
      • 从左到右扫描表达式。
      • 如果是数字，则压入栈。
      • 如果是操作符，则从栈中弹出所需数量的操作数（例如，对于二元操作符-，弹出两个），执行运算，然后将结果压回栈中。
      • 最终，栈中剩下的唯一一个数就是表达式的值。

中缀转后缀 (调度场算法 - Shunting-yard algorithm 的简化版)

将中缀表达式转换为后缀表达式的基本思路是：

  1. 使用一个栈来存放操作符。
  2. 从左到右扫描中缀表达式。
  3. 如果遇到操作数（数字），直接输出。
  4. 如果遇到左括号 (，将其压入操作符栈。
  5. 如果遇到右括号 )，则依次弹出操作符栈中的操作符并输出，直到遇到左括号 ( 为止，并将左括号 ( 弹出（但不输出）。
  6. 如果遇到操作符（如 +, -, *, /）：
    • 当操作符栈顶的操作符优先级大于或等于当前操作符的优先级时，将栈顶操作符弹出并输出。
    • 将当前操作符压入操作符栈。
  7. 当整个表达式扫描完毕后，将操作符栈中剩余的所有操作符依次弹出并输出。

这种写法（指将数字（操作数）和操作符（如 +, - 等）都用空格分隔开，形成一个由token（词法单元）组成的序列）非常符合 C++ 数据结构和算法课程中对于表达式处理的要求和实践。

为何要转后缀

  1. 易于解析 (Tokenization)：在编程中，处理一个由空格分隔的字符串序列比处理一个紧凑的字符串要简单得多。你可以很容易地使用 std::istringstream 或 std::stringstream 结合 >> 操作符来逐个读取这些“词法单元”（token）。例如，"100 4 - 3 /" 可以很方便地被解析成 ["100", "4", "-", "3", "/"]。

    // 示例：简单的词法分析
std::string postfix = "100 4 - 3 /";
std::istringstream iss(postfix);
std::string token;
while (iss >> token) {
    if (token == "+" || token == "-" || token == "*" || token == "/") {
        // 处理操作符
    } else {
        // 处理操作数 (需要转换为数字，如 std::stoi(token))
    }
}

  2. 符合后缀表达式求值算法：标准的后缀表达式求值算法就是基于这种“空格分隔的token序列”来设计的。

    • 从左到右读取token。
    • 如果是数字，压入栈。
    • 如果是操作符，从栈中弹出操作数，计算，结果压回栈。
    • 最终栈中剩下的元素就是结果。
    • 这个算法直接操作的就是一个个独立的token。

  3. 清晰性和可读性：对于人类阅读和调试代码来说，这种格式非常清晰。它明确地将操作数和操作符区分开来。

  4. 数据结构课程的通用实践：在学习栈、队列等数据结构时，处理表达式是经典的应用场景。无论是中缀转后缀、后缀转中缀还是表达式求值，将输入表示为token序列（通常由空格分隔）是教学和编程实践中最常见、最推荐的方式。

因此，后缀表达式是C++（以及大多数编程语言）数据结构课程中标准且推荐的表示和处理方式，举例：

((100-4)/3+3*(36-7))*2 = 100 4 - 3 / 3 36 7 - * + 2 *