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

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

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

3、式，其優(yōu)點(diǎn)在于易于計(jì)算機(jī)處理表達(dá)式。2、產(chǎn)生逆波蘭式的前提中綴算術(shù)表達(dá)式3、逆波蘭式生成的實(shí)驗(yàn)設(shè)計(jì)思想及算法否出錯(cuò)處理否否是是是是否是否輸入一個(gè)中綴式表示的簡單運(yùn)算表達(dá)式#入棧sym=當(dāng)前輸入符號(hào)sym是數(shù)字嗎?對(duì)數(shù)字進(jìn)行處理，形成一個(gè)數(shù)字串棧頂運(yùn)算符優(yōu)先級(jí)低于sym嗎?將向前看符號(hào)入棧棧頂運(yùn)算符與sym優(yōu)先級(jí)相等嗎?將棧頂運(yùn)算符彈出，且輸出棧頂運(yùn)算符優(yōu)先級(jí)高于sym嗎棧頂是(且sym為）嗎棧頂運(yùn)算符出棧程序結(jié)束(1)首先構(gòu)造一個(gè)運(yùn)算符棧，此運(yùn)算符在棧內(nèi)遵循越往棧頂優(yōu)先級(jí)越高的原則。(2)讀入一個(gè)用中綴表示的簡單算術(shù)表達(dá)式，為方便起見,設(shè)該簡單算術(shù)表達(dá)式的右端多加上了優(yōu)先級(jí)最低的特殊符號(hào)“#”

4、。(3)從左至右掃描該算術(shù)表達(dá)式，從第一個(gè)字符開始判斷，如果該字符是數(shù)字，則分析到該數(shù)字串的結(jié)束并將該數(shù)字串直接輸出。(4)如果不是數(shù)字，該字符則是運(yùn)算符，此時(shí)需比較優(yōu)先關(guān)系。做法如下：將該字符與運(yùn)算符棧頂?shù)倪\(yùn)算符的優(yōu)先關(guān)系相比較。如果，該字符優(yōu)先關(guān)系高于此運(yùn)算符棧頂?shù)倪\(yùn)算符，則將該運(yùn)算符入棧。倘若不是的話，則將此運(yùn)算符棧頂?shù)倪\(yùn)算符從棧中彈出，將該字符入棧。(5)重復(fù)上述操作(1)-(2)直至掃描完整個(gè)簡單算術(shù)表達(dá)式，確定所有字符都得到正確處理，我們便可以將中綴式表示的簡單算術(shù)表達(dá)式轉(zhuǎn)化為逆波蘭表示的簡單算術(shù)表達(dá)式。3、逆波蘭式計(jì)算的實(shí)驗(yàn)設(shè)計(jì)思想及算法讀入一個(gè)逆波蘭算術(shù)表達(dá)式sym=當(dāng)前輸入符

5、號(hào)sym是運(yùn)算符嗎?將該字符入棧根據(jù)運(yùn)算符的特點(diǎn)從棧頂部取出若干個(gè)運(yùn)算對(duì)象進(jìn)行該運(yùn)算將運(yùn)算結(jié)果入棧程序結(jié)束否是Sym=#否是(1)構(gòu)造一個(gè)棧，存放運(yùn)算對(duì)象。(2)讀入一個(gè)用逆波蘭式表示的簡單算術(shù)表達(dá)式。(3)自左至右掃描該簡單算術(shù)表達(dá)式并判斷該字符，如果該字符是運(yùn)算對(duì)象，則將該字符入棧。若是運(yùn)算符，如果此運(yùn)算符是二目運(yùn)算符，則將對(duì)棧頂部的兩個(gè)運(yùn)算對(duì)象進(jìn)行該運(yùn)算，將運(yùn)算結(jié)果入棧，并且將執(zhí)行該運(yùn)算的兩個(gè)運(yùn)算對(duì)象從棧頂彈出。如果該字符是一目運(yùn)算符，則對(duì)棧頂部的元素實(shí)施該運(yùn)算，將該棧頂部的元素彈出，將運(yùn)算結(jié)果入棧。(4)重復(fù)上述操作直至掃描完整個(gè)簡單算術(shù)表達(dá)式的逆波蘭式，確定所有字符都得到正確處理，我

6、們便可以求出該簡單算術(shù)表達(dá)式的值。 4.實(shí)驗(yàn)的源程序代碼如下： #include#include#define max 100char exmax; /*存儲(chǔ)后綴表達(dá)式*/void trans() /*將算術(shù)表達(dá)式轉(zhuǎn)化為后綴表達(dá)式*/char strmax; /*存儲(chǔ)原算術(shù)表達(dá)式*/char stackmax; /*作為棧使用*/char ch;int sum,i,j,t,top=0;printf(*n);printf(*輸入一個(gè)求值的表達(dá)式，以#結(jié)束。*n);printf(*n);printf(算數(shù)表達(dá)式：);i=0; /*獲取用戶輸入的表達(dá)式*/doi+;scanf(%c,&stri);w

7、hile(stri!=# & i!=max); sum=i;t=1;i=1;ch=stri;i+;while(ch!=#)switch(ch)case (: /*判定為左括號(hào)*/top+;stacktop=ch; break; case ): /*判定為右括號(hào)*/while(stacktop!=() ext=stacktop;top-;t+;top-;break; case +: /*判定為加減號(hào)*/case -: while(top!=0&stacktop!=()ext=stacktop;top-;t+;top+;stacktop=ch;break;case *: /*判定為乘除號(hào)*/ ca

8、se /:while(stacktop=*|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á)式：);for(j=1;jsum;j+)printf(%c,strj); printf(nt后綴表達(dá)式：,ex);for(j=1;j=0&ch=9) d=10*d+ch-0; /*將數(shù)字字符轉(zhuǎn)化為對(duì)應(yīng)的數(shù)值*/ ch=ext;t+; top+; stacktop=d;ch=ext;t+;printf(nt計(jì)算結(jié)果:%gn,stacktop);main()trans();comp