【洛谷日报#176】浅谈表达式的求值（后缀表达式）

0:序言

我们在做一些题目的时候，需要求一些恶心的表达式的值。那么，我们需要用一些快一些的方法求值。

我们能最先想到的就是暴力求值，也就是：

一步步将可运算的地方运算好，最后剩下的就是表达式的值了。

举个栗子：

 (6+2*3)/4-5
=(6+6)/4-5
=(12)/4-5
=3-5
=-2


但是，这种方法很容易被卡掉。例如，1+(2+(3+(4+(5+6))))这个式子中，每一次可以执行的符号只有最里面括号的值（因为其他运算符都因为右边的运算没有结果而不能被运算）

这个时候时间复杂度降到了，非常慢。

这个时候，我们就要想一些更快的方法。

1:表达式的树

实际上，我们可以将整个表达式看成一个二叉树，每个非叶子节点上表示的是一个运算符，左右为这个运算符在原来的表达式中左右的值。叶子节点表示的是一个值。

在计算时，我们可以用DFS的方法，在一个节点处先搜索左右儿子代表的值，之后计算。

伪代码如下：

f() 参数：一个整数。返回值：一个整数。
f(now) 
    if(now是叶子节点)    return 这个叶子节点代表的值
    return f(左儿子)[now所代表的运算符]f(右儿子)

我们还可以这么看：

很多个数排在一起。每一次，两个相邻的数通过某种方式（就是根代表的运算符）合并成一个数，最后只剩下一个数，这就是表达式的值。

举个例子：

(6+2*3)/4-5


合并过程长这样：

6 2 3 4 5
6 6 4 5
12 4 5
3 5
-2

过程如下：

我们通过以下方式处理字符串（又是伪代码）：

tr() 参数：字符串S 返回：一棵树
tr(S)
    if(S只包含一个数字)
        return 以这个数字为根的树（只有一个节点）
    找到最后运行的运算符X
    将X设为这个树的根
    将左儿子设为tr(S以X为分界线分开的左边部分)
    右儿子设为tr(S以X为分界线分开的右边部分)
    return 这个树


最后运行的运算符很好找，只要找这个表达式最外层的运算符中优先级最小的就好（不会优先级的出门左转）

有多个只用取其中一个，这只会影响计算的先后，不影响结果。

很棒。所以我们找到了另一个求表达式值的方法——

转换为树的时候，通过回溯计算值。

但是，很可惜。这个方法中，我们每一次构造的时候，要扫一次字符串并取出一个计算符。还是能用1+(2+(3+(4+(5+6))))这个例子卡成。

那怎么办？

2:表达式的变形

我们想到，一个数有它的三种遍历方式：[前|中|后]序遍历

我们把刚才这个树遍历：

前：- / + 6 * 2 3 4 5
中：6 + 2 * 3 / 4 - 5
后：6 2 3 * + 4 / 5 -

中序遍历就是原式， 但是 我们通过运算优先级建树，这时候受到括号的影响，计算的优先级会改变（括号里面的优先）。

判断的方式很简单。

就比如除号，它在树中左边是加号，运算符优先级比它小，但是竟然先被计算，所以，加号所在子树左右应该加上括号。

我们盯着[前|后]序遍历看。

前序的时候，假设有一个排列如下：

计算符 数字1 数字2


那么这三个数可以被数字1[计算符]数字2代替（就是一次计算）

后序的时候，假设有一个排列如下：

数字1 数字2 计算符

那么这三个数可以被数字1[计算符]数字2代替（就是一次计算）

这个性质由前后序遍历中根不在左右子树中间而来。

由于后序遍历的结果可以用for或in range计算（利用栈即可），我们用后序遍历的结果计算。

P.S. :表达式的[前|中|后]序遍历有对应的名字：前缀表达式（波兰表达式），中缀表达式，后缀表达式（逆波兰表达式）

3:求后缀表达式的简便方法

我们旨在用的时间求出表达式的值，所以我们只能遍历表达式常数次。

我们抓住1*2+3这个栗子看，后缀表达式为1 2 * 3 +

我们再住1+2*3这个栗子看，后缀表达式为1 2 3 * +

我们从左往右遍历这个式子，我们发现，这两个式子中，

在遍历到第二个运算符的时候，两者的操作不一样——一个将*加入后缀表达式，一个不是。

这仅仅是*和+的优先级有差异。

所以，我们实际上就是要维护一个运算优先级非降的运算符序列，在添加运算符的时候，我们仅仅需要在这个序列中去掉后面的元素，让这个序列添加这个运算符的时候依然有序。

当你维护一个单调的序列的时候，你能想到什么？

单调队列！

我们可以想到，当扫到一个数字的时候，直接加到后缀表达式里面，扫到一个运算符的时候，就把它丢到一个单调队列里面，并且这个单调队列维护的是运算优先级非降的一个字符列表。

也就是说：

* s[N],ret[N];
stack<char> pri;
for i from 1 to N
    if(s[i]是一个数)    直接加到ret中
    else
        while(pri顶部字符的优先级大于s[i]的优先级)
            把pri顶端的字符加到ret里面，之后从pri里面弹出
        把s[i]加到pri里面
while(pri里面还有字符)
    把pri顶端的字符加到ret里面，之后从pri里面弹出
ret -> 后缀表达式


好了，我们已经处理完了不含括号的时候后缀表达式的计算。

那么，当表达式有了括号的时候，怎么办呢？

我们想到，括号里面的计算符的计算优先级比外面的高，所以我们可以这样处理：

碰到(时，直接加入到队列（不进行任何弹出操作），并设置(的优先级为负无穷（这样能保证(不被弹出）
碰到)时，从pri疯狂弹出字符，直到碰到(，把(弹出

为什么要疯狂弹出呢？

很简单，我们要计算完括号里面的计算才能往下走，所以我们需要把括号里面的计算符先弹出，在后缀表达式的计算中相当于计算完括号里面的值。

所以，真正的后缀表达式的寻找方法应该是这样

* s[N],ret[N];
stack<char> pri;
for i from 1 to N
    if(s[i]是一个数)    直接加到ret中
    else if(s[i]是'(')    直接加到pri中
    else if(s[i]是')')
        while(pri顶部字符不是'(')
            把pri顶端的字符加到ret里面，之后从pri里面弹出
        从pri里面弹出'('
    else
        while(pri顶部字符的优先级大于s[i]的优先级)
            把pri顶端的字符加到ret里面，之后从pri里面弹出
        把s[i]加到pri里面
while(pri里面还有字符)
    把pri顶端的字符加到ret里面，之后从pri里面弹出
ret -> 后缀表达式


模拟(6+2*3)/4-5的计算

扫到(：直接弹入pri。
---
ret : 
pri : (
---
扫到6：直接加入ret。
---
ret : 6
pri : (
---
扫到+：加入到pri，因为(的优先级更小，所以没有弹出。
---
ret : 6
pri : ( +
---
扫到2：直接加入ret。
---
ret : 6 2
pri : ( +
---
扫到*：加入到pri，因为+的优先级更小，所以没有弹出。
---
ret : 6 2
pri : ( + *
---
扫到3：直接加入到ret。
---
ret : 6 2 3
pri : ( + *
---
扫到)：将pri中的字符疯狂弹出，直到碰到(，将(弹出。
---
ret : 6 2 3 * +
pri : 
---
扫到/：直接加入到pri（pri是空的）。
---
ret : 6 2 3 * +
pri : /
---
扫到4：直接加到ret。
---
ret : 6 2 3 * + 4
pri : /
---
扫到-：加入到pri，因为/的优先级更大，将/弹出并加入到ret。
---
ret : 6 2 3 * + 4 /
pri : -
---
扫到5：直接加入到ret。
---
ret : 6 2 3 * + 4 / 5
pri : -
---
清空pri
ret : 6 2 3 * + 4 / 5 -

因为计算的过程比较简单，所以我相信模拟可以让你们明白。

模拟计算过程：

扫到6，加入栈
+------------
| 6|  |  |  |
+------------
扫到2，加入栈
+------------
| 6| 2|  |  |
+------------
扫到3，加入栈
+------------
| 6| 2| 3|  |
+------------
扫到*，计算2*3，返回6，把6加入栈中
+------------
| 6| 6|  |  |
+------------
扫到+，计算6+6，返回12，把12加入栈中
+------------
|12|  |  |  |
+------------
扫到4，加入栈
+------------
|12| 4|  |  |
+------------
扫到/，计算12/4，返回3，把3加入栈中
+------------
| 3|  |  |  |
+------------
扫到5，加入栈
+------------
| 3| 5|  |  |
+------------
扫到-，计算3-5，返回-2，把-2加入栈中
+------------
|-2|  |  |  |
+------------
结束，返回-2


所以，表达式的计算成功降到了

4:例题

P1175 表达式的转换

注意 ： 这道题中，pri维护的是升序（不能等于），每次运算需要找到第一个字符并计算。

#include<cstdio>
#include<cstring>
#include<stack>
#include<algorithm>
#include<cmath>
using namespace std;
//8 - 18行均为运算符的优先级比较 
int ope(char q){
    if(q=='(')  return -1;
    if(q=='+')  return 0;
    if(q=='-')  return 0;
    if(q=='*')  return 1;
    if(q=='/')  return 1;
    if(q=='^')    return 2;
    return -2/*default*/;
}
bool cmp(char a,char b){
    return ope(a)>=ope(b);
}
struct Node{
    bool is_num;  //是否为运算符 
    int nm;       //数字 
    char op;      //运算符 
    Node(bool is_num=false,int nm=0,char op='\0'):is_num(is_num),nm(nm),op(op){}
}ret[105];        //后缀表达式 
stack<char> pri;
int N;            //后缀表达式长度 
char A[105];
void print(){
    for(int i=0;i<N;i++){
        if(ret[i].is_num)    printf('%d ',ret[i].nm);
        else    printf('%c ',ret[i].op);
    }
    printf('\n');
}
void solve(){
    for(int i=0;A[i];i++){
        if(A[i]>='0' && A[i]<='9')    ret[N++]=Node(true,A[i]-'0','\0');
        else if(A[i]=='(')    pri.push(A[i]);
        else if(A[i]==')'){
            while(pri.top()!='('){
                //如果保证表达式没有毛病，那么一个)一定对应一个( ，此时不用加!pri.empty() 
                ret[N++]=Node(false,0,pri.top());
                pri.pop();
            }
            pri.pop();
        }
        else{
            while(!pri.empty() && cmp(pri.top(),A[i])){
                //这里要加!pri.empty()，因为有时候在疯狂弹出的时候到头了（栗子中的/和-） 
                ret[N++]=Node(false,0,pri.top());
                pri.pop();
            }
            pri.push(A[i]);
        }
    }
    while(!pri.empty()){
        ret[N++]=Node(false,0,pri.top());
        pri.pop();
    }
    print();
    while(N!=1){
        //找到第一个计算符 
        int l=0;
        while(ret[l].is_num)    ++l;
        //暴力计算 
        switch(ret[l].op){
            case '+':
                ret[l-2]=Node(true,ret[l-2].nm+ret[l-1].nm,'\0');
                break;
            case '-':
                ret[l-2]=Node(true,ret[l-2].nm-ret[l-1].nm,'\0');
                break;
            case '*':
                ret[l-2]=Node(true,ret[l-2].nm*ret[l-1].nm,'\0');
                break;
            case '/':
                ret[l-2]=Node(true,ret[l-2].nm/ret[l-1].nm,'\0');
                break;
            case '^':
                ret[l-2]=Node(true,pow(ret[l-2].nm,ret[l-1].nm),'\0');
                break;
            default:
                break;
        }
        //往左挪两格 
        for(int i=l-1;i<N;i++)    ret[i]=ret[i+2];
        print();
        N-=2;
    } 
}
int main(){
    scanf('%s',A);
    solve();
}

提交记录

5:In the end

表达式的求值在一些大模拟题目中很常见（比如说未来程序·改中的语句）。当然，在平常编写科学计算器的时候也是一个重要的知识点。

所以，后缀表达式在表达式求值的题中节省了时间（）。

完结撒花！★,°:.☆(￣▽￣)/$:.°★ 。

放心吧，我不会推荐未来程序·改的

---

洛谷日报接受投稿，采用后有薄礼奉送,请戳 https://www./discuss/show/47327 .