0:序言

我們在做一些題目的時候，需要求一些惡心的表達(dá)式的值。那么，我們需要用一些快一些的方法求值。

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

一步步將可運(yùn)算的地方運(yùn)算好，最后剩下的就是表達(dá)式的值了。

舉個栗子：

但是，這種方法很容易被卡掉。例如，1+(2+(3+(4+(5+6))))這個式子中，每一次可以執(zhí)行的符號只有最里面括號的值（因為其他運(yùn)算符都因為右邊的運(yùn)算沒有結(jié)果而不能被運(yùn)算）

這個時候時間復(fù)雜度降到了，非常慢。

這個時候，我們就要想一些更快的方法。

1:表達(dá)式的樹

實際上，我們可以將整個表達(dá)式看成一個二叉樹，每個非葉子節(jié)點上表示的是一個運(yùn)算符，左右為這個運(yùn)算符在原來的表達(dá)式中左右的值。葉子節(jié)點表示的是一個值。

在計算時，我們可以用DFS的方法，在一個節(jié)點處先搜索左右兒子代表的值，之后計算。

偽代碼如下：

f() 參數(shù)：一個整數(shù)。返回值：一個整數(shù)。
f(now) 
    if(now是葉子節(jié)點)    return 這個葉子節(jié)點代表的值
    return f(左兒子)[now所代表的運(yùn)算符]f(右兒子)

我們還可以這么看：

很多個數(shù)排在一起。每一次，兩個相鄰的數(shù)通過某種方式（就是根代表的運(yùn)算符）合并成一個數(shù)，最后只剩下一個數(shù)，這就是表達(dá)式的值。

舉個例子：

合并過程長這樣：

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

過程如下：

我們通過以下方式處理字符串（又是偽代碼）：

最后運(yùn)行的運(yùn)算符很好找，只要找這個表達(dá)式最外層的運(yùn)算符中優(yōu)先級最小的就好（不會優(yōu)先級的出門左轉(zhuǎn)）

有多個只用取其中一個，這只會影響計算的先后，不影響結(jié)果。

很棒。所以我們找到了另一個求表達(dá)式值的方法——

轉(zhuǎn)換為樹的時候，通過回溯計算值。

但是，很可惜。這個方法中，我們每一次構(gòu)造的時候，要掃一次字符串并取出一個計算符。還是能用1+(2+(3+(4+(5+6))))這個例子卡成。

那怎么辦？

2:表達(dá)式的變形

我們想到，一個數(shù)有它的三種遍歷方式：[前|中|后]序遍歷

我們把剛才這個樹遍歷：

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

中序遍歷就是原式， 但是 我們通過運(yùn)算優(yōu)先級建樹，這時候受到括號的影響，計算的優(yōu)先級會改變（括號里面的優(yōu)先）。

判斷的方式很簡單。

就比如除號，它在樹中左邊是加號，運(yùn)算符優(yōu)先級比它小，但是竟然先被計算，所以，加號所在子樹左右應(yīng)該加上括號。

我們盯著[前|后]序遍歷看。

前序的時候，假設(shè)有一個排列如下：

那么這三個數(shù)可以被數(shù)字1[計算符]數(shù)字2代替（就是一次計算）

后序的時候，假設(shè)有一個排列如下：

數(shù)字1 數(shù)字2 計算符

那么這三個數(shù)可以被數(shù)字1[計算符]數(shù)字2代替（就是一次計算）

這個性質(zhì)由前后序遍歷中根不在左右子樹中間而來。

由于后序遍歷的結(jié)果可以用for或in range計算（利用棧即可），我們用后序遍歷的結(jié)果計算。

P.S. :表達(dá)式的[前|中|后]序遍歷有對應(yīng)的名字：前綴表達(dá)式（波蘭表達(dá)式），中綴表達(dá)式，后綴表達(dá)式（逆波蘭表達(dá)式）

3:求后綴表達(dá)式的簡便方法

我們旨在用的時間求出表達(dá)式的值，所以我們只能遍歷表達(dá)式常數(shù)次。

我們抓住1*2+3這個栗子看，后綴表達(dá)式為1 2 * 3 +

我們再住1+2*3這個栗子看，后綴表達(dá)式為1 2 3 * +

我們從左往右遍歷這個式子，我們發(fā)現(xiàn)，這兩個式子中，

在遍歷到第二個運(yùn)算符的時候，兩者的操作不一樣——一個將*加入后綴表達(dá)式，一個不是。

這僅僅是*和+的優(yōu)先級有差異。

所以，我們實際上就是要維護(hù)一個運(yùn)算優(yōu)先級非降的運(yùn)算符序列，在添加運(yùn)算符的時候，我們僅僅需要在這個序列中去掉后面的元素，讓這個序列添加這個運(yùn)算符的時候依然有序。

當(dāng)你維護(hù)一個單調(diào)的序列的時候，你能想到什么？

單調(diào)隊列！

我們可以想到，當(dāng)掃到一個數(shù)字的時候，直接加到后綴表達(dá)式里面，掃到一個運(yùn)算符的時候，就把它丟到一個單調(diào)隊列里面，并且這個單調(diào)隊列維護(hù)的是運(yùn)算優(yōu)先級非降的一個字符列表。

也就是說：

好了，我們已經(jīng)處理完了不含括號的時候后綴表達(dá)式的計算。

那么，當(dāng)表達(dá)式有了括號的時候，怎么辦呢？

我們想到，括號里面的計算符的計算優(yōu)先級比外面的高，所以我們可以這樣處理：

碰到(時，直接加入到隊列（不進(jìn)行任何彈出操作），并設(shè)置(的優(yōu)先級為負(fù)無窮（這樣能保證(不被彈出）
碰到)時，從pri瘋狂彈出字符，直到碰到(，把(彈出

為什么要瘋狂彈出呢？

很簡單，我們要計算完括號里面的計算才能往下走，所以我們需要把括號里面的計算符先彈出，在后綴表達(dá)式的計算中相當(dāng)于計算完括號里面的值。

所以，真正的后綴表達(dá)式的尋找方法應(yīng)該是這樣

模擬(6+2*3)/4-5的計算

掃到(：直接彈入pri。
---
ret : 
pri : (
---
掃到6：直接加入ret。
---
ret : 6
pri : (
---
掃到+：加入到pri，因為(的優(yōu)先級更小，所以沒有彈出。
---
ret : 6
pri : ( +
---
掃到2：直接加入ret。
---
ret : 6 2
pri : ( +
---
掃到*：加入到pri，因為+的優(yōu)先級更小，所以沒有彈出。
---
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，因為/的優(yōu)先級更大，將/彈出并加入到ret。
---
ret : 6 2 3 * + 4 /
pri : -
---
掃到5：直接加入到ret。
---
ret : 6 2 3 * + 4 / 5
pri : -
---
清空pri
ret : 6 2 3 * + 4 / 5 -

因為計算的過程比較簡單，所以我相信模擬可以讓你們明白。

模擬計算過程：

所以，表達(dá)式的計算成功降到了

4:例題

P1175 表達(dá)式的轉(zhuǎn)換

注意 ： 這道題中，pri維護(hù)的是升序（不能等于），每次運(yùn)算需要找到第一個字符并計算。

#include<cstdio>
#include<cstring>
#include<stack>
#include<algorithm>
#include<cmath>
using namespace std;
//8 - 18行均為運(yùn)算符的優(yōu)先級比較 
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;  //是否為運(yùn)算符 
    int nm;       //數(shù)字 
    char op;      //運(yùn)算符 
    Node(bool is_num=false,int nm=0,char op='\0'):is_num(is_num),nm(nm),op(op){}
}ret[105];        //后綴表達(dá)式 
stack<char> pri;
int N;            //后綴表達(dá)式長度 
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()!='('){
                //如果保證表達(dá)式?jīng)]有毛病，那么一個)一定對應(yīng)一個( ，此時不用加!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

表達(dá)式的求值在一些大模擬題目中很常見（比如說未來程序·改中的語句）。當(dāng)然，在平常編寫科學(xué)計算器的時候也是一個重要的知識點。

所以，后綴表達(dá)式在表達(dá)式求值的題中節(jié)省了時間（）。

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

放心吧，我不會推薦未來程序·改的