前言

我们平时见到的表达式一般为中缀表达式，比如3 + 5 * (2 - 1)，这个表达式对于计算机来说并不是直接计算出它的答案的，而是先将其转换成后缀表达式然后再进行计算。

后缀表达式（逆波兰表达式）

举个例子，计算一个中缀表达式的具体步骤：

  1. 中缀表达式：3 + 5 * (2 - 1)
  2. 转换为后缀表达式：3 5 2 1 - * +
  3. 计算结果

转换过程

转换的步骤通常遵循运算符优先级和括号规则以及左优先原则：

  1. 操作数：遇到操作数（数字）时，将其放入输出列表。
  2. 操作符：遇到操作符时，根据优先级进行处理：
    • 如果当前操作符的优先级高于栈顶操作符，则将其压入栈。
    • 如果当前操作符的优先级低于或等于栈顶操作符，则将栈顶操作符弹出，加入输出列表，直到找到优先级较低的操作符或栈为空，然后将当前操作符压入栈。
  3. 括号：
    • 遇到左括号 ( 时，将其压入栈。
    • 遇到右括号 ) 时，将栈中的操作符弹出并加入输出列表，直到遇到左括号。

以3 + 5 * (2 - 1)为例：

  1. 栈->[]，输出->[]
  2. 栈->[]，输出->[3]
  3. 栈->[+]，输出->[3]
  4. 栈->[+]，输出->[3, 5]
  5. 栈->[+, *]，输出->[3, 5]
  6. 栈->[+, *, (]，输出->[3, 5]
  7. 栈->[+, *, (]，输出->[3, 5, 2]
  8. 栈->[+, *, (, -]，输出->[3, 5, 2, 1]
  9. 栈->[+, *]，输出->[3, 5, 2, 1, -,]
  10. 栈->[+]，输出->[3, 5, 2, 1, -, *]
  11. 栈->[]，输出->[3, 5, 2, 1, -, *, +]

最后得到结果：3 5 2 1 - * +

计算过程

  1. 遇到操作数时，将其压入栈。
  2. 遇到操作符时，从栈中弹出相应数量的操作数进行运算，并将结果压回栈。
  3. 最终，栈中剩下的值就是表达式的结果。

以后缀表达式3 5 2 1 - * +为例：

  1. 栈->[]
  2. 栈->[3]
  3. 栈->[3, 5]
  4. 栈->[3, 5, 2]
  5. 栈->[3, 5, 2, 1]
  6. 栈->[3, 5, 1]
  7. 栈->[3, 5]
  8. 栈->[8]

最后得到结果：8

前缀表达式（波兰表达式）

前缀表达式是将操作符放到了两个操作数前面，比如：
中缀表达式3 + 5 * (2 - 1)转换为后缀表达式为+ 3 * 5 - 2 1

它的转换规则与逆波兰表达式基本一致，只是遍历方向变成了从右往左。