0:序言

我們?cè)谧鲆恍╊}目的時(shí)候，需要求一些惡心的表達(dá)式的值。那么，我們需要用一些快一些的方法求值。

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

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

舉個(gè)栗子：

但是，這種方法很容易被卡掉。例如，1+(2+(3+(4+(5+6))))這個(gè)式子中，每一次可以執(zhí)行的符號(hào)只有最里面括號(hào)的值（因?yàn)槠渌\(yùn)算符都因?yàn)橛疫叺倪\(yùn)算沒有結(jié)果而不能被運(yùn)算）

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

這個(gè)時(shí)候，我們就要想一些更快的方法。

1:表達(dá)式的樹

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

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

偽代碼如下：

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

我們還可以這么看：

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

舉個(gè)例子：

合并過程長(zhǎng)這樣：

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

過程如下：

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

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

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

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

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

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

那怎么辦？

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

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

我們把剛才這個(gè)樹遍歷：

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

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

判斷的方式很簡(jiǎn)單。

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

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

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

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

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

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

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

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

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

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

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

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

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

我們?cè)僮?code>1+2*3這個(gè)栗子看，后綴表達(dá)式為1 2 3 * +

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

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

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

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

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

單調(diào)隊(duì)列！

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

也就是說：

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

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

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

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

為什么要瘋狂彈出呢？

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

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

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

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

因?yàn)橛?jì)算的過程比較簡(jiǎn)單，所以我相信模擬可以讓你們明白。

模擬計(jì)算過程：

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

4:例題

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

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

#include<cstdio>
#include<cstring>
#include<stack>
#include<algorithm>
#include<cmath>
using namespace std;
//8 - 18行均為運(yùn)算符的優(yōu)先級(jí)比較 
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á)式長(zhǎng)度 
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)]有毛病，那么一個(gè))一定對(duì)應(yīng)一個(gè)( ，此時(shí)不用加!pri.empty() 
                ret[N++]=Node(false,0,pri.top());
                pri.pop();
            }
            pri.pop();
        }
        else{
            while(!pri.empty() && cmp(pri.top(),A[i])){
                //這里要加!pri.empty()，因?yàn)橛袝r(shí)候在瘋狂彈出的時(shí)候到頭了（栗子中的/和-） 
                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){
        //找到第一個(gè)計(jì)算符 
        int l=0;
        while(ret[l].is_num)    ++l;
        //暴力計(jì)算 
        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é)計(jì)算器的時(shí)候也是一個(gè)重要的知識(shí)點(diǎn)。

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

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

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