以前挺喜欢后缀表达式的…

后缀表达式（也称为逆波兰表达式）是一种数学表达式的表示方法，其中操作符在操作数之后。在后缀表达式中，不需要括号来指示运算次序，而是通过操作符的位置来确定运算的顺序。后缀表达式的优点是可以消除运算符的优先级和括号对运算顺序的影响，使表达式的求值变得简单而直观。

经常面临的问题是：如何将中缀表达式变为后缀表达式？

  • 对于此问题，我们通常使用**数据结构“栈”**来实现我们的目的

首先，定义一下本文可能用到的伪代码函数：

1
2
3
4
5
read x ：读取 x （ x 为数据或运算符）
top : 返回栈顶元素
append  x : 将 x 追加到字符串后
pop : 返回并弹出栈顶元素
push x : 把 x 压栈

一、首先仅考虑 + - （即同一优先级）

对于表达式变换：

a+b+c−d−e+f   →   ab+c+d−e−f+a+b+c-d-e+f~~~ \rightarrow ~~~ab+c+d-e-f+

可以发现，忽略运算符的话，a b c d e f 的出现顺序没有任何变化。

那么可以尝试不改变 数据 的顺序，仅在输出数据时 插入运算符，即可实现转换。

实操可以发现：

​ 如果仅改写表达式 a+b ,可以这样搞：

  • 假设 s = "a+b" , ans 为结果字符串 , stack 用来存储运算符
1
2
3
4
5
6
7
read 'a' from s[];
append 'a' to ans[];  // ans[] = "a"
read '+' from s[];
append '+' to stack;  // stack = +
read 'b' from s[];
append 'b' to ans[]; // ans[] = "ab"
pop '+' from stack , append '+' to ans[]; //ans[] = "ab+"

这样一来我们成功处理了"a+b"

然后，我们把 a+b 看成一个 数据 u，这样a+b+c-d-e+f，就成了u+c-d-e+f --> uc+d-e-f+

是不是变得简单了呢！！！

逐个迭代，我们发现了这样一个方法：

  • 如果表达式中仅含有 + - 运算符，我们可以这样搞：
  1. 顺次读取表达式，遇到数据 (a b c …)，我们把它直接加到结果字符串后面；
  2. 遇到运算符 ，如果 stack 中什么也没有，就先把此运算符压栈；如果 stack 中有运算符，先把栈顶的运算符pop 出来**，添加到结果字符串后面，然后**再压栈；
  3. 如果中缀表达式已经读取完毕，stack 内还有运算符，就把所有运算符 pop 出来，依次加到结果字符串后面；

二、在“一”的基础上，我们加上左右括号来讨论，

例如：

a+b+(c−d)−e+f   →   ab+cd−+e−f+a+b+(c-d)-e+f ~~~\rightarrow ~~~ab+cd-+e-f+

正常情况下，我们应该先计算括号里面的，比如把 (c-d) 设为 u （是不是很像前面的？！！），然后得到新的表达式

a+b+u−e+f   →   ab+u+e−f+a+b+u-e+f ~~~\rightarrow ~~~ab+u+e-f+

而 u 可以 转化为 cd- ，把 u = cd- 带入，就可以得到正确的表达式了！！！

​ 但是，人类是可以看到括号，先计算再带入的，机器只会笨笨地从前往后读入。

​ 机器可以怎样实现呢？

我们可以这么干：

  1. 当我们正常从前往后读，如果碰到 ‘(’ ,就开启一个“新栈”（ 当然不是重开一个stack2 ），我们可以顺势把 ‘(’ 压栈，用它来隔绝外部栈（自创名词）的空间，把 ‘(’ 以后的部分当成一个新栈，然后继续按照 “一”中的1. 2.步骤进行（当然具体代码要改一下，比如判断是否是空栈应该检查 top 是不是 ‘(’ ）；
  2. 当我们读到右括号 ‘)’ ，就相当于 u 已经读取完毕且“新栈”结束，把新栈内还存在的运算符 pop 出来，依次加到结果字符串后面（看看像不像“一”中的步骤3），并且记得要把 ‘(’ 去掉；

例如我们演示一遍，假如：

  • 输入缓冲区中还未读取的部分为 (c-d)-e+f

  • 栈 stack 中的运算符目前为 stack = +

  • 结果字符串中的情况 ans[] = ab+

  • -> 表示进行的相应操作

现在继续进行读取，每一步从缓冲区中读取一个字符：

1
2
3
4
5
6
7
read  '('  ->  push '('                          // stack = +(
read  'c'  ->  append 'c'                        // ans[] = "ab+c"
read  '-'  ->  push '-'                          // stack = +(-
read  'd'  ->  append 'd'                        // ans[] = "ab+cd"
read  ')'  ->  while((elem=pop)!='(') append elem// ans[] = "ab+cd-"   stack = +
read  '-'  ->  append pop; push '-'              // ans[] = "ab+cd-+"  stack = -
......

三、在“二”的基础上，继续引入 * / 运算符

例如：

a+b+(c−d)−e∗f+g   →   ab+cd−+ef∗−g+a+b+(c-d)-e*f+g ~~~\rightarrow ~~~ ab+cd-+ef*-g+

按照我们小学二年级~~（真的是二年级）~~学习到的“先算乘除再算加减”的法则，实际上在我们看来，乘除法的表达式可以看作是“自带括号”的，也就是说**“先算乘除再算加减”的法则给我们带来了一种“隐形的括号”**，因此我们可以把这种“隐形括号”（方括号表示）的概念通过 “设置优先级”的方式 传递给计算机。

a+b+(c−d)−[e∗f]+g   →   ab+cd−+[ef∗]−g+a+b+(c-d)-[e*f]+g ~~~\rightarrow ~~~ ab+cd-+[ef*]-g+

我们不妨认为 oprtr1 > oprtr2 表示运算符 oprtr1 的优先级大于 oprtr2（e.g. *>-表示*的优先级大于-）

我们演示一遍：

  • 比如输入缓冲区中还未读取的部分为 -e*f+g
  • 栈 stack 中的运算符目前**为 **stack = +
  • 结果字符串中的情况 ans[] = ab+cd-

现在继续进行读取，每一步从缓冲区中读取一个字符：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
read  '-'  
->  while(stack.notEmpty) append pop;  
    push'-'                                      // stack = -   ans[] = "ab+cd-+"
read  'e'  ->  append 'e'                        // stack = -   ans[] = "ab+cd-+e"
//重点来了！！

/*
接下来要 read '*'，而我们发现 * > top ,这时我们认为有一个隐形的括号隔绝了前半部分，也就是说，
虽然栈内有运算符，不过因为 栈顶的运算符oprtr1的优先级小于我们要加入的运算符oprtr2 ，
我们视作开始了一个新的空栈（只不过没有真实的'('字符做标记）,因此我们直接压栈...
*/

read  '*'  ->  push '*'                          // stack = -*  ans[] = "ab+cd-+e"
read  'f'  ->  append 'f'                        // stack = -*  and[] = "ab+cd-+ef"

/*
接下来要 read '+' ,而我们发现 + < top ,这时新栈结束，我们要将新栈中的运算符全部pop出,
而栈中没有字符'('作为结束标志符，因此我们可以这么干 while(top>'+') append pop ；现在我
们的新栈已经处理完毕了，而与')'不同的是，我们读到的 '+' 是有意义的,需要出现在表达式里面，
所以我们需要在下一次还能读到这个 '+' 进行后续操作，我们可以把 '+' 返回到输入缓
冲区 ungetc('+') ，以便于下一次操作

实际上类似于“二”中代码区中的这一部分：
        read  ')'  ->  while((elem=pop)!='(') append elem;
*/

read  '+'   
->  while( stack.notEmpty && top>'+') append pop;
    ungetc('+');                                 // stack = -   and[] = "ab+cd-+ef*"
read  '+'

/*到这里新栈就处理完毕了，剩下的部分就是”一“中的情况啦~~~*/
......

四、在“三”的基础上引入乘方 ^ 操作

公式里的^ 用逻辑且符号 ∧ 替代

例如：

a−b∧c∗d+e   →   abc∧d∗−e+a-b \land c*d+e~~~ \rightarrow~~~ abc \land d*-e+

嗐，其实还是“三”那一套，设置 ^ 的优先级最高，剩下的只要按照“三”中的步骤即可。

不过有个要注意的小地方，就是连续的乘方是从右到左计算的：

a∧b∧c=a∧(b∧c)   →   abc∧∧a \land b \land c = a \land (b \land c) ~~~\rightarrow~~~ abc \land \land

不过这种特殊情况加特判就好啦~~

五、最终结论

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
while( read x && x!=EOF ){ //这里的EOF不一定是文件末尾，只要是结束标志就可以，比如'='
    if( x == '(' ){
        push x
    }else if( x == ')' ){
        while((elem = pop)!=')') append elem; //可避免 append '('
    }else if( isoperator(x) ){  // x == + - * / ^
        if( stack.notEmpty ){
            if( x == top ){ // 指优先级相等
                if( x!='^' ){ // x 不是 '^' 特判
                    append pop
                }
                push x
            }else if( x < top ){
                while( stack.notEmpty && x < top ){
                    append pop
                }
                ungetc x
            }else{  // x > top
                push x
            }
        }else{
            push x
        }
    }else{  // x为数据
        append x
    }
}
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

快来参与讨论吧~