資源描述：
《波蘭式轉(zhuǎn)換為逆波蘭式》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。
1、波蘭式轉(zhuǎn)換為逆波蘭式（中綴表達式轉(zhuǎn)換為后綴表達式）逆波蘭式（ReversePolishnotation，RPN，或逆波蘭記法），也叫后綴表達式（將運算符寫在操作數(shù)之后）一、定義一個表達式E的后綴形式可以如下定義：（1）如果E是一個變量或常量，則E的后綴式是E本身。（2）如果E是E1opE2形式的表達式，這里op是如何二元操作符，則E的后綴式為E1'E2'op，這里E1'和E2'分別為E1和E2的后綴式。（3)如果E是（E1）形式的表達式，則E1的后綴式就是E的后綴式。如：我們平時寫a+b，這是中綴表達式，寫成后綴表達式就是：
2、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/-二、算法實現(xiàn)將一個普通的中序表達式轉(zhuǎn)換為逆波蘭表達式的一般算法是：首先需要分配2個棧，一個作為臨時存儲運算符的棧S1（含一個結(jié)束符號），一個作為輸入逆波蘭式的棧S2（空棧），S1?？上确湃雰?yōu)先級最低的運算符#，注意，中綴式應(yīng)以此最低優(yōu)先級的運算符結(jié)束?？芍付ㄆ渌址?，不一定非#不可。從中綴式的左端開始取字符，逐
3、序進行如下步驟：（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步
4、，直至處理完所有的輸入字符（6）若取出的字符是“#”，則將S1棧內(nèi)所有運算符（不包括“#”），逐個出棧，依次送入S2棧。完成以上步驟，S2棧便為逆波蘭式輸出結(jié)果。不過S2應(yīng)做一下逆序處理。便可以按照逆波蘭式的計算方法計算了！三、作用實現(xiàn)逆波蘭式的算法，難度并不大，但為什么要將看似簡單的中序表達式轉(zhuǎn)換為復(fù)雜的逆波蘭式？原因就在于這個簡單是相對人類的思維結(jié)構(gòu)來說的，對計算機而言中序表達式是非常復(fù)雜的結(jié)構(gòu)。相對的，逆波蘭式在計算機看來卻是比較簡單易懂的結(jié)構(gòu)。因為計算機普遍采用的內(nèi)存結(jié)構(gòu)是棧式結(jié)構(gòu)，它執(zhí)行先進后出的順序。四、舉例下面
5、以(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了
6、。逆波蘭式除了可以實現(xiàn)上述類型的運算，它還可以派生出許多新的算法，數(shù)據(jù)結(jié)構(gòu)，這就需要靈活運用了。逆波蘭式只是一種序列體現(xiàn)形式。五、程序?qū)崿F(xiàn)//逆波蘭式（C語言版）#include#include#include#include#definemax100charex[max];/*存儲后綴表達式*/voidtrans(){/*將算術(shù)表達式轉(zhuǎn)化為后綴表達式*/charstr[max];/*存儲原算術(shù)表達式*/charstack[max];/*作為棧使用
7、*/charch;intsum,i,j,t,top=0;printf("*****************************************");printf("*輸入一個求值的表達式，以#結(jié)束。*");printf("******************************************");printf("算數(shù)表達式：");i=0;/*獲取用戶輸入的表達式*/do{i++;cin>>str[i];/*此步我用的是C++C語言的話在后面之所以用這個有一點區(qū)別都*///scanf("%
8、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'
