前言

相关代码: 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 

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

输入 操作 栈(后边是栈顶) 注释
* 入栈 *
+ 入栈 *,+
1 入栈 *,+,1 只有一个操作数字,继续入栈
2 加法运算 *,3 1,+ 出栈,计算 1+2,结果3入栈。当前为数字,且栈顶为数字。
+ 入栈 *,3,+
3 入栈 *,3,+,3
4 加法运算 *,3,7 3,+ 出栈,计算结果7 ,入栈
乘法运算 21 7,3,* 出栈,计算结果21,入栈

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

输入 操作 栈(后边是栈顶) 注释
1 入栈 1
2 入栈 1,2
+ 加法运算符 3 2,1 出栈,计算结果3入栈
3 入栈 3,3
4 入栈 3,3,4
+ 加法运算符 3,7 4, 3 出栈,计算结果7入栈
* 乘法运算符 21 7,3出栈,计算结果21 ,入栈

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

不同表达式的转换

中缀转前缀

  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 为例:

输入 S2(数字栈,栈底->栈顶) S1(操作符栈,栈底->栈顶) 注释
5 5 数字直接入栈
- 5 - 操作符栈为空,直接入栈
) 5 - ) 右括号,直接入栈
4 5 4 - ) 数字直接入栈
* 5 4 - ) * 栈顶是右括号,操作符直接入栈
) 5 4 - ) * ) 右括号,直接入栈
3 5 4 3 - ) * ) 数字直接入栈
+ 5 4 3 - ) * ) + 栈顶是右括号,操作符直接入栈
2 5 4 3 2 - ) * ) + 数字直接入栈
( 5 4 3 2 + - ) * 左括号,操作符栈弹出,直到遇到右括号,入栈数字栈
( 5 4 3 2 + * - 左括号,操作符栈弹出,直到遇到右括号,入栈数字栈
+ 5 4 3 2 + * - + 优先级和-相同,入操作符栈
1 5 4 3 2 + * 1 - + 数字直接入栈
5 4 3 2 + * 1 + - 操作符栈弹出,入数字栈

中缀转后缀

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

  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 为例:

输入 S2(数字栈,栈底->栈顶) S1(操作符栈,栈底->栈顶) 注释
1 1 数字直接入栈
+ 1 + 操作符栈为空,直接入栈
( 1 + ( 左括号,直接入栈
( 1 + ( ( 左括号,直接入栈
2 1 2 + ( 数字直接入栈
+ 1 2 + ( + 栈顶为左括号,直接入栈
3 1 2 3 + ( + 数字直接入栈
) 1 2 3 + + 右括号,操作符栈出栈,直到遇到左括号,入栈数字栈
* 1 2 3 + + ( * 栈顶为左括号,直接入栈
4 1 2 3 + 4 + ( * 数字直接入栈
) 1 2 3 + 4 * + 右括号,操作符栈出栈,直到遇到左括号,入栈数字栈
- 1 2 3 + 4 * + - 优先级相同,+出栈, -入栈
5 1 2 3 + 4 * + 5 + - 数字直接入栈
1 2 3 + 4 * + 5 - 操作符栈弹出,入数字栈

参考