逆波蘭式

逆波蘭式

逆波蘭式(Reverse Polish notation,RPN,或逆波蘭記法),也叫後綴表達式(將運算符寫在運算元之後)

定義

一個表達式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<ω2為算符優先權,如“+”和“-”<“*”和“/”。pop(b,B),push(b,B)中B為臨時變數,用來存儲出棧的元素。stop為算法結束。

算法開始時,現將△如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<ω2,則 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++語言版

數據結構版

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<="z"&&ch>="a")||(ch<="Z" && 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;

}

還有一種方法,用2叉樹.

二叉樹法

將最終進行的運算符記為根節點,將兩邊的表達式分別記為左右子樹,依次進行直到所有的運算符與數字或字母標在一棵二叉樹上。然後對二叉樹進行後序遍歷即可。

相關詞條

相關搜尋

熱門詞條

聯絡我們