前缀表达式+中缀表达式+后缀表达式

前言

相关代码： some-code/php/calculator at master · extra-demo/some-code · GitHub

三种表达式是什么

前缀表达式

波兰表示法（Polish notation，或波兰记法），是一种逻辑、算术和代数表示方法，其特点是操作符置于操作数的前面，因此也称做前缀表示法。

中缀表达式

中缀表示法（或中缀记法）是一个通用的算术或逻辑公式表示方法， 操作符是以中缀形式处于操作数的中间（例：3 + 4）。

后缀表达式

在逆波兰记法中，所有操作符置于操作数的后面，因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。

鉴于波兰和逆波兰这种说法用的比较少，下边都是用前缀、中缀、后缀方式代替。

三种表达式实例

只有两个数字和一个运算符的情况

• 前缀表达式 + 1 1
• 中缀表达式 1 + 1
• 后缀表达式 1 1 +

看到前缀表达式的时候是不是感觉似曾相识？ 对就是 lisp 这门语言，如果感兴趣的话可以自己搜索一下。中缀表达式就是很常见的我们日常写法。

下边我们给一个相对毕竟复杂的写法：

• 前缀表达式 (* (+ 1 2) (+ 3 4))，去掉括号：* + 1 2 + 3 4
• 中缀表达式 (1 + 2) * (3 + 4)，这里的括号是不可以去掉的，会影响己算优先级
• 后缀表达式 ((1 2 +) (3 4 +) *)，去掉括号：1 2 + 3 4 + *

为什么会有这三种表达式

不管看着前缀还是后缀表达式都不如中缀表达式顺眼，毕竟我们从小学的都是中缀表达式，既然我们从小学习的是中缀表达式，那为啥还要制造出前缀和后缀表达式呢？

我们已 (1 + 2) * (3 + 4) 运算为例，中缀表达式，需要根据括号的优先级进行计算，也就是说会展开成下图的抽象语法树，然后递归己算叶子节点。

1
2
3
4
5

     *
   /   \
  +     + 
 / \   / \
1   2 3   4 

如果我们拥有一个前缀表达式那么我们要如何己算呢？ 因为前缀和后缀都不用考虑优先级，所以可以直接进行线性己算 以 * + 1 2 + 3 4 为例。这个时候我们可以把运算符当作一个函数调用，那么就可以写成 *(+(1, 2), +(3, 4))。(PS：lisp 就是这么玩的)。some-code/calculator.php at master · extra-demo/some-code · GitHub

后缀表达式怎么计算呢？以 1 2 + 3 4 + * 为例。 我们以栈的形式进行计算。some-code/calculator.php at master · extra-demo/some-code · GitHub

我们可以看到，计算行云流水，简单粗暴。细心的你可能发现，为啥弹出两个数字就开始计算接过来呢？ 因为：四则运算是二元运算！

不同表达式的转换

• 前=》后
• 前=》中
• 中=》后
• 中=》前
• 后=》前
• 后=》中

中缀转前缀

1. 初始化两个栈：运算符栈S1和储存中间结果的栈S2；
2. 从右至左扫描中缀表达式；
3. 遇到操作数时，将其压入S2；
4. 遇到运算符时，比较其与S1栈顶运算符的优先级：
   1. 如果S1为空，或栈顶运算符为右括号“)”，则直接将此运算符入栈；
   2. 否则，若优先级比栈顶运算符的较高或相等，也将运算符压入S1；
   3. 否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较；
5. 遇到括号时：
   1. 如果是右括号“)”，则直接压入S1；
   2. 如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃；
6. 重复步骤(2)至(5)，直到表达式的最左边；
7. 将S1中剩余的运算符依次弹出并压入S2；
8. 依次弹出S2中的元素并输出，结果即为中缀表达式对应的前缀表达式。

下边我们以 1 + ( ( 2 + 3 ) × 4 ) - 5 为例：

中缀转后缀

与转换为前缀表达式相似，遵循以下步骤：

1. 初始化两个栈：运算符栈S1和储存中间结果的栈S2；
2. 从左至右扫描中缀表达式；
3. 遇到操作数时，将其压入S2；
4. 遇到运算符时，比较其与S1栈顶运算符的优先级：
   1. 如果S1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
   2. 比栈顶高，也将运算符压入S1 （注意转换为前缀表达式时是优先级较高或相同，而这里则不包括相同的情况）；
   3. 比栈顶低或相同，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较；
5. 遇到括号时：
   1. 如果是左括号“(”，则直接压入S1；
   2. 如果是右括号“)”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到左括号为止，此时将这一对括号丢弃；可以想象成“（”比任何运算符都高，“）”比任何运算符都低 。
6. 重复步骤(2)至(5)，直到表达式的最右边；
7. 将S1中剩余的运算符依次弹出并压入S2；
8. 依次弹出S2中的元素并输出，结果的逆序 即为中缀表达式对应的后缀表达式（转换为前缀表达式时不用逆序）。

下边我们以 1 + ( ( 2 + 3 ) × 4 ) - 5 为例：

参考

• 波兰表示法 - 维基百科，自由的百科全书
• 逆波兰表示法 - 维基百科，自由的百科全书
• 中缀表示法 - 维基百科，自由的百科全书
• 调度场算法 - 维基百科，自由的百科全书
• 中缀表达式转换成前缀表达式和后缀表达式 - 飞鸟快跑 - 博客园