-
逆波蘭式
鎖定
逆波蘭式算法定義
一個表達式E的後綴形式可以如下定義:
(1)如果E是一個變量或常量,則E的後綴式是E本身。
(2)如果E是E1 op E2形式的表達式,這裏op是任何二元操作符,則E的後綴式為E1'E2' op,這裏E1'和E2'分別為E1和E2的後綴式。
(3)如果E是(E1)形式的表達式,則E1的後綴式就是E的後綴式。
如:我們平時寫a+b,這是中綴表達式,寫成後綴表達式就是:ab+
(a+b)*c-(a+b)/e的後綴表達式為:
(a+b)*c-(a+b)/e
→((a+b)*c)((a+b)/e)-
→((a+b)c*)((a+b)e/)-
→(ab+c*)(ab+e/)-
→ab+c*ab+e/-
逆波蘭式算法作用
實現逆波蘭式的算法,難度並不大,但為什麼要將看似簡單的中綴表達式轉換為複雜的逆波蘭式?原因就在於這個簡單是相對人類的思維結構來説的,對計算機而言中序表達式是非常複雜的結構。相對的,逆波蘭式在計算機看來卻是比較簡單易懂的結構。因為計算機普遍採用的內存結構是棧式結構,它執行先進後出的順序。
逆波蘭式算法實現
將一個普通的中綴表達式轉換為逆波蘭表達式的一般算法是:
首先需要分配2個棧,一個作為臨時存儲運算符的棧S1(含一個結束符號),一個作為存放結果(逆波蘭式)的棧S2(空棧),S1棧可先放入優先級最低的運算符#,注意,中綴式應以此最低優先級的運算符結束。可指定其他字符,不一定非#不可。從中綴式的左端開始取字符,逐序進行如下步驟:
(1)若取出的字符是操作數,則分析出完整的運算數,該操作數直接送入S2棧。
(2)若取出的字符是運算符,則將該運算符與S1棧棧頂元素比較,如果該運算符(不包括括號運算符)優先級高於S1棧棧頂運算符(包括左括號)優先級,則將該運算符進S1棧,否則,將S1棧的棧頂運算符彈出,送入S2棧中,直至S1棧棧頂運算符(包括左括號)低於(不包括等於)該運算符優先級時停止彈出運算符,最後將該運算符送入S1棧。
(3)若取出的字符是“(”,則直接送入S1棧頂。
(4)若取出的字符是“)”,則將距離S1棧棧頂最近的“(”之間的運算符,逐個出棧,依次送入S2棧,此時拋棄“(”。
(5)重複上面的1~4步,直至處理完所有的輸入字符。
(6)若取出的字符是“#”,則將S1棧內所有運算符(不包括“#”),逐個出棧,依次送入S2棧。
完成以上步驟,S2棧便為逆波蘭式輸出結果。不過S2應做一下逆序處理。便可以按照逆波蘭式的計算方法計算了!
逆波蘭式計算方法
逆波蘭式算法舉例
下面以(a+b)*c為例子進行説明:
(a+b)*c的逆波蘭式為ab+c*,假設計算機把ab+c*按從左到右的順序壓入棧中,並且按照遇到運算符就把棧頂兩個元素出棧,執行運算,得到的結果再入棧的原則來進行處理,那麼ab+c*的執行結果如下:
(1)a入棧(0位置)
(2)b入棧(1位置)
(3)遇到運算符“+”,將a和b出棧,執行a+b的操作,得到結果d=a+b,再將d入棧(0位置)
(4)c入棧(1位置)
(5)遇到運算符“*”,將d和c出棧,執行d*c的操作,得到結果e,再將e入棧(0位置)
經過以上運算,計算機就可以得到(a+b)*c的運算結果e了。
逆波蘭式除了可以實現上述類型的運算,它還可以派生出許多新的算法,數據結構,這就需要靈活運用了。逆波蘭式只是一種序列體現形式。
逆波蘭式算法圖示
其中△代表一個標識,ω代表預算法,名字Q代表變量(如int a,b等),
算法用到三個棧:a棧,b棧,in棧。
其中a棧用來存儲逆波蘭式,b用來存儲△號和運算符,in棧為輸入棧。
第一豎排為b棧中符號,第一橫排為輸入棧中符號。
pop(in)為輸入棧棧頂元素出棧,pop(a,Q)為Q入a棧,NEXT算法即為進行下一輪循環,其中ω1
算法開始時,現將△如b棧,輸入棧以#號結尾。
輸入流 b[s-1] | 名字Q | ( | ω2 | ) | # |
△ | POP(in); PUSH(a,Q) NEXT | POP(in); PUSH(b,△) NEXT | POP(in) PUSH(b,ω2) NEXT | POP(in) POP(b,B) NEXT | STOP |
ω1 | POP(in) PUSH(a,Q) NEXT | POP(in) PUSH(b,△) NEXT | 若ω1 POP(in) PUSH(b,ω2) NEXT 若ω1≥ω2,則POP(in) POP(b,B), PUSH(a,B) | POP(b,B) PUSH(a,B) | POP(b,B) PUSH(a,B) |
逆波蘭式程序實現
C/C++語言版
//#include<iostream> #include <stdlib.h> #include <stdio.h> #include <stack> #include <math.h> #include <string.h> #definemax100 usingnamespacestd; char ex[max]; /*存儲後綴表達式*/ voidtrans() { /*將算術表達式轉化為後綴表達式*/ char str[max]; /*存儲原算術表達式*/ char stack[max]; /*作為棧使用*/ char ch; int sum, i, j, t, top = 0; printf("*****************************************\n"); printf("*輸入一個求值的表達式,以#結束。*\n"); printf("******************************************\n"); printf("算數表達式:"); i = 0; /*獲取用户輸入的表達式*/ do { i++; //cin>>str[i];/*此步我用的是C++C語言的話在後面之所以用這個有一點區別都*/ scanf("%c", &str[i]); } while (str[i] != '#' && i != max); sum = i; t = 1; i = 1; ch = str[i]; i++; // while (ch != '#') { switch (ch) { case '(': /*判定為左括號*/ top++; stack[top] = ch; break; case ')': /*判定為右括號*/ while (stack[top] != '(') { ex[t] = stack[top]; top--; t++; } top--; break; case '+': /*判定為加減號*/ case '-': while (top != 0 && stack[top] != '(') { ex[t] = stack[top]; top--; t++; } top++; stack[top] = ch; break; case '*': /*判定為乘除號*/ case '/': while (stack[top] == '*' || stack[top] == '/') { ex[t] = stack[top]; top--; t++; } top++; stack[top] = ch; break; case'': break; default: while (ch >= '0' && ch <= '9') { /*判定為數字*/ ex[t] = ch; t++; ch = str[i]; i++; } i--; ex[t] =''; t++; } ch = str[i]; i++; } while (top != 0) { ex[t] = stack[top]; t++; top--; } ex[t] =''; printf("\n\t原來表達式:"); for (j = 1; j < sum; j++) printf("%c", str[j]); printf("\n\t逆波蘭式:", ex); for (j = 1; j < t; j++) printf("%c", ex[j]); } voidcompvalue() { /*計算後綴表達式的值*/ floatstack[max], d; /*作為棧使用*/ charch; intt = 1, top = 0; /*t為ex下標,top為stack下標*/ ch = ex[t]; t++; while (ch !='') { switch (ch) { case '+': stack[top - 1] = stack[top - 1] + stack[top]; top--; break; case '-': stack[top - 1] = stack[top - 1] - stack[top]; top--; break; case '*': stack[top - 1] = stack[top - 1] * stack[top]; top--; break; case '/': if (stack[top] != 0) stack[top - 1] = stack[top - 1] / stack[top]; else { printf("\n\t除零錯誤!\n"); exit(0); /*異常退出*/ } top--; break; default: d = 0; while (ch >= '0' && ch <= '9') { d = 10 * d + ch - '0'; /*將數字字符轉化為對應的數值*/ ch = ex[t]; t++; } top++; stack[top] = d; } ch = ex[t]; t++; } printf("\n\t計算結果:%g\n", stack[top]); } intmain() { trans(); compvalue(); system("pause"); return 0; }
數據結構版
int precede(char op){ int x; switch(op){ case '*': x=2; break; case '/': x=2; break; case '+': x=1; break; case '-': x=1; break; default : x=0; } return x; } char *RPExpression(char *e){ /* 返回表達式e的逆波蘭式 */ char *c; c=(char*)malloc(sizeof(char)*20); //不能用char c[]Stack s1;InitStack(s1); int i=0,j=0; char ch; Push(s1,'@'); ch=e[i++]; while(ch!= 0){ if(ch=='('){ Push(s1,ch); ch=e[i++]; } else if(ch==')'){ while(Top(s1)!='('){ Pop(s1,c[j++]); } /* to[j++]=pop(&s1);*/ Pop(s1,ch); ch=e[i++]; }else if(ch=='+'||ch=='-'||ch=='*'||ch=='/'){ char w; w=Top(s1); while(precede(w)>=precede(ch)){ Pop(s1,c[j++]); w=Top(s1); } Push(s1,ch); ch=e[i++]; }else{ //while((ch='a')||(ch='A')){c[j++]=ch;ch=e[i++]; //} //c[j++]=' ';} } Pop(s1,ch); while(ch!='@'){ c[j++]=ch; Pop(s1,ch); } //c[j++]=;c[j++]=0; return c; }
還有一種方法,用二叉樹。