合肥學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系課程設(shè)計(jì)報(bào)告2009～2010學(xué)年第二學(xué)期課程數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)名稱模擬計(jì)算器程序?qū)W生姓名桂俊飛學(xué)號0804012021專業(yè)班級08計(jì)本〔2〕班指導(dǎo)教師王昆侖張貫虹2010年6月一：問題分析和任務(wù)定義本程序?qū)懙氖悄M計(jì)算器。要求設(shè)計(jì)一個(gè)模擬計(jì)算器的程序，要求對包含加、減、乘、除、括號運(yùn)算符及SQR和ABS函數(shù)的任意整型表達(dá)式進(jìn)行求解。這里可以做一個(gè)擴(kuò)展，比方實(shí)現(xiàn)求某數(shù)的Ｎ次方，求模，一些常用的三角函數(shù)等。這個(gè)程序?qū)嶋H上就是對一個(gè)表達(dá)式進(jìn)行計(jì)算。而一個(gè)算術(shù)表達(dá)式中包含各種運(yùn)算符，每個(gè)運(yùn)算符的等級可能會不同，這就成了本程序需要解決的一個(gè)主要的問題之一了。另外計(jì)算器中需要有各種數(shù)學(xué)函數(shù)，比方：abssqrtsincostan等，如何對這些函數(shù)進(jìn)行處理，也是本程序能成功的一個(gè)關(guān)鍵。還有一個(gè)問題就是如何處理操作符和操作數(shù)之間的關(guān)系也是一個(gè)要點(diǎn)。例如：1+2*(3-2/1)，經(jīng)過怎么樣的變換和處理能得出結(jié)果５。數(shù)據(jù)的輸入這里應(yīng)該要用字符，然后通過字符和整形之間的關(guān)系進(jìn)行轉(zhuǎn)換即可，這樣處理的話，就方便很多了。二：概要設(shè)計(jì)和數(shù)據(jù)結(jié)構(gòu)選擇輸入的時(shí)候?qū)⒁粋€(gè)算術(shù)表達(dá)式用一個(gè)字符數(shù)組來接收，故需要對這個(gè)數(shù)組進(jìn)行處理，讓操作數(shù)和操作符分開，這里我想把開始的算術(shù)表達(dá)式轉(zhuǎn)換成一個(gè)后綴表達(dá)式，這樣在進(jìn)行計(jì)算的時(shí)候就簡單多了。而在轉(zhuǎn)換的過程中，對運(yùn)算符的處理極為重要，這里運(yùn)用堆棧，用堆棧的先進(jìn)后出的特點(diǎn)，來處理運(yùn)算符優(yōu)先級的問題，讓其成功轉(zhuǎn)換成后綴表達(dá)式。而在對后綴表達(dá)式進(jìn)行處理的時(shí)候，又需要一個(gè)堆棧，這個(gè)堆棧存放操作數(shù)的。并將運(yùn)算結(jié)果存入該棧中。兩個(gè)堆棧的數(shù)據(jù)結(jié)構(gòu)如下：struct{chardata[Maxlen];inttop;}optr;//定義運(yùn)算符棧struct{doubledata[Maxlen];inttop;}opnd;//定義操作數(shù)棧這里定義了類型，并且一起定義了兩者類型的對象optr,opnd。在將算術(shù)表達(dá)式轉(zhuǎn)換成后綴表達(dá)式，定義change函數(shù)；在對后綴表達(dá)式進(jìn)行處理時(shí)，定義jisuan函數(shù)，另外本程序有個(gè)歡送界面，由meun函數(shù)實(shí)現(xiàn)。因此主函數(shù)于各函數(shù)之間的關(guān)系為：meun()main()change()jisuan()本程序?qū)崿F(xiàn)的流程：這里的兩個(gè)主要的函數(shù)具體算法在詳細(xì)設(shè)計(jì)中有說明。三：詳細(xì)設(shè)計(jì)和編碼首先定義兩個(gè)數(shù)組，p[400]用來存放算術(shù)表達(dá)式，q[400]用來存放后綴表達(dá)式。由前面的數(shù)據(jù)結(jié)構(gòu)定義兩個(gè)對象ｏｐｔｒ，ｏｐｎｄ。當(dāng)輸入一個(gè)表達(dá)式后，定義i作為q的下標(biāo)，定義dh=1表示是負(fù)號，初始化運(yùn)算符棧optr.top=-1;讓后對ｐ進(jìn)行掃描，當(dāng)ｐ指向的為數(shù)字字符，那么將此字符如ｑ，后在往ｑ中輸入＃，具體為：while(*p>='0'&&*p<='9') {q[i]=*p;i++;p++;}if(*p=='.') {q[i]='.';i++;p++;while(*p>='0'&&*p<='9'){q[i]=*p;i++;p++;}}q[i]='#';i++;dh=0;p后移，繼續(xù)掃描，當(dāng)遇到＋或－時(shí)，執(zhí)行if(dh==1){if(*p=='-')optr.top++;optr.data[optr.top]='@';p++;break;}while(optr.top!=-1&&optr.data[optr.top]!='(') {q[i]=optr.data[optr.top];optr.top--;i++; }optr.top++;optr.data[optr.top]=*p;p++;dh=0;break;當(dāng)遇到*或/時(shí)，先查看操作符棧中是否有優(yōu)秀級比它大的或者一樣大的運(yùn)算符，有的話就將其他的出棧，最后自己入棧。執(zhí)行：while(optr.data[optr.top]=='*'||optr.data[optr.top]=='/'||optr.data[optr.top]=='s') {q[i]=optr.data[optr.top];optr.top--;i++;} optr.top++;optr.data[optr.top]=*p;p++;dh=0;break;當(dāng)遇到〔時(shí)，此時(shí)不需要別的其他的操作，只需將其入操作符棧，并將dh=0;當(dāng)遇到〕時(shí)，此時(shí)需要將〔之前的操作符全部出棧，具體操作如下：while(optr.data[optr.top]!='(') {q[i]=optr.data[optr.top];optr.top--;i++;} optr.top--;p++;dh=0;break;當(dāng)遇到^時(shí)，根據(jù)運(yùn)算符的優(yōu)先級，執(zhí)行：while(optr.data[optr.top]=='^') {q[i]=optr.data[optr.top];optr.top--;i++;} optr.top++;optr.data[optr.top]=*p;p++;dh=0;break;遇到％時(shí)的操作和^差不多，這里就不做介紹了。當(dāng)遇到數(shù)學(xué)函數(shù)的相關(guān)符號時(shí)，這里以sin為例，當(dāng)掃描ｓ時(shí)，還需要掃描后面的兩個(gè)字符，當(dāng)它們是in時(shí)，說明就是sin函數(shù)的符號，此時(shí)將此函數(shù)的標(biāo)志入操作符棧，當(dāng)其為qrt時(shí)，說明是sqrt函數(shù)，此時(shí)將sqrt函數(shù)的標(biāo)志入棧，這里的標(biāo)志是自己定的。如果都不是上面兩種情況，說明輸入有誤，跳回。具體的程序如下：if((*(p+1)=='i'||*(p+1)=='I')&&(*(p+2)=='n'||*(p+2)=='N')){optr.top++;optr.data[optr.top]='s';p+=3;dh=0;break;} elseif((*(p+1)=='q'||*(p+1)=='Q')&&(*(p+2)=='r'||*(p+2)=='R')&&(*(p+3)=='t'||*(p+3)=='T')) {optr.top++;optr.data[optr.top]='q';p+=4;dh=0;break; }else{cout<<endl<<"有錯(cuò)誤符號"<<endl;returnerror;}其他的數(shù)學(xué)函數(shù)的操作都是類似的，這里就不一一說明了。這里值得注意的是，當(dāng)將ｐ掃描完時(shí)，操作符棧并未一定為空，故需要將操作符棧里的數(shù)據(jù)全部出棧：while(optr.top!=-1) {q[i]=optr.data[optr.top];i++;optr.top--;}以上是將算術(shù)表達(dá)式轉(zhuǎn)換成后綴表達(dá)式。還要對后綴表達(dá)式進(jìn)行計(jì)算，才能得到結(jié)果。首先還是對表達(dá)式進(jìn)行掃描，遇到數(shù)字符時(shí)，先將其轉(zhuǎn)換成整形后，再判斷是否有小數(shù)點(diǎn)存在，繼續(xù)掃描直到遇到運(yùn)算符，讓后通過運(yùn)算，將次數(shù)轉(zhuǎn)換成小數(shù)，最后入棧。具體程序?qū)崿F(xiàn)：d=0;while(*q>='0'&&*q<='9') {d=10*d+(*q-'0');q++;}x=0.1;if(*q=='.'){q++;while(*q>='0'&&*q<='9'){d=d+x*(*q-'0');x*=0.1;q++;}}當(dāng)遇到操作符時(shí)，為雙目運(yùn)算符時(shí)，只需要將操作數(shù)棧的棧頂和次棧頂數(shù)拿出來進(jìn)行相應(yīng)的計(jì)算，并將其壓入次棧頂。為單目運(yùn)算符時(shí)，只需將操作數(shù)棧頂元素進(jìn)行運(yùn)算即可，并將運(yùn)算符壓入棧即可。這里以/和ｓｉｎ為例。其余的均和此類似。if(opnd.data[opnd.top]!=0)opnd.data[opnd.top-1]=opnd.data[opnd.top-1]/opnd.data[opnd.top];else{cout<<endl<<"除數(shù)不能為零!"<<endl;returnerror;}和opnd.top--;break;opnd.data[opnd.top]=sin(opnd.data[opnd.top]);當(dāng)q都掃描完時(shí)，返回操作數(shù)棧頂元素就是計(jì)算的結(jié)果。四：上機(jī)調(diào)試在語法上的錯(cuò)誤，出現(xiàn)過很多，比方少了一個(gè)括號，少了個(gè)分號，這些問題都是日常寫程序中經(jīng)常出現(xiàn)的問題，想要防止有點(diǎn)難，不過這些錯(cuò)誤根據(jù)編譯器的提示和警告，就能很快的該出來。就圖1中出現(xiàn)的問題，這個(gè)問題是在#defineerror1234567時(shí)出現(xiàn)的，這個(gè)問題我一直想不同，我定義123456789時(shí)可以通過編譯，而變成1234567就不行了，通過向老師請教，發(fā)現(xiàn)這里的error和編譯器里的定義重合了，故不能通過。解決方法是將這里的error改成derror，這樣在函數(shù)中error相應(yīng)的也要該。在邏輯上的錯(cuò)誤，主要就是算法中出現(xiàn)的問題，本程序中的算法有點(diǎn)復(fù)雜，在表達(dá)式轉(zhuǎn)換成后綴表達(dá)式的過程中就出現(xiàn)了很多的錯(cuò)誤。這里舉出一個(gè)簡單的錯(cuò)誤，由于本程序在寫的時(shí)候，定義了derror=1234567在程序中就不能出現(xiàn)這個(gè)計(jì)算結(jié)果，雖然它超過了本程序的能處理的范圍，可是其結(jié)果還是1234567，故返回主函數(shù)時(shí)，在if(change(p,q)==1){k=jisuan(q); if(k==derror) cout<<"";else cout<<"計(jì)算結(jié)果為："<<k<<endl; }這里就會出錯(cuò)。導(dǎo)致圖中的錯(cuò)誤。解決方法，這里我對這中情況沒有做特殊的處理。應(yīng)為在實(shí)際的運(yùn)算過程中，很少有1234567這個(gè)結(jié)果出現(xiàn)，幾乎是不出現(xiàn)的。如何去定義這個(gè)數(shù)，一直是個(gè)問題。本程序的，在定義的時(shí)用了兩個(gè)數(shù)組，故其空間復(fù)雜度是n，在算法上，這里我用了一個(gè)死循環(huán)，當(dāng)輸入不為0時(shí)，會一直運(yùn)行。所以只討論運(yùn)行一次的時(shí)間復(fù)雜度。在轉(zhuǎn)換的函數(shù)中，有個(gè)while()循環(huán)，這里的復(fù)雜度是n，而在這個(gè)循環(huán)里，還存在while()循環(huán)，故其時(shí)間復(fù)雜度是n的平方。在計(jì)算函數(shù)中，其復(fù)雜度也是n的平方。故可知本程序的時(shí)間復(fù)雜度是n平方。經(jīng)驗(yàn)和體會：這個(gè)程序我一直是很簡單的，因?yàn)槲液芫弥熬驮谝恢笨紤]這個(gè)問題，但是沒有去實(shí)現(xiàn)過，以為很簡單，可是當(dāng)真正寫起來的時(shí)候，發(fā)現(xiàn)有點(diǎn)困難。開始的時(shí)候用書山的那種方法，可是發(fā)現(xiàn)那種方法不適合我，不是有多難，就是我的大腦反響不過來。后來想到用后綴表達(dá)式，這樣處理起來就方便多了，思路也清晰了很多。在不斷的錯(cuò)誤中改錯(cuò)，在調(diào)試中發(fā)現(xiàn)程序中的邏輯錯(cuò)誤并改正錯(cuò)誤。終于這個(gè)程序完成了，心中不免有中自豪感。五：用戶使用說明本程序用ｖｃ＋＋６．０編的，在ＤＯＳ界面下運(yùn)行的。運(yùn)行時(shí)，程序有個(gè)歡送的界面，并提示輸入表達(dá)式，在輸入時(shí)要注意的是，本程序能處理的數(shù)據(jù)長度最長為６位。另外，輸入０時(shí)，結(jié)束本程序；如輸入的表達(dá)式有錯(cuò)誤的符號時(shí)，程序提示輸入錯(cuò)誤；當(dāng)輸入正確時(shí)，按回車鍵，即可得到計(jì)算結(jié)果。六：測試結(jié)果經(jīng)過人工計(jì)算，可知以上結(jié)果是正確的。參考文獻(xiàn)：[1]王昆侖，李紅.數(shù)據(jù)結(jié)構(gòu)與算法.北京：中國鐵道出版社，2006年5月。[2]鄭莉，董淵，張瑞豐c++語言程序設(shè)計(jì)北京：清華大學(xué)出版社，2004七：附錄〔源程序代碼〕#include"iostream"#include"math.h"#include"string"#include"stdlib.h"#include"windows.h"#definederror1234567#defineMaxlen400usingnamespacestd;struct{chardata[Maxlen];inttop;}optr; //定義運(yùn)算符棧，并定義全局變量struct{doubledata[Maxlen];inttop;}opnd; //定義操作數(shù)棧，并定義全局變量voidmain(){charp[400],q[400];doublek;voidmeun(); //聲明菜單函數(shù)intchange(char*p,charq[]); //聲明轉(zhuǎn)換函數(shù)doublejisuan(char*q); //聲明計(jì)算函數(shù)meun();for(;;) //循環(huán)執(zhí)行{cout<<"請輸入:";cin>>p;if(strcmp(p,"0")==0)return;if(change(p,q)==1){k=jisuan(q); if(k==derror) cout<<"";else cout<<"計(jì)算結(jié)果為："<<k<<endl; }system("pause");//控制輸出格式system("cls");meun();}}voidmeun(){system("color0a");cout<<"\t\t**************************************"<<endl;cout<<"歡送使用本計(jì)算器"<<endl;cout<<"\t\t**************************************"<<endl;cout<<endl;cout<<"按0結(jié)束本程序"<<endl;}intchange(char*p,charq[])//將算術(shù)表達(dá)式p轉(zhuǎn)換成表達(dá)式后綴表達(dá)式q{inti=0;//i作為q的下標(biāo)intdh=1;//dh=1表示是負(fù)號optr.top=-1;//初始化運(yùn)算符棧while(*p!='\0')//p表達(dá)式未掃描完時(shí)循環(huán){switch(*p)//判斷各種情況,并做相應(yīng)的處理 {case'(':optr.top++;optr.data[optr.top]=*p;dh=1;p++;break;case')':while(optr.data[optr.top]!='(') {q[i]=optr.data[optr.top];optr.top--;i++; }optr.top--;p++;dh=0;break;case'+':case'-':if(dh==1)//+,-是正負(fù)號 {if(*p=='-')optr.top++;optr.data[optr.top]='@';p++;break; }while(optr.top!=-1&&optr.data[optr.top]!='(') {q[i]=optr.data[optr.top];optr.top--;i++; }optr.top++;optr.data[optr.top]=*p;p++;dh=0;break;case'*':case'/':while(optr.data[optr.top]=='*'||optr.data[optr.top]=='/'||optr.data[optr.top]=='s') {q[i]=optr.data[optr.top];optr.top--;i++; }optr.top++;optr.data[optr.top]=*p;p++;dh=0;break;case'^':while(optr.data[optr.top]=='^') {q[i]=optr.data[optr.top];optr.top--;i++; }optr.top++;optr.data[optr.top]=*p;p++;dh=0;break;case'%':while(optr.data[optr.top]=='%') {q[i]=optr.data[optr.top];optr.top--;i++; }optr.top++;optr.data[optr.top]=*p;p++;dh=0;break;case'':p++;break;//消除空格case's':case'S':if((*(p+1)=='i'||*(p+1)=='I')&&(*(p+2)=='n'||*(p+2)=='N')) {optr.top++;optr.data[optr.top]='s';p+=3;dh=0;break; }elseif((*(p+1)=='q'||*(p+1)=='Q')&&(*(p+2)=='r'||*(p+2)=='R')&&(*(p+3)=='t'||*(p+3)=='T')) {optr.top++;optr.data[optr.top]='q';p+=4;dh=0;break; }else{cout<<endl<<"有錯(cuò)誤符號"<<endl;returnderror;}case'c':case'C':if((*(p+1)=='o'||*(p+1)=='O')&&(*(p+2)=='s'||*(p+2)=='S')) {optr.top++;optr.data[optr.top]='c';p+=3;dh=0;break; }else{cout<<endl<<"有錯(cuò)誤符號"<<endl;returnderror;}case'T':case't':if((*(p+1)=='a'||*(p+1)=='A')&&(*(p+2)=='n'||*(p+2)=='N')) {optr.top++;optr.data[optr.top]='t';p+=3;dh=0;break; }else{cout<<endl<<"有錯(cuò)誤符號"<<endl;;returnderror;}case'e':case'E':if((*(p+1)=='x'||*(p+1)=='X')&&(*(p+2)=='p'||*(p+2)=='P')) {optr.top++;optr.data[optr.top]='e';p+=3;dh=0;break; }else{cout<<endl<<"有錯(cuò)誤符號"<<endl;returnderror;}case'a':case'A':if((*(p+1)=='b'||*(p+1)=='B')&&(*(p+2)=='s'||*(p+2)=='S')) {optr.top++;optr.data[optr.top]='a';p+=3;dh=0;break; }else{cout<<endl<<"有錯(cuò)誤符號"<<endl;returnderror;}default:while(*p>='0'&&*p<='9')//判斷是否為數(shù)字 {q[i]=*p;i++;p++; }if(*p=='.') {q[i]='.';i++;p++;while(*p>='0'&&*p<='9') {q[i]=*p;i++;p++;} }q[i]='#';i++;dh=0;//用#標(biāo)識一個(gè)數(shù)值串結(jié)束 } }while(optr.top!=-1)//此時(shí)p掃描完畢,棧不空時(shí)循環(huán) {q[i]=optr.data[optr.top];i++;optr.top--; }q[i]='\0';//給q表達(dá)式添加結(jié)束標(biāo)識return1;}doublejisuan(char*q)//計(jì)算后綴表達(dá)式的值{doubled,x;opnd.top=-1;//初始化操作數(shù)棧while(*q!='\0')//q字符串未掃描完時(shí)循環(huán){switch(*q)//判斷各種情況，并做相應(yīng)的運(yùn)算,并入棧{case'+':opnd.data[opnd.top-1]=opnd.data[opnd.top-1]+opnd.data[opnd.top];opnd.top--;break;case'-':opnd.data[opnd.top-1]=opnd.data[opnd.top-1]-opnd.data[opnd.top];opnd.top--;break;case'*':opnd.data[opnd.top-1]=opnd.data[opnd.top-1]*opnd.data[opnd.top];opnd.top--;break;case'/':if(opnd.data[opnd.top]!=0)opnd.data[opnd.top-1]=opnd.data[opnd.top-1]/opnd.data[opnd.top];else {cout<<endl<<"除數(shù)不能為零!"<<endl;returnderror; }opnd.top--;break;case'^':opnd.data[opnd.top-1]=pow(opnd.data[opnd.top-1],opnd.data[opnd.top]);opnd.top--;break;case