后缀表达式的转化

感谢文章原作者西门蒸馍

将表达式转化为后缀表达式：

定义伪代码函数：

• 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 的出现顺序没有任何变化。

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

实操可以发现：

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

假设 s = "a+b"，ans 为结果字符串，stack 用来存储运算符，过程如下：

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+

正常情况下，我们应该先计算括号里面的，比如把 (c-d) 设为 u（是不是很像前面的？！！），然后得到新的表达式 a+b+u-e+f --> 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+"

-> 表示进行的相应操作

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

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 --> ab+cd-+[ef*]-g+

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

例如我们演示一遍： 比如输入缓冲区中还未读取的部分为 -e*f+g 栈 stack 中的运算符目前为 stack = + 结果字符串中的情况 ans[] = "ab+cd-" 现在继续进行读取，每一步从缓冲区中读取一个字符：

read '-' -> while(stack.notEmpty) append pop;  
            push '-'                           // stack = -   ans[] = "ab+cd-+"

read 'e' -> append 'e'                         // stack = -   ans[] = "ab+cd-+e"

/* 重点来了！！
 * 接下来要 read '*'，而我们发现 * > top，这时我们认为有一个隐形的括号隔绝了前半部分，
 * 也就是说，虽然栈内有运算符，不过因为栈顶的运算符op1的优先级小于我们要加入的运算符op2，
 * 我们视作开始了一个新的空栈（只不过没有真实的'('字符做标记）,因此我们直接压栈...
 */
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^c == a^(b^c) --> abc^^

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

五、最终结论

伪代码：

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
    }
}