逆波蘭式算法的源代碼

1、.實驗目的深入理解算符優(yōu)先分析法掌握FirstVt和LastVt集合的求法有算符優(yōu)先關系表的求法掌握利用算符優(yōu)先分析法完成中綴表達式到逆波蘭式的轉化.實驗內容及要求將非后綴式用來表示的算術表達式轉換為用逆波蘭式來表示的算術表達式，并計算用逆波蘭式來表示的算術表達式的值。程序輸入J輸出示例：輸出的格式如卜：逆波蘭式的生成及計算程序，編制人：|姓名，學號，班瓦輸入一以#結束的中綴表達式(包括*/ ()數字#): |在此位置輸入符號串如(28+68)*2御逆波蘭式為：|28&68+2*逆波蘭式|28&68+2*|計算結果為|192|備注：(1)在生成的逆波蘭式中如果兩個數相連則用&分隔，如28和68

2、,中間用&分隔；|在此位置輸入符號串|為用戶自行輸入的符號串。注意：1.表達式中允許使用運算符(+-*/)、分割符(括號)、數字，結束符#;如果遇到錯誤的表達式，應輸出錯誤提示信息(該信息越詳細越好)；對學有余力的同學，測試用的表達式事先放在文本文件中，一行存放一個表達式，同時以 分號分割。同時將預期的輸出結果寫在另一個文本文件中，以便和輸出進行對照：三.實驗過程1、逆波蘭式定義將運算對象寫在前面，而把運算符號寫在后面。用這種表示法表示的表達式也稱 做后綴式。逆波蘭式的特點在于運算對象順序不變，運算符號位置反映運算順序。采用 逆波蘭式可以很好的表示簡單算術表達式，其優(yōu)點在于易于計算機處理表達式

3、。2、產生逆波蘭式的前提中綴算術表達式3、逆波蘭式生成的實驗設計思想及算法首先構造一個運算符棧，此運算符在棧內遵循越往棧頂優(yōu)先級越高的原則。讀入一個用中綴表示的簡單算術表達式，為方便起見，設該簡單算術表達式的右端多 加上了優(yōu)先級最低的特殊符號從左至右掃描該算術表達式，從第一個字符開始判斷，如果該字符是數字，則分析 到該數字串的結束并將該數字串直接輸出。如果不是數字，該字符則是運算符，此時需比較優(yōu)先關系。做法如下：將該字符與運算符棧頂的運算符的優(yōu)先關系相比較。如果，該字符優(yōu)先關系 高于此運算符棧頂的運算符，則將該運算符入棧。倘若不是的話，則將此運算符棧頂的運算符從棧中彈出，將該字符入棧。重復上述

4、操作(1)-(2)直至掃描完整個簡單算術表達式，確定所有字符都得到正確處 理，我們便可以將中綴式表示的簡單算術表達式轉化為逆波蘭表示的簡單算術表達式。3、逆波蘭式計算的實驗設計思想及算法構造一個棧，存放運算對象。讀入一個用逆波蘭式表示的簡單算術表達式。自左至右掃描該簡單算術表達式并判斷該字符，如果該字符是運算對象，則將 該字符入棧。若是運算符，如果此運算符是二目運算符，則將對棧頂部的兩個運算對象 進行該運算，將運算結果入棧，并旦將執(zhí)行該運算的兩個運算對象從棧頂彈出。如果該 字符是一目運算符，則對棧頂部的元素實施該運算，將該棧頂部的元素彈出，將運算結 果入棧。重復上述操作直至掃描完整個簡單算術表

5、達式的逆波蘭式，確定所有字符都得 到正確處理，我們便可以求出該簡單算術表達式的值。實驗的源程序代碼如下：#include#include棄define max 100char exmax;void trans0/*char exmax;void trans0/*將算術表達式轉化為后綴表達式*/clw strniax;/*存儲原算術表達式*/clw stackniax;/*作為棧使用*/char ch;int sum,i,j,t,top=0;pnntff*輸入一個求值的表達式，以#結束。int sum,i,j,t,top=0;pnntff*輸入一個求值的表達式，以#結束。*1T);p 血 w*

6、*f pnntf(”算數表達式：，】=0；/*獲取用戶輸入的表達式*/do(i+;scanf(”c”.&stri);while(stri!=# & i!=max);sum=i;t=l；i=l； ch=stri;i+;while(ch!=#)switch(ch)(case (,：/*判定為左括號*/top+;stacktop=ch;break;case y：/*判定為右括號*/while(stacktopext=stacktop; top;t+; top-；break;/*判定為加減號/*判定為加減號*/casewhile(top!=0&stacktop !=()ext=stacktop ;to

7、p-;t+;top+;stacktop=ch;break;case/*判定為乘除號*/case 71:while(stacktop=* * | stacktop=7) (ext=stacktop ;top;t+;)top+;stacktop=ch;break;case 1 f: break;default:while(ch=,0,&ch=,9,)(/* 判定為數字*/ext=ch;t+;ch=stii;i+;1-;ext=#;t+;)ch=stri;i+;while(top!=0)(ext=stacktop;t+；top;ext=#;pnntfCiit 原來表達式：)；fbr(j=l j=O&ch#中舞表達式；12*15-6) 逆波蘭表達式:12&15&6 I計算結 = 108Press atny key to continue.