(編譯原理)逆波蘭式算法的源代碼

1、1 .實驗?zāi)康? .深入理解算符優(yōu)先分析法2 .掌握FirstVt和LastVt集合的求法有算符優(yōu)先關(guān)系表的求法3 .掌握利用算符優(yōu)先分析法完成中綴表達(dá)式到逆波蘭式的轉(zhuǎn)化2 .實驗內(nèi)容及要求將非后綴式用來表示的算術(shù)表達(dá)式轉(zhuǎn)換為用逆波蘭式來表示的算術(shù)表達(dá)式，并計算用逆波蘭式來表示的算術(shù)表達(dá)式的值。程序輸入/輸出示例：輸出的格式如下：(1)逆波蘭式的生成及計算程序，編制人：姓名|學(xué)號，班級(2)輸入一以#結(jié)束的中綴表達(dá)式(包括+*/ ()數(shù)字#):性此位置輸入符號串如 (28+68)*2#(3)逆波蘭式為：28&68+2*(4)逆波蘭式|28&6波2* |計算結(jié)果為192備注：(1

2、)在生成的逆波蘭式中如果兩個數(shù)相連則用&分隔，如28和68,中間用&分隔；(2)|在此位置輸入符號串為用戶自行輸入的符號串。注意：1.表達(dá)式中允許使用運算符(+-*/)、分割符(括號)、數(shù)字，結(jié)束符#;2 .如果遇到錯誤的表達(dá)式，應(yīng)輸出錯誤提示信息(該信息越詳細(xì)越好)；3 .對學(xué)有余力的同學(xué)，測試用的表達(dá)式事先放在文本文件中，一行存放一個表達(dá)式，同時以 分號分割。同時將預(yù)期的輸出結(jié)果寫在另一個文本文件中，以便和輸出進行對照；三.實驗過程1、逆波蘭式定義將運算對象寫在前面，而把運算符號寫在后面。用這種表示法表示的表達(dá)式也稱 做后綴式。逆波蘭式的特點在于運算對象順序不變，運算符號位

3、置反映運算順序。采用 逆波蘭式可以很好的表示簡單算術(shù)表達(dá)式，其優(yōu)點在于易于計算機處理表達(dá)式。2、產(chǎn)生逆波蘭式的前提中綴算術(shù)表達(dá)式3、逆波蘭式生成的實驗設(shè)計思想及算法(1)首先構(gòu)造一個運算符棧,此運算符在棧內(nèi)遵循越往棧頂優(yōu)先級越高的原則。，設(shè)該簡單算術(shù)表達(dá)式的右端多(2)讀入一個用中綴表示的簡單算術(shù)表達(dá)式，為方便起見加上了優(yōu)先級最低的特殊符號“#"。從左至右掃描該算術(shù)表達(dá)式，從第一個字符開始判斷，如果該字符是數(shù)字，則分析 到該數(shù)字串的結(jié)束并將該數(shù)字串直接輸出。(4)如果不是數(shù)字，該字符則是運算符，此時需比較優(yōu)先關(guān)系。如果，該字符優(yōu)先關(guān)系做法如下：將該字符與運算符棧頂?shù)倪\算符的優(yōu)先關(guān)系相

4、比較。高于此運算符棧頂?shù)倪\算符，則將該運算符入棧。倘若不是的話，則將此運算符棧頂?shù)倪\算 符從棧中彈出，將該字符入棧。(5)重復(fù)上述操作(1)-(2)直至掃描完整個簡單算術(shù)表達(dá)式，確定所有字符都得到正確處 理，我們便可以將中綴式表示的簡單算術(shù)表達(dá)式轉(zhuǎn)化為逆波蘭表示的簡單算術(shù)表達(dá)式。3、逆波蘭式計算的實驗設(shè)計思想及算法(1)構(gòu)造一個棧，存放運算對象。(2)讀入一個用逆波蘭式表示的簡單算術(shù)表達(dá)式。(3)自左至右掃描該簡單算術(shù)表達(dá)式并判斷該字符，如果該字符是運算對象，則將該字符入棧。若是運算符，如果此運算符是二目運算符，則將對棧頂部的兩個運算對象進行該運算，將運算結(jié)果入棧，并且將執(zhí)行該運算的兩個運算對

5、象從棧頂彈出。如果該字符是一目運算符，則對棧頂部的元素實施該運算，將該棧頂部的元素彈出，將運算結(jié)果入棧。(4)重復(fù)上述操作直至掃描完整個簡單算術(shù)表達(dá)式的逆波蘭式，確定所有字符都得 到正確處理，我們便可以求出該簡單算術(shù)表達(dá)式的值。4 .實驗的源程序代碼如下：#include<stdio.h>#include<math.h>#define max 100char exmax;/*存儲后綴表達(dá)式*/void trans()/*將算術(shù)表達(dá)式轉(zhuǎn)化為后綴表達(dá)式*/char strmax; /*存儲原算術(shù)表達(dá)式*/char stackmax;/* 作為棧使用*/char ch;int

6、 sum,i,j,t,top=0;printf("*n");printf（"* 輸入一個求值的表達(dá)式，以#結(jié)束。 *n"）;printf("*n");printf（" 算數(shù)表達(dá)式："）;i=0;/*獲取用戶輸入的表達(dá)式*/doi+;scanf("%c",&stri);while(stri!='#' && i!=max);sum=i;t=1;i=1;ch=stri;i+;while(ch!='#')switch(ch)case '(&

7、#39;:/* 判定為左括號*/top+;stacktop=ch;break;case ')':/* 判定為右括號*/while(stacktop!='(')ext=stacktop;top-;t+;top-;break;case '+':/* 判定為加減號*/casewhile(top!=0&&stacktop!='(')ext=stacktop;top-;t+;top+;stacktop=ch;break;case '*':/*判定為乘除號*/case '/':while(sta

8、cktop='*'|stacktop='/')ext=stacktop;top-;t+;top+;stacktop=ch;break;case ' ':break;default:while(ch>='0'&&ch<='9')/* 判定為數(shù)字*/ext=ch;t+;ch=stri;i+;i-;ext='#'t+;ch=stri;i+;while(top!=0)ext=stacktop;t+;top-;ext='#'printf("nt 原來表達(dá)式

9、：");for(j=1;j<sum;j+)printf("%c",strj);printf("nt 后綴表達(dá)式：",ex);for(j=1;j<t;j+)printf("%c",exj);void compvalue()/*計算后綴表達(dá)式的值*/float stackmax,d;/* 作為棧使用*/char ch;int t=1,top=0;/*t 為 ex 下標(biāo)， top 為 stack 下標(biāo) */ch=ext;t+;while(ch!='#')switch(ch)case '+'

10、;:stacktop-1=stacktop-1+stacktop;top-;break;case '-':stacktop-1=stacktop-1-stacktop;top-;break;casestacktop-1=stacktop-1*stacktop;top-;break;case '/':if(stacktop!=0)stacktop-1=stacktop-1/stacktop;elseprintf("nt 除零錯誤!n");exit(0);/*異常退出*/top-;break;default:d=0;while(ch>=&#

11、39;0'&&ch<='9')/*將數(shù)字字符轉(zhuǎn)化為對應(yīng)的數(shù)值*/d=10*d+ch-'0'ch=ext;t+;top+;stacktop=d;ch=ext;t+;printf("nt 計算結(jié)果：gn",stacktop);main()trans();compvalue();5.程序的運行結(jié)果如下:'Documents and Seir= - - - - - - = = - - - - - = - - - - = " - - - - = - - - - - - - - - = - - - - - = =-= = - = "