簡易計算器棧與隊列實驗報告

1、 第三組專題二棧與隊列實驗報告 -簡易計算器一.（1）問題描述通過模擬一個簡單的計算器來進行+、-、*、/、%、（乘方）等運算，從鍵盤上輸入一算術(shù)表達(dá)式（一般為中綴表達(dá)式），計算出表達(dá)式的值。（2）基本要求編寫程序，要求可對一實數(shù)算術(shù)表達(dá)式進行簡單的數(shù)學(xué)運算?？梢宰R別帶加減乘除等運算符及括號的中綴表達(dá)式。a. 按照四則運算規(guī)則，求表達(dá)式的值。一般規(guī)則如下：1）先括號內(nèi)，再括號外。2）先乘方，再乘除，后加減。b. 同級運算從左到右順序執(zhí)行。c如表達(dá)式有誤，應(yīng)給出相應(yīng)的提示信息。（3）數(shù)據(jù)結(jié)構(gòu)與算法分析解決表達(dá)式求值問題的方法之一是：第一步將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，第二步按后綴表達(dá)式求值。解題

2、時可以結(jié)合字符串的相關(guān)知識。（4）測試 4.5+5+6.5*1.06=16.39二.（1）問題分析： 計算機要計算一個式子，不能像我們一樣計算，它需要把表達(dá)式由中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式，即逆波蘭表達(dá)式。 將一般中綴表達(dá)式轉(zhuǎn)換為逆波蘭表達(dá)式有如下轉(zhuǎn)換過程：(1)首先構(gòu)造一個運算符棧，此運算符在棧內(nèi)遵循越往棧頂優(yōu)先級越高的原則。(2)讀入一個用中綴表示的簡單算術(shù)表達(dá)式，為方便起見,設(shè)該簡單算術(shù)表達(dá)式的右端多加上了優(yōu)先級最低的特殊符號“=”。(3)從左至右掃描該算術(shù)表達(dá)式，從第一個字符開始判斷，如果該字符是數(shù)字，則分析到該數(shù)字串的結(jié)束并將該數(shù)字串直接輸出。 (4)如果不是數(shù)字，該字符則是運算符，此

3、時需比較優(yōu)先關(guān)系。做法如下：將該字符與運算符棧頂?shù)倪\算符的優(yōu)先關(guān)系相比較。如果，該字符優(yōu)先關(guān)系高于此運算符棧頂?shù)倪\算符，則將該運算符入棧。倘若不是的話，則將棧頂?shù)倪\算符從棧中彈出，直到棧頂運算符的優(yōu)先級低于當(dāng)前運算符，將該字符入棧。(5)重復(fù)上述操作(3)-(4)直至掃描完整個簡單算術(shù)表達(dá)式，確定所有字符都得到正確處理，我們便可以將中綴式表示的簡單算術(shù)表達(dá)式轉(zhuǎn)化為逆波蘭表示的簡單算術(shù)表達(dá)式。（2）問題實現(xiàn)及代碼。 1.菜單函數(shù)：使用switch函數(shù)根據(jù)輸入的數(shù)字選擇是否進入計算器2.檢測非法輸入函數(shù)：3.雙目運算符定義函數(shù)：完成對+，-，*，/,的定義：4.判斷運算符的優(yōu)先級，決定是壓棧或者彈

4、棧運用到計算中：5.括號匹配檢測函數(shù)：6.運算棧：分為運算符棧和運算數(shù)棧：7.算式計算函數(shù)（最關(guān)鍵函數(shù)）：用于對用戶輸入的算式進行計算，給出最后結(jié)果：三.程序運行演示：括號檢測：非法輸入檢測：四.MFC界面介紹.我們不滿足于DC限制的黑框框界面，所以我們運用了MFC界面。（1） 界面初步簡介：（2） 對程序的改動：（3） 對c+程序的改進： 加、減、乘、除、退格鍵的報錯提示：五.優(yōu)勢與不足：優(yōu)勢：（1）做出了界面，不再是黑框框（2）報錯系統(tǒng)完善，基本不會出錯。（3）結(jié)果顯示正確，不會出現(xiàn)多余的0。不足：（1）雖然做出了界面，但是還不是很優(yōu)美。（2）功能還不是很強大，不能進行三角函數(shù)的運算及其他

5、運算。這些缺點我們都會再以后的學(xué)習(xí)中克服掉！源代碼：#include<iostream>#include<cmath>#include<string>#include<iomanip>using namespace std;void menu();/位于calculate函數(shù)后面的菜單函數(shù)聲明double D_Operate(double x,char op,double y)/雙目運算符的運算定義 double a;/計算結(jié)果 switch(op) case'+': a=x+y;break; case'-': a

6、=x-y;break; case'*': a=x*y;break; case'/': a=x/y;break; case'': a=pow(x,y);break;/冪運算包括乘方和開方 /因為都是利用double進行運算 因此不定義取模運算 return a;char Precede(char op1,char op2) /判斷符號的優(yōu)先級 op1在返回的結(jié)果符的左邊 op2在右邊/用于判定運算符的優(yōu)先級 以決定是把運算符壓棧 還是把棧內(nèi)的運算符彈出來進行計算 if(op1='+'|op1='-')&&am

7、p;(op2='+'|op2='-'|op2=')'|op2='=')| (op1='*'|op1='/')&&(op2='+'|op2='-'|op2='*'|op2='/'|op2=')'|op2='=') |(op1=''&&(op2='+'|op2='-'|op2='*'|op2='/'

8、|op2=')'|op2='=') return '>'/上述情況下 棧頂運算符優(yōu)先級高于待定運算符 需彈棧 if(op1='('&&op2=')')|(op1='='&&op2='=') return '=' else return '<'int illegal_char(string s,int i)/非法輸入字符判定函數(shù) int j=0; while(j<i) if(sj>='0&#

9、39;&&sj<='9') j+; else if(sj='+'|sj='-'|sj='*'|sj='/'|sj='.'|sj='('|sj=')'|sj='') j+; /以上都是標(biāo)準(zhǔn)的數(shù)字字符和運算符 如若存在其他形式的字符 則是非法輸入 else cout<<"程序終止，存在非法的字符輸入！"<<endl; return 0; return 1;/沒有非法字符 返回1 否則返回0i

10、nt match(string s)/棧結(jié)構(gòu)的括號匹配檢測函數(shù) int i=0,top=0; char stack50; while(si!='0') if(si='(') stacktop=si;top+; /push 左括號壓入棧內(nèi) if(si=')') if(stacktop-1='(') int a=i+1; stacktop-1=NULL; top-; /把與右括號匹配的左括號彈掉 else cout<<"括號輸入有誤"<<endl; return 0;/多了右括號 括號失陪

11、返回非法 /pop'(' i+; if (top!=0) cout<<"括號輸入有誤"<<endl; return 0;/多了左括號 括號失陪 返回非法 return 1;/返回合法class NUMstack/運算數(shù)棧 public: double num1000; int top; void start()/初始化棧清空棧頂指針置底 for(int i=0;i<1000;i+) numi=0; top=0; void push(char a)/因為有多位數(shù)的運算因此不能一壓棧就提升棧頂指針 numtop=numtop*10+

12、(a-'0');/把字符轉(zhuǎn)成數(shù)因為每次入棧之前要乘10 所以初始化要清0double pop() top-; double number=numtop; numtop=0; return number; /彈棧函數(shù) 彈掉棧頂元素 棧頂歸0 top指針下降 double getTop()/取棧頂元素但不必彈棧 return numtop-1; void lift()/提升top指針的函數(shù) top+;class OPERstack/運算符棧 public: char oper1000; int top; void start()/初始化函數(shù)棧清空棧底放一"="用

13、于判定算式結(jié)束 oper0='=' for(int i=1;i<1000;i+) operi=NULL; top=1;/棧頂指針置于棧底的上一位 void push(char a) opertop=a; top+;/與數(shù)字棧不同一壓棧就可以提升指針 char pop() top-; char op=opertop; opertop=NULL; return op;/彈出計算符 用于計算 char getTop() return opertop-1;/取棧頂符號 但不彈棧 可用于判定優(yōu)先級 ;void calculate(string equation)/算式計算函數(shù)（關(guān)鍵

14、函數(shù)） NUMstack number;/定義運算數(shù)棧變量number OPERstack oper;/定義運算符棧變量oper number.start(); oper.start();/把兩個棧初始化 int i=0,len=0,k; char p,sig; double yuan1,yuan2; while(equationi!='0') len+; i+; /計算等式長度len if(equationlen-1!='=') cout<<"輸入有誤！沒有輸入終止符號-等號“=”"<<endl; return;/檢

15、測有沒有結(jié)束符等號"=" int le; le=illegal_char(equation,len-1); if(le=0) return;/有非法字符 不進行后續(xù)計算 le=match(equation); if(le=0) return;/括號匹配非法 不進行后續(xù)計算 for(i=0;i<len;i+)/初步確定合法后開始計算算式 if(equationi>='0'&&equationi<='9') number.push(equationi);/壓數(shù)字字符入棧 if(equationi+1<

16、9;0'|equationi+1>'9')&&equationi+1!='.') number.lift();/當(dāng)整個多位運算數(shù)讀取完畢后，運算數(shù)棧棧頂指針才能提升 else if(equationi='.')/小數(shù)壓棧代碼 int x=1; while(equationi+x>='0'&&equationi+x<='9') number.numnumber.top+=(equationi+x-'0')/pow(10,x);/第x位小數(shù)入棧

17、x+; x-; number.lift(); i=i+x; else if(equationi='(') oper.push(equationi);/左括號無條件壓棧 else/數(shù) 乘方左括號判斷完畢后其他運算符的分類討論 if(oper.top=1)/運算符棧為空運算符可以無條件入棧 oper.push(equationi); else/運算符棧不為空則要進行優(yōu)先級判斷 char temp1=oper.getTop();/取出棧頂符號 char temp2;/待入棧符號 temp2=equationi; p=Precede(temp1,temp2); if(p='&l

18、t;') oper.push(temp2);/棧頂符優(yōu)先級較低現(xiàn)在待定的運算符就可以入棧了 if(p='>'|p='=') char rep=p;/當(dāng)棧頂符優(yōu)先級不低于待入棧的符號 則運算符棧不停地彈棧 /進行運算直到低于待入棧符號為止 rep用于記錄比較結(jié)果 要多次進行判斷 while(rep='>'|p='=')&&(oper.top-1>0) sig=oper.pop(); yuan1=number.pop(); yuan2=number.getTop();/靠前的一個運算數(shù)只要取得

19、不要彈出來 if(sig='/'&&yuan1=0)/yuan1是雙目運算符后面的第二運算元 cout<<"錯誤！除數(shù)為0！"<<endl; return; if(sig='+'|sig='-'|sig='*'|sig='/'|sig='') number.num(number.top)-1=D_Operate(yuan2,sig,yuan1); temp1=oper.getTop(); rep=Precede(temp1,temp2);/

20、雙目運算符的計算 if(equationi=')')/如果棧外符是右括號要把與之匹配的左括號彈出棧外 oper.pop(); else oper.push(equationi); if(number.num0=ceil(number.num0) cout<<equation<<number.num0<<endl; else cout<<equation<<fixed<<setprecision(8)<<number.num0<<endl;/輸出結(jié)果控制精度8位小數(shù) /調(diào)試時檢查運算結(jié)束后站內(nèi)情況的代碼段void menu()/