數(shù)據(jù)結構 模擬乘法器

1、課程設計題 目 名 稱 設計一個模擬計算器 課 程 名 稱 數(shù) 據(jù) 結 構 學 生 姓 名 學 號 專 業(yè) 電子信息科學與技術 指 導 教 師 2015年 12 月 30 日一：問題分析和任務定義本程序寫的是模擬計算器。要求設計一個模擬計算器的程序，要求對包含加、減、乘、除、括號運算符及SQR和ABS函數(shù)的任意整型表達式進行求解。這里可以做一個擴展，比如實現(xiàn)求某數(shù)的次方，求模，一些常用的三角函數(shù)等。這個程序實際上就是對一個表達式進行計算。而一個算術表達式中包含各種運算符，每個運算符的等級可能會不同，這就成了本程序需要解決的一個主要的問題之一了。另外計算器中需要有各種數(shù)學函數(shù)，比如：abs sq

2、rt sin cos tan等，如何對這些函數(shù)進行處理，也是本程序能成功的一個關鍵。還有一個問題就是如何處理操作符和操作數(shù)之間的關系也是一個要點。例如：1+2*(3-2/1)，經過怎么樣的變換和處理能得出結果。數(shù)據(jù)的輸入這里應該要用字符，然后通過字符和整形之間的關系進行轉換即可，這樣處理的話，就方便很多了。二：概要設計和數(shù)據(jù)結構選擇輸入的時候將一個算術表達式用一個字符數(shù)組來接收，故需要對這個數(shù)組進行處理，讓操作數(shù)和操作符分開，這里我想把開始的算術表達式轉換成一個后綴表達式，這樣在進行計算的時候就簡單多了。而在轉換的過程中，對運算符的處理極為重要，這里運用堆棧，用堆棧的先進后出的特點，來處理運算

3、符優(yōu)先級的問題，讓其成功轉換成后綴表達式。而在對后綴表達式進行處理的時候，又需要一個堆棧，這個堆棧存放操作數(shù)的。并將運算結果存入該棧中。兩個堆棧的數(shù)據(jù)結構如下：struct char dataMaxlen;int top;optr; /定義運算符棧struct double dataMaxlen;int top;opnd; /定義操作數(shù)棧這里定義了類型，并且一起定義了兩者類型的對象optr,opnd。在將算術表達式轉換成后綴表達式，定義change函數(shù)；在對后綴表達式進行處理時，定義jisuan函數(shù)，另外本程序有個歡迎界面，由meun函數(shù)實現(xiàn)。因此主函數(shù)于各函數(shù)之間的關系為： meun() j

4、isuan()本程序實現(xiàn)的流程：三：詳細設計和編碼首先定義兩個數(shù)組，p400用來存放算術表達式，q400用來存放后綴表達式。由前面的數(shù)據(jù)結構定義兩個對象，。當輸入一個表達式后，定義i作為q的下標，定義dh=1表示是負號，初始化運算符棧optr.top=-1;讓后對進行掃描，當指向的為數(shù)字字符，則將此字符如，后在往中輸入，具體為： while (*p>='0' && *p<='9')qi=*p;i+; p+; if (*p='.') qi='.' i+; p+;while (*p>='0&#

5、39; && *p<='9')qi=*p;i+; p+;qi='#' i+; dh=0;p后移，繼續(xù)掃描，當遇到或時，執(zhí)行 if (dh=1) if (*p='-')optr.top+;optr.dataoptr.top='' p+; break; while (optr.top!=-1 && optr.dataoptr.top!='(') qi=optr.dataoptr.top;optr.top-; i+;optr.top+;optr.dataoptr.top=*p; p+

6、; dh=0; break;當遇到*或/時，先查看操作符棧中是否有優(yōu)秀級比它大的或者一樣大的運算符，有的話就將其他的出棧，最后自己入棧。執(zhí)行：while (optr.dataoptr.top='*' | optr.dataoptr.top='/'| optr.dataoptr.top='s') qi=optr.dataoptr.top;optr.top-; i+; optr.top+;optr.dataoptr.top=*p; p+; dh=0; break;當遇到（時，此時不需要別的其他的操作，只需將其入操作符棧，并將dh=0;當遇到）時，此時

7、需要將（之前的操作符全部出棧，具體操作如下：while (optr.dataoptr.top!='(') qi=optr.dataoptr.top;optr.top-; i+;optr.top-; p+; dh=0; break;當遇到時，根據(jù)運算符的優(yōu)先級，執(zhí)行：while (optr.dataoptr.top='') qi=optr.dataoptr.top;optr.top-;i+;optr.top+;optr.dataoptr.top=*p;p+;dh=0;break;遇到時的操作和差不多，這里就不做介紹了。當遇到數(shù)學函數(shù)的相關符號時，這里以sin 為例

8、，當掃描時，還需要掃描后面的兩個字符，當它們是in時，說明就是sin函數(shù)的符號，此時將此函數(shù)的標志入操作符棧，當其為qrt時，說明是sqrt函數(shù)，此時將sqrt函數(shù)的標志入棧，這里的標志是自己定的。如果都不是上面兩種情況，說明輸入有誤，跳回。具體的程序如下：if(*(p+1)='i' | *(p+1)='I')&&(*(p+2)='n' | *(p+2)='N') optr.top+;optr.dataoptr.top='s'p+=3; dh=0;break; elseif(*(p+1)='

9、q'| *(p+1)='Q')&&(*(p+2)='r' | *(p+2)='R')&&(*(p+3)='t' | *(p+3)='T') optr.top+;optr.dataoptr.top='q'p+=4;dh=0;break;else cout<<endl<<"有錯誤符號"<<endl; return error; 其他的數(shù)學函數(shù)的操作都是類似的，這里就不一一說明了。這里值得注意的是，當將掃描完時

10、，操作符棧并未一定為空，故需要將操作符棧里的數(shù)據(jù)全部出棧：while (optr.top!=-1) qi=optr.dataoptr.top;i+; optr.top-; 以上是將算術表達式轉換成后綴表達式。還要對后綴表達式進行計算，才能得到結果。首先還是對表達式進行掃描，遇到數(shù)字符時，先將其轉換成整形后，再判斷是否有小數(shù)點存在，繼續(xù)掃描直到遇到運算符，讓后通過運算，將次數(shù)轉換成小數(shù)，最后入棧。 具體程序實現(xiàn)：d=0; while (*q>='0' && *q<='9') d=10*d+(*q-'0'); q+; x=

11、0.1;if (*q='.')q+;while (*q>='0' && *q<='9') d=d+x*(*q-'0');x*=0.1; q+; 當遇到操作符時，為雙目運算符時，只需要將操作數(shù)棧的棧頂和次棧頂數(shù)拿出來進行相應的計算，并將其壓入次棧頂。為單目運算符時，只需將操作數(shù)棧頂元素進行運算即可，并將運算符壓入棧即可。這里以 / 和為例。 其余的均和此類似。if (opnd.dataopnd.top!=0)opnd.dataopnd.top-1=opnd.dataopnd.top-1/opnd.data

12、opnd.top;else cout<<endl<<"除數(shù)不能為零!"<<endl;return error; 和opnd.top-;break;opnd.dataopnd.top=sin(opnd.dataopnd.top);當q都掃描完時， 返回操作數(shù)棧頂元素就是計算的結果。四：上機調試在語法上的錯誤，出現(xiàn)過很多，比如少了一個括號，少了個分號，這些問題都是日常寫程序中經常出現(xiàn)的問題，想要避免有點難，不過這些錯誤根據(jù)編譯器的提示和警告，就能很快的該出來。就圖1中出現(xiàn)的問題，這個問題是在#define error 1234567時出現(xiàn)的，

13、這個問題我一直想不同，我定義123456789時可以通過編譯，而變成1234567就不行了，通過向老師請教，發(fā)現(xiàn)這里的error和編譯器里的定義重合了，故不能通過。解決辦法是將這里的error改成derror，這樣在函數(shù)中error相應的也要該。在邏輯上的錯誤，主要就是算法中出現(xiàn)的問題，本程序中的算法有點復雜，在表達式轉換成后綴表達式的過程中就出現(xiàn)了很多的錯誤。這里舉出一個簡單的錯誤，由于本程序在寫的時候，定義了derror=1234567在程序中就不能出現(xiàn)這個計算結果，雖然它超過了本程序的能處理的范圍，可是其結果還是1234567，故返回主函數(shù)時，在if (change(p,q)=1) k=

14、jisuan(q);if(k=derror)cout<<""elsecout<<"計算結果為："<<k<<endl;這里就會出錯。導致圖中的錯誤。解決辦法，這里我對這中情況沒有做特殊的處理。應為在實際的運算過程中，很少有1234567這個結果出現(xiàn)，幾乎是不出現(xiàn)的。如何去定義這個數(shù)，一直是個問題。本程序的，在定義的時用了兩個數(shù)組，故其空間復雜度是n，在算法上，這里我用了一個死循環(huán)，當輸入不為0時，會一直運行。所以只討論運行一次的時間復雜度。在轉換的函數(shù)中，有個while()循環(huán)，這里的復雜度是n，而在這個循環(huán)

15、里，還存在while()循環(huán)，故其時間復雜度是n的平方。在計算函數(shù)中，其復雜度也是n的平方。故可知本程序的時間復雜度是n平方。 五.經驗和體會 這個程序我一直是很簡單的，因為我很久之前就在一直考慮這個問題，但是沒有去實現(xiàn)過，以為很簡單，可是當真正寫起來的時候，發(fā)現(xiàn)有點困難。開始的時候用書山的那種方法，可是發(fā)現(xiàn)那種方法不適合我，不是有多難，就是我的大腦反應不過來。后來想到用后綴表達式，這樣處理起來就方便多了，思路也清晰了很多。在不斷的錯誤中改錯，在調試中發(fā)現(xiàn)程序中的邏輯錯誤并改正錯誤。終于這個程序完成了，心中不免有中自豪感。本程序用編的，在界面下運行的。運行時，程序有個歡迎的界面，并提示輸入表達

16、式，在輸入時要注意的是，本程序能處理的數(shù)據(jù)長度最長為位。另外，輸入時，結束本程序；如輸入的表達式有錯誤的符號時，程序提示輸入錯誤；當輸入正確時，按回車鍵，即可得到計算結果。六：測試結果經過人工計算，可知以上結果是正確的。參考文獻：1 王昆侖，李紅. 數(shù)據(jù)結構與算法. 北京：中國鐵道出版社，2006年5月。2 鄭莉 ，董淵，張瑞豐 c+語言程序設計 北京：清華大學出版社，2004七：附錄（源程序代碼）#include "iostream"#include "math.h"#include "string"#include "s

17、tdlib.h"#include "windows.h"#define derror 1234567#define Maxlen 400using namespace std;struct char dataMaxlen;int top;optr; /定義運算符棧，并定義全局變量struct double dataMaxlen;int top;opnd; /定義操作數(shù)棧，并定義全局變量void main() char p400,q400;double k;void meun(); /聲明菜單函數(shù)int change(char *p, char q); /聲明轉換函

18、數(shù)double jisuan(char *q); /聲明計算函數(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<<""elsecout<<"計算結果為："<<k<<endl;system("pause"); /控制輸出格式system("

19、;cls");meun();system("color 0a");cout<<"tt *"<<endl;cout<<" 歡迎使用本計算器"<<endl;cout<<"tt *"<<endl;cout<<endl;cout<<"按0結束本程序"<<endl;int change(char *p, char q) /將算術表達式p轉換成表達式后綴表達式q int i=0; /i作為q

20、的下標int dh=1; /dh=1表示是負號optr.top=-1; /初始化運算符棧while (*p!='0') /p表達式未掃描完時循環(huán) switch(*p) /判斷各種情況,并做相應的處理case '(': optr.top+;optr.dataoptr.top=*p; dh=1;p+;break;case ')': while (optr.dataoptr.top!='(') qi=optr.dataoptr.top;optr.top-; i+;optr.top-; p+; dh=0; break;case '

21、+':case '-': if (dh=1) / +,-是正負號 if (*p='-')optr.top+;optr.dataoptr.top=''p+; break;while (optr.top!=-1 && optr.dataoptr.top!='(') qi=optr.dataoptr.top;optr.top-; i+;optr.top+;optr.dataoptr.top=*p; p+; dh=0; break;case '*':case '/': while (

22、optr.dataoptr.top='*' | optr.dataoptr.top='/'| optr.dataoptr.top='s') qi=optr.dataoptr.top;optr.top-; i+;optr.top+;optr.dataoptr.top=*p; p+; dh=0; break;case '': while (optr.dataoptr.top='') qi=optr.dataoptr.top;optr.top-;i+;optr.top+;optr.dataoptr.top=*p;p+;d

23、h=0;break;case '%': while (optr.dataoptr.top='%') qi=optr.dataoptr.top;optr.top-;i+;optr.top+;optr.dataoptr.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)='

24、;N') optr.top+;optr.dataoptr.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.dataoptr.top='q'p+=4;dh=0;break;else cout<<endl<<&quo

25、t;有錯誤符號"<<endl; return derror; case 'c':case 'C': if(*(p+1)='o' | *(p+1)='O')&&(*(p+2)='s' | *(p+2)='S') optr.top+;optr.dataoptr.top='c'p+=3; dh=0;break;else cout<<endl<<"有錯誤符號"<<endl; return derro

26、r; case 'T':case 't':if(*(p+1)='a'| *(p+1)='A')&&(*(p+2)='n' | *(p+2)='N') optr.top+;optr.dataoptr.top='t'p+=3;dh=0;break;else cout<<endl<<"有錯誤符號"<<endl; return derror; case 'e':case 'E':if(*(

27、p+1)='x'| *(p+1)='X')&&(*(p+2)='p' | *(p+2)='P') optr.top+;optr.dataoptr.top='e'p+=3;dh=0;break;else cout<<endl<<"有錯誤符號"<<endl; return derror; case 'a':case 'A': if(*(p+1)='b'| *(p+1)='B')&

28、;&(*(p+2)='s' | *(p+2)='S') optr.top+;optr.dataoptr.top='a'p+=3;dh=0;break;else cout<<endl<<"有錯誤符號"<<endl; return derror; default:while (*p>='0' && *p<='9') /判斷是否為數(shù)字qi=*p;i+;p+;if (*p='.') qi='.' i+

29、; p+;while (*p>='0' && *p<='9') qi=*p;i+;p+;qi='#' i+; dh=0;/用#標識一個數(shù)值串結束while (optr.top!=-1) /此時p掃描完畢,棧不空時循環(huán) qi=optr.dataoptr.top;i+; optr.top-;qi='0' /給q表達式添加結束標識return 1;double jisuan(char *q) /計算后綴表達式的值 double d,x;opnd.top=-1; /初始化操作數(shù)棧while (*q!='

30、0') /q字符串未掃描完時循環(huán) switch (*q) /判斷各種情況，并做相應的運算,并入棧case '+':opnd.dataopnd.top-1=opnd.dataopnd.top-1+opnd.dataopnd.top; opnd.top-;break;case '-':opnd.dataopnd.top-1=opnd.dataopnd.top-1-opnd.dataopnd.top; opnd.top-;break;case '*':opnd.dataopnd.top-1=opnd.dataopnd.top-1*opnd.dataopnd.top; opnd.top-;break;case '/': if (opnd.dataopnd.top!=0)opnd.dataopnd.top-1=opnd.dataopnd.top-1/opnd.dataopnd.top;else cout<<endl<<"除數(shù)不能為零!"<<endl;return derror;opnd.top-;break;case '':opnd.dataopnd.top-1=pow(opnd.datao