我們在做一些題目的時候,需要求一些惡心的表達(dá)式的值。那么,我們需要用一些快一些的方法求值。
我們能最先想到的就是暴力求值,也就是:
一步步將可運算的地方運算好,最后剩下的就是表達(dá)式的值了。
舉個栗子:
(6+2*3)/4-5
=(6+6)/4-5
=(12)/4-5
=3-5
=-2
但是,這種方法很容易被卡掉。例如,1+(2+(3+(4+(5+6))))
這個式子中,每一次可以執(zhí)行的符號只有最里面括號的值(因為其他運算符都因為右邊的運算沒有結(jié)果而不能被運算)
這個時候時間復(fù)雜度降到了
這個時候,我們就要想一些更快的方法。
實際上,我們可以將整個表達(dá)式看成一個二叉樹,每個非葉子節(jié)點上表示的是一個運算符,左右為這個運算符在原來的表達(dá)式中左右的值。葉子節(jié)點表示的是一個值。
在計算時,我們可以用DFS的方法,在一個節(jié)點處先搜索左右兒子代表的值,之后計算。
偽代碼如下:
f() 參數(shù):一個整數(shù)。返回值:一個整數(shù)。
f(now)
if(now是葉子節(jié)點) return 這個葉子節(jié)點代表的值
return f(左兒子)[now所代表的運算符]f(右兒子)
我們還可以這么看:
很多個數(shù)排在一起。每一次,兩個相鄰的數(shù)通過某種方式(就是根代表的運算符)合并成一個數(shù),最后只剩下一個數(shù),這就是表達(dá)式的值。
舉個例子:
(6+2*3)/4-5
合并過程長這樣:
6 2 3 4 5
6 6 4 5
12 4 5
3 5
-2
過程如下:
我們通過以下方式處理字符串(又是偽代碼):
tr() 參數(shù):字符串S 返回:一棵樹
tr(S)
if(S只包含一個數(shù)字)
return 以這個數(shù)字為根的樹(只有一個節(jié)點)
找到最后運行的運算符X
將X設(shè)為這個樹的根
將左兒子設(shè)為tr(S以X為分界線分開的左邊部分)
右兒子設(shè)為tr(S以X為分界線分開的右邊部分)
return 這個樹
最后運行的運算符很好找,只要找這個表達(dá)式最外層的運算符中優(yōu)先級最小的就好(不會優(yōu)先級的出門左轉(zhuǎn))
有多個只用取其中一個,這只會影響計算的先后,不影響結(jié)果。
很棒。所以我們找到了另一個求表達(dá)式值的方法——
轉(zhuǎn)換為樹的時候,通過回溯計算值。
但是,很可惜。這個方法中,我們每一次構(gòu)造的時候,要掃一次字符串并取出一個計算符。還是能用1+(2+(3+(4+(5+6))))
這個例子卡成
那怎么辦?
我們想到,一個數(shù)有它的三種遍歷方式:[前|中|后]序遍歷
我們把剛才這個樹遍歷:
前:- / + 6 * 2 3 4 5
中:6 + 2 * 3 / 4 - 5
后:6 2 3 * + 4 / 5 -
中序遍歷就是原式, 但是 我們通過運算優(yōu)先級建樹,這時候受到括號的影響,計算的優(yōu)先級會改變(括號里面的優(yōu)先)。
判斷的方式很簡單。
就比如除號,它在樹中左邊是加號,運算符優(yōu)先級比它小,但是竟然先被計算,所以,加號所在子樹左右應(yīng)該加上括號。
我們盯著[前|后]序遍歷
看。
前序的時候,假設(shè)有一個排列如下:
計算符 數(shù)字1 數(shù)字2
那么這三個數(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á)式)
我們旨在用
我們抓住1*2+3
這個栗子看,后綴表達(dá)式為1 2 * 3 +
我們再住1+2*3
這個栗子看,后綴表達(dá)式為1 2 3 * +
我們從左往右遍歷這個式子,我們發(fā)現(xiàn),這兩個式子中,
在遍歷到第二個運算符的時候,兩者的操作不一樣——一個將*
加入后綴表達(dá)式,一個不是。
這僅僅是*
和+
的優(yōu)先級有差異。
所以,我們實際上就是要維護(hù)一個運算優(yōu)先級非降的運算符序列,在添加運算符的時候,我們僅僅需要在這個序列中去掉后面的元素,讓這個序列添加這個運算符的時候依然有序。
當(dāng)你維護(hù)一個單調(diào)的序列的時候,你能想到什么?
我們可以想到,當(dāng)掃到一個數(shù)字的時候,直接加到后綴表達(dá)式里面,掃到一個運算符的時候,就把它丟到一個單調(diào)隊列里面,并且這個單調(diào)隊列維護(hù)的是運算優(yōu)先級非降的一個字符列表。
也就是說:
* s[N],ret[N];
stack<char> pri;
for i from 1 to N
if(s[i]是一個數(shù)) 直接加到ret中
else
while(pri頂部字符的優(yōu)先級大于s[i]的優(yōu)先級)
把pri頂端的字符加到ret里面,之后從pri里面彈出
把s[i]加到pri里面
while(pri里面還有字符)
把pri頂端的字符加到ret里面,之后從pri里面彈出
ret -> 后綴表達(dá)式
好了,我們已經(jīng)處理完了不含括號的時候后綴表達(dá)式的計算。
那么,當(dāng)表達(dá)式有了括號的時候,怎么辦呢?
我們想到,括號里面的計算符的計算優(yōu)先級比外面的高,所以我們可以這樣處理:
碰到(時,直接加入到隊列(不進(jìn)行任何彈出操作),并設(shè)置(的優(yōu)先級為負(fù)無窮(這樣能保證(不被彈出)
碰到)時,從pri瘋狂彈出字符,直到碰到(,把(彈出
為什么要瘋狂彈出呢?
很簡單,我們要計算完括號里面的計算才能往下走,所以我們需要把括號里面的計算符先彈出,在后綴表達(dá)式的計算中相當(dāng)于計算完括號里面的值。
所以,真正的后綴表達(dá)式的尋找方法應(yīng)該是這樣
* s[N],ret[N];
stack<char> pri;
for i from 1 to N
if(s[i]是一個數(shù)) 直接加到ret中
else if(s[i]是'(') 直接加到pri中
else if(s[i]是')')
while(pri頂部字符不是'(')
把pri頂端的字符加到ret里面,之后從pri里面彈出
從pri里面彈出'('
else
while(pri頂部字符的優(yōu)先級大于s[i]的優(yōu)先級)
把pri頂端的字符加到ret里面,之后從pri里面彈出
把s[i]加到pri里面
while(pri里面還有字符)
把pri頂端的字符加到ret里面,之后從pri里面彈出
ret -> 后綴表達(dá)式
模擬(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 -
因為計算的過程比較簡單,所以我相信模擬可以讓你們明白。
模擬計算過程:
掃到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| | | |
+------------
結(jié)束,返回-2
所以,表達(dá)式的計算成功降到了
注意 : 這道題中,pri維護(hù)的是升序(不能等于),每次運算需要找到第一個字符并計算。
#include<cstdio>
#include<cstring>
#include<stack>
#include<algorithm>
#include<cmath>
using namespace std;
//8 - 18行均為運算符的優(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; //是否為運算符
int nm; //數(shù)字
char op; //運算符
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();
}
表達(dá)式的求值在一些大模擬題目中很常見(比如說未來程序·改中的語句)。當(dāng)然,在平常編寫科學(xué)計算器的時候也是一個重要的知識點。
所以,后綴表達(dá)式在表達(dá)式求值的題中節(jié)省了時間(
放心吧,我不會推薦未來程序·改的