逆波蘭式

實現(xiàn)逆波蘭式的算法，難度并不大，但為什么要將看似簡單的中序表達式轉(zhuǎn)換為復(fù)雜的逆波蘭式?原因就在于這個簡單是相對人類的思維結(jié)構(gòu)來說的，對計算機而言中序表達式是非常復(fù)雜的結(jié)構(gòu)。相對的，逆波蘭式在計算機看來卻是比較簡單易懂的結(jié)構(gòu)。因為計算機普遍采用的內(nèi)存結(jié)構(gòu)是棧式結(jié)構(gòu)，它執(zhí)行先進后出的順序。

新建一個表達式,如果當(dāng)前字符為變量或者為數(shù)字，則壓棧，如果是運算符，則將棧頂兩個元素彈出作相應(yīng)運算，結(jié)果再入棧，最后當(dāng)表達式掃描完后，棧里的就是結(jié)果。

將一個普通的中序表達式轉(zhuǎn)換為逆波蘭表達式的一般算法是:

首先需要分配2個棧，一個作為臨時存儲運算符的棧S1(含一個結(jié)束符號)，一個作為輸入逆波蘭式的棧S2(空棧)，S1?？上确湃雰?yōu)先級最低的運算符#，注意，中綴式應(yīng)以此最低優(yōu)先級的運算符結(jié)束?？芍付ㄆ渌址?，不一定非#不可。從中綴式的左端開始取字符，逐序進行如下步驟:

(1)若取出的字符是操作數(shù)，則分析出完整的運算數(shù)，該操作數(shù)直接送入S2棧

(2)若取出的字符是運算符，則將該運算符與S1棧棧頂元素比較，如果該運算符優(yōu)先級大于S1棧棧頂運算符優(yōu)先級，則將該運算符進S1棧，否則，將S1棧的棧頂運算符彈出，送入S2棧中，直至S1棧棧頂運算符低于(不包括等于)該運算符優(yōu)先級，最后將該運算符送入S1棧。

(3)若取出的字符是"("，則直接送入S1棧頂。

(4)若取出的字符是")"，則將距離S1棧棧頂最近的"("之間的運算符，逐個出棧，依次送入S2棧，此時拋棄"("。

(5)重復(fù)上面的1~4步，直至處理完所有的輸入字符

(6)若取出的字符是"#"，則將S1棧內(nèi)所有運算符(不包括"#")，逐個出棧，依次送入S2棧。

完成以上步驟，S2棧便為逆波蘭式輸出結(jié)果。不過S2應(yīng)做一下逆序處理。便可以按照逆波蘭式的計算方法計算了!

一個表達式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/-

下面以(a+b)*c為例子進行說明:

(a+b)*c的逆波蘭式為ab+c*，假設(shè)計算機把ab+c*按從左到右的順序壓入棧中，并且按照遇到運算符就把棧頂兩個元素出棧，執(zhí)行運算，得到的結(jié)果再入棧的原則來進行處理，那么ab+c*的執(zhí)行結(jié)果如下:

1)a入棧(0位置)

2)b入棧(1位置)

3)遇到運算符"+"，將a和b出棧，執(zhí)行a+b的操作，得到結(jié)果d=a+b，再將d入棧(0位置)

4)c入棧(1位置)

5)遇到運算符"*"，將d和c出棧，執(zhí)行d*c的操作，得到結(jié)果e，再將e入棧(0位置)

經(jīng)過以上運算，計算機就可以得到(a+b)*c的運算結(jié)果e了。

逆波蘭式除了可以實現(xiàn)上述類型的運算，它還可以派生出許多新的算法，數(shù)據(jù)結(jié)構(gòu)，這就需要靈活運用了。逆波蘭式只是一種序列體現(xiàn)形式。

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叉樹.

其中△代表一個標(biāo)識，ω代表預(yù)算法，名字Q代表變量(如int a，b等)，

算法用到三個棧:a棧，b棧，in棧。

其中a棧用來存儲逆波蘭式，b用來存儲△號和運算符，in棧為輸入棧。

第一豎排為b棧中符號，第一橫排為輸入棧中符號。

pop(in)為輸入棧棧頂元素出棧，pop(a，Q)為Q入a棧，NEXT算法即為進行下一輪循環(huán)，其中ω1<ω2為算符優(yōu)先級，如"+"和"-"<"*"和"/"。pop(b，B)，push(b，B)中B為臨時變量，用來存儲出棧的元素。stop為算法結(jié)束。

算法開始時，現(xiàn)將△如b棧，輸入棧以#號結(jié)尾。

?

將最終進行的運算符記為根節(jié)點，將兩邊的表達式分別記為左右子樹，依次進行直到所有的運算符與數(shù)字或字母標(biāo)在一棵二叉樹上。然后對二叉樹進行后序遍歷即可。

主要有閥體，搖桿，閥蓋，閥座，密封座等組成，工作時，氣體在一定壓力作用下頂開閥蓋由進氣口進入止逆閥內(nèi)，由出口流出，當(dāng)空氣壓力突然減小時，閥蓋在搖桿的帶動下，自動將閥座蓋住，起到密封作用，這樣氣體不會倒流。