模擬計算器程序課程設計

1、模擬計算器學生姓名：* 指導老師：*摘 要 本課程設計的課題是設計一個模擬計算器的程序，能夠進行表達式的計算，并且表達式中可以包含Abs()和Sqrt()運算。在課程設計中，系統(tǒng)開發(fā)平臺為Windows ，程序設計設計語言采用C+，程序運行平臺為Windows 或 *nix。本程序的關(guān)鍵就是表達式的分離和處理，在程序設計中，采用了將輸入的中綴表達式轉(zhuǎn)化為后綴表達式的方法，具有可靠的運行效率。本程序做到了對輸入的表達式（表達式可以包含浮點數(shù)并且Abs()和Sqrt()中可以嵌套子表達式）進行判定表達式是否合法并且求出表達式的值的功能。經(jīng)過一系列的調(diào)試運行，程序?qū)崿F(xiàn)了設計目標，可以正確的處理用戶輸

2、入的表達式，對海量級數(shù)據(jù)都能夠通過計算機運算快速解決。關(guān)鍵詞 C+程序設計；數(shù)據(jù)結(jié)構(gòu)；表達式運算；棧；中綴表達式；后綴表達式；字符串處理；表達式合法判定；目 錄1 引 言21.1課程設計目的31.2課程設計內(nèi)容32 設計思路與方案33 詳細實現(xiàn)43.1 表達式的合法判定43.2 中綴表達式轉(zhuǎn)化為后綴表達式53.3 處理后綴表達式73.4 表達式嵌套處理84 運行環(huán)境與結(jié)果84.1 運行環(huán)境84.2 運行結(jié)果85 結(jié)束語11參考文獻12附錄1：模擬計算器源程序清單141 引 言本課程設計主要解決的是傳統(tǒng)計算器中，不能對表達式進行運算的問題，通過制作該計算器模擬程序，可以做到快速的求解表達式的值，

3、并且能夠判定用戶輸入的表達式是否合法。該模擬計算器的核心部分就在用戶輸入的中綴表達式的轉(zhuǎn)化，程序中用到了“?！钡暮筮M先出的基本性質(zhì)。利用兩個“?！?，一個“數(shù)據(jù)?！保粋€“運算符?！眮戆阎芯Y表達式轉(zhuǎn)換成后綴表達式。最后利用后綴表達式來求解表達式的值。該算法的復雜度為O(n)，能夠高效、快速地求解表達式的值，提高用戶的效率。1.1課程設計目的 數(shù)據(jù)結(jié)構(gòu)主要是研究計算機存儲，組織數(shù)據(jù)，非數(shù)值計算程序設計問題中所出現(xiàn)的計算機操作對象以及它們之間的關(guān)系和操作的學科。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學、計算機軟件和計算機硬件之間的一門計算機專業(yè)的核心課程，它是計算機程序設計、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人工智能

4、等的重要基礎，廣泛的應用于信息學、系統(tǒng)工程等各種領(lǐng)域。學習數(shù)據(jù)結(jié)構(gòu)是為了將實際問題中涉及的對象在計算機中表示出來并對它們進行處理。通過課程設計可以提高學生的思維能力，促進學生的綜合應用能力和專業(yè)素質(zhì)的提高。模擬計算器程序主要利用了“?！边@種數(shù)據(jù)結(jié)構(gòu)來把中綴表達式轉(zhuǎn)化為后綴表達式，并且運用了遞歸的思想來解決Abs()和Sqrt()中嵌套表達式的問題，其中還有一些統(tǒng)計的思想來判定表達式是否合法的算法。1.2課程設計內(nèi)容本次課程設計為計算器模擬程序，主要解決表達式計算的問題，實現(xiàn)分別按表達式處理的過程分解為幾個子過程，詳細的求解過程如下：1 用戶輸入表達式。2 判定表達式是否合法。3 把中綴表達式轉(zhuǎn)

5、化為后綴表達式。4 求出后綴表達式的結(jié)果。5 輸出表達式的結(jié)果。通過設計該程序，從而做到方便的求出一個表達式的值，而不需要一步一步進行運算。2 設計思路與方案本課程設計需要考慮許多的問題，首先是表達式的合法判斷，然后是字符串表達式提取分離的問題，核心部分就是中綴表達式轉(zhuǎn)化為后綴表達式。對于第一個問題，我是分步來判斷，首先表達式中是否含有其它非法字符，然后判斷括號是否合法，接著判斷運算法兩邊是否合法，比如除法時，除數(shù)不能為零。對于第二個問題，我是直接轉(zhuǎn)換的，從左到右遍歷中綴表達式，把數(shù)據(jù)全部取出來。對于核心問題，利用了“?！边@種“后進先出”的數(shù)據(jù)結(jié)構(gòu)，利用兩個“?！?，一個“數(shù)據(jù)?！?，一個“運算符

6、?！眮戆阎芯Y表達式轉(zhuǎn)換成后綴表達式。最后利用后綴表達式來求解表達式的值。 上面是數(shù)據(jù)處理的算法部分。本程序用戶界面總共分為3個模塊，分別是操作提示，數(shù)據(jù)輸入，數(shù)據(jù)輸出。如圖2.1所示。圖2.1 用戶界面除了實現(xiàn)基本的功能外，我還增加了其它一些功能，比如支持輸入數(shù)據(jù)為浮點數(shù)，更重要的是本程序還支持表達式的嵌套運算，例如：A(1+2*S(2)我的實現(xiàn)方法是利用函數(shù)的遞歸調(diào)用來解決此問題，即把1+2*S(2)看成一個子表達式，這個子表達式中2也看成子表達式。這樣使得程序的適用范圍更加的廣泛，適應性更強，能支持更復雜的表達式的運算。這也是本程序的優(yōu)點之一。3 詳細實現(xiàn)3.1 表達式的合法判定表達式的合

7、法判定過程如圖3.1所示是否存在其它字符括號是否合法運算符是否合法 圖3.1 表達式的合法判定過程首先是其它字符的判定，從左到右遍歷中綴表達式，看是否存在其它非法的。然后是判定括號是否的匹配是否和合法，首先把“(”對應為1，相應的“)”對應為-1。從左到右遍歷表達式，如果遇到括號就加上其對應的值，用sum來保存其累加值。如果在中途出現(xiàn)sum小于零的情況，即出現(xiàn)“. )” 那么的情況，即非法。在遍歷的最后，還要判斷sum的值是否為零，如果為零就是合法，否則就是非法。代碼如下： for(i=0;i<s.length();i+) /檢驗括號是否合法，以及是否存在非法字符 if(!IsNum(s

8、i) && !IsSign(si) && si!='(' && si!=')' && si!='A' && si!='S' && si!='.')return false; if(si='(')sum+=1; else if(si=')')sum-=1; if(sum<0)return false; /括號匹配不合法運算符判斷是否合法，也是遍歷一遍表達式，遇到“/”，看其后面的除數(shù)是

9、否為零。這里要考慮表達式中出現(xiàn)負數(shù)的情況，因此特殊考慮“-”號，判斷它的前面是“(”還是沒有字符了，那么就是負數(shù)。3.2 中綴表達式轉(zhuǎn)化為后綴表達式中綴表達式轉(zhuǎn)化為后綴表達式，利用兩個“?！?，一個“數(shù)據(jù)?！?，一個“運算符?！眮戆阎芯Y表達式轉(zhuǎn)換成后綴表達式。最后利用后綴表達式來求解表達式的值。設一個stack存后綴數(shù)據(jù)，一個rout棧存運算符。算法流程如下：（1）從右向左依次取得數(shù)據(jù)ch。（2）如果ch是操作數(shù)，直接加進stack中。（3）如果ch是運算符（含左右括號），則： a：如果ch = '('，放入堆棧rout中。 b：如果ch = ')'，依次輸出堆棧r

10、out中的運算符，直到遇到'('為止。 c：如果ch不是')'或者'('，那么就和堆棧rout頂點位置的運算符top做優(yōu)先級比較。 1：如果ch優(yōu)先級比rtop高，那么將ch放入堆棧rout。 2：如果ch優(yōu)先級低于或者等于rtop，那么輸出top到stack中（直到！top或者滿足 1），然后將ch放入堆棧rout。 可以看出算法復雜度是O(n）的，因此效率是比較高的，能夠在1s內(nèi)處理百萬級別長度的表達式。算法的主要思想是利用“?！钡暮筮M先出的特性，以及運算符的優(yōu)先級，這里我們定義運算符的優(yōu)先級；代碼如下：int GetKey(char c)

11、/定義運算符的關(guān)鍵字 int key; switch(c) case '+':key=1;break; case '-':key=1;break; case '*':key=2;break; case '/':key=2;break; case '(':key=4;break; case ')':key=5;break; return key;中綴轉(zhuǎn)化為后綴處理的核心代碼如下： /* 雙棧,sta1存放后綴表達式,sta2存放運算符符號*/ stack<pair<double,int&g

12、t; > sta1,sta2; for(i=0;i<k;i+) if(!numi.second)sta1.push(numi); /為數(shù)據(jù),直接放入sta1 else if(numi.second=4)sta2.push(numi); /為'(',直接放入sta2/* 為')',從sta2中取出運算符,push到sta1中,直到遇到')' */ else if(numi.second=5) while(sta2.top().second!=4) sta1.push(sta2.top(); sta2.pop(); sta2.pop();

13、 /取出'('括號 /*為'+','-','*'或者'/'運算符,取出sta2中的運算符, push到sta1中,直到比sta2棧頂中的優(yōu)先級大*/ else while(!sta2.empty() && sta2.top().second>=numi.second && sta2.top().second!=4) sta1.push(sta2.top(); sta2.pop(); sta2.push(numi); /放入當前運算符 最后，后綴表達式就存放在sta1棧中，把st

14、a1棧中的結(jié)果存放到SufExp中就得到了后綴表達式。3.3 處理后綴表達式這里也是運用“?！眮硖幚?，運用棧模板在求值過程順序掃描后綴表達式，每次遇到操作數(shù)便將它壓入堆棧；遇到運算符，則從棧中彈出兩個操作數(shù)進行計算，然后再把結(jié)果壓入堆棧，等到掃描結(jié)束時，則表達式的結(jié)果就求出來了。算法流程如圖3.3所示： 后綴表達式 掃描并判定數(shù)據(jù)類型 從棧中取出數(shù)字進行運算 數(shù)字壓入棧中 棧 結(jié)果壓入棧中 輸出最終結(jié)果圖 3.3 處理后綴表達式流程核心代碼如下：double Expression:GetAns() int i; double temp,num1,num2; /num1和num2為運算符兩遍的操

15、作數(shù) stack<double> sta; /數(shù)據(jù)棧 for(i=0;i<Size;i+) if(!SufExpi.second) /為數(shù)據(jù) sta.push(SufExpi.first); else /為運算符 num1=sta.top(); /取出第一個操作數(shù) sta.pop(); num2=sta.top(); /取出第二個操作數(shù) sta.pop(); temp=Cal(char)SufExpi.first,num2,num1); sta.push(temp); /放入操作數(shù)結(jié)果 Ans=sta.top(); return Ans; /返回最終結(jié)果3.4 表達式嵌套處理

16、如果遇到A()和S()中含有表達式，而不是單純的數(shù)字，例如A(1.1+3.4*S(2.5),那么就需要對其字表達式“1.1+3.4*S(2.5)”進行遞歸處理,這個子表達式中還含有子表達式“2.5”,然后再遞歸處理,依次類推下去。其核心代碼如下： if(si='A' | si='S') /遇到Abs()或者Sqrt()遞歸處理子表達式 Expression temp; /創(chuàng)建子表達式 temp.Init(); for(j=0;i+j+2<Posi+1;j+) /復制表達式 stj=si+j+2; stj=0; temp.s=st; /復制表達式 temp.

17、SloveExp(); /得到子表達式的值 numk.first=(si='A'?fabs(temp.Ans):sqrt(temp.Ans); numk.second=0; /標記為數(shù)據(jù) if(si-1='-' && (i-1=0 | si-2='(')numk.first=-numk.first; k+,i=Posi+1;4 運行環(huán)境與結(jié)果4.1 運行環(huán)境運行環(huán)境：Windows XP / Windows 7 / Linux Ubuntu13.044.2 運行結(jié)果表達式中含非法字符判斷如圖4.1所示：圖4.1 非法字符判斷表達式

18、中非法括號匹配判斷如圖4.2所示：圖4.2 非法括號匹配判斷表達式中運算符判斷如圖4.3所示：圖4.3 運算符判斷表達式中有浮點數(shù)如圖4.4所示：圖4.4 表達式中有浮點數(shù)A()運算符中嵌套表達式如圖4.5所示：圖4.5 A()運算符中嵌套表達式S()運算符中嵌套表達式如圖4.6所示：圖4.6 S()運算符中嵌套表達式復雜的表達式運算如圖4.7所示：圖4.7 復雜的表達式運算5 結(jié)束語通過兩周的課程設計，我學會了如何寫一個精簡、快速、健壯的程序。一個好的程序應該是一個所占空間小、運行時間短、其他性能也好的程序。而要做出一個好的程序則應該通過對算法與其數(shù)據(jù)結(jié)構(gòu)的時間復雜度和空間復雜度進行實現(xiàn)與改

19、進。然而，實際上很難做到十全十美，原因是各要求有時相互抵觸，要節(jié)約算法的執(zhí)行時間往往要以犧牲更多的存儲空間為代價：而為了節(jié)省存儲空間又可能要以更多的時間為代價。因此，只能根據(jù)具體情況有所側(cè)重：如果程序的使用次數(shù)較少，則應該力求算法簡明易懂，而易于轉(zhuǎn)換為上機程序；如果程序反復多次使用，則應該盡可能選用快速算法；如果解決問題的數(shù)據(jù)量極大，機器的內(nèi)存空間較小，則在編寫算法時應該考慮如何節(jié)省空間。本次課程設計培養(yǎng)了了我們獨立思考的能力，提高了我們的動手操作水平。在具體設計操作中，我們鞏固了本學期所學的數(shù)據(jù)結(jié)構(gòu)與算法的理論知識，進一步提高了自己的編程能力。這也是課程設計的最終目的所在。通過實際操作，開發(fā)

20、了自己的邏輯思維能力，培養(yǎng)了分析問題、解決問題的能力。但在程序設計的過程中我也深刻的感受到自己實力的不足，無法靈活的運用各種工具和函數(shù)，對于課程所講的東西也無法在脫離課本的情況中完成，我意識到自己在今后的學習生活中，一定要勤于思考，扎實掌握理論知識，靈活運用課上所學的東西，做一個優(yōu)秀的程序員。參考文獻1Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest. 北京. 算法導論(第三版)M. 機械工業(yè)出版社:Thomas H.Cormen, 20132 劉汝佳, 黃亮. 北京. 清華大學出版社. 算法藝術(shù)與信息學競賽.3 王曉東. 北京. 清華

21、大學出版社. 算法設計與分析（第二版）.附錄1：模擬計算器源程序清單/ 程序名稱：Calculator.cpp/ 程序功能：模擬計算器/ 程序作者：*/ 學號: */ 最后修改日期：2013-7-5/*課題4：設計一個模擬計算器的程序，要求能對包含加、減、乘、除、括號運算符及SQR和ABS函數(shù)的任意整型表達式進行求解。 要求：要檢查有關(guān)運算的條件，并對錯誤的條件產(chǎn)生報警。我的代碼在此基礎上增加了幾個功能：1. 不僅支持整數(shù)運算，還支持浮點數(shù)運算2. 可支持表達式的嵌套，Ex：A(1+2*S(3)）*/#include <iostream>#include <cstdlib&g

22、t;#include <cstring>#include <string>#include <cstdio>#include <stack>#include <cmath>using namespace std;#define mem(a,b) memset(a,b,sizeof(a)const int MaxLength=1010; /數(shù)組的最大存儲空間bool IsNum(char c) /判斷是否是數(shù)字 if(c>='0' && c<='9')return true;

23、return false;bool IsSign(char c) /判斷是否是運算符號 if(c='+' | c='-' | c='*' | c='/')return true; return false;int GetKey(char c) /定義運算符的關(guān)鍵字 int key; switch(c) case '+':key=1;break; case '-':key=1;break; case '*':key=2;break; case '/':key=2;bre

24、ak; case '(':key=4;break; case ')':key=5;break; return key;double Cal(char c,double a,double b) /根據(jù)運算符來計算運算結(jié)果 switch(c) case '+':return a+b; case '-':return a-b; case '*':return a*b; case '/':return a/b; return 0;class Graph /圖形界面類public: void Window()

25、; /圖形窗口函數(shù);void Graph:Window() cout<<" |=歡迎使用本計算器=|"<<endl; cout<<" | 1.本計算器支持表達式計算,輸入數(shù)據(jù)為實數(shù) |"<<endl; cout<<" | 2.可支持表達式的嵌套,Ex:A(1+2*S(3) |"<<endl; cout<<" |-|"<<endl; cout<<" | 7 8 9 + / |"<<

26、;endl; cout<<" | 4 5 6 - A(abs) |"<<endl; cout<<" | 1 2 3 * S(sqrt) |"<<endl; cout<<" |-|"<<endl;class Expressionpublic: void Input(); /表達式輸入 void Init(); /表達式數(shù)據(jù)初始化 bool SloveExp(); /表達式處理過程 bool CheckExp(); /檢查表達式是否合法 void GetSuffix(

27、); /得到后綴表達式 double GetAns(); /根據(jù)后綴表達式來得到結(jié)果 void Display(); /輸出表達式結(jié)果private: int Size; /后綴表達式的長度 string s; /表達式存儲 bool HaveAns; /表達式是否有結(jié)果 double Ans; /表達式結(jié)果 pair<double,int> SufExpMaxLength; /后綴表達式存儲 int PosMaxLength; /中綴表達式中'('對應的')'數(shù)組下標位置;void Expression:Input() /表達式輸入 cout<

28、;<"請輸入您的表達式: " cin>>s;void Expression:Init() /表達式數(shù)據(jù)初始化 HaveAns=false; mem(Pos,-1);bool Expression:SloveExp() if(HaveAns=CheckExp()=0)return HaveAns=false; /表達式不合法，退出 GetSuffix(); /得到后綴表達式 GetAns(); /根據(jù)后綴表達式來得到結(jié)果 return true;bool Expression:CheckExp() /檢查表達式是否合法 int i,j,cnt; int su

29、m=0; for(i=0;i<s.length();i+) /檢驗括號是否合法，以及是否存在非法字符 if(!IsNum(si) && !IsSign(si) && si!='(' && si!=')' && si!='A' && si!='S' && si!='.')return false; if(si='(')sum+=1; else if(si=')')sum-=1; if(

30、sum<0)return false; /括號匹配不合法 if(sum!=0)return false; for(i=0;i<s.length();i+) if(IsSign(si) if(si='/' && si+1='0') /判斷除法的被除數(shù)是不是為零 return false; for(i=0;i<s.length();i+) /括號匹配，獲取'('對應的')'的下標 if(si!=')')continue; for(j=i;j>=0;j-) /遇到')

31、9;括號 if(sj=')')sum+=1; else if(sj='(')sum-=1; if(sum=0) /如果sum的值為0,那么找到')'的匹配括號 Posj=i; break; return true; /表達式正確void Expression:GetSuffix() /得到后綴表達式 int i,j,w,k=0; char stMaxLength; pair<double,int> numMaxLength; /保存后綴表達式，double為數(shù)據(jù)，int標記符號 for(i=0;i<s.length();i+)

32、if(si='A' | si='S') /遇到Abs()或者Sqrt()遞歸處理子表達式 Expression temp; /創(chuàng)建子表達式 temp.Init(); for(j=0;i+j+2<Posi+1;j+) /復制表達式 stj=si+j+2; stj=0; temp.s=st; /復制表達式 temp.SloveExp(); /得到子表達式的值 numk.first=(si='A'?fabs(temp.Ans):sqrt(temp.Ans); numk.second=0; /標記為數(shù)據(jù) if(si-1='-' &a

33、mp;& (i-1=0 | si-2='(')numk.first=-numk.first; k+; i=Posi+1; else if(IsNum(si) /處理數(shù)據(jù) double sum=0; int ok=0,w=1; /*把數(shù)據(jù)提取出來*/ for(j=i;j<s.length() && (IsNum(sj) | sj='.');j+) if(sj!='.')sum=sum*10+(double)(sj-'0'); else ok=1,w=0; if(ok)w+; /小數(shù)點位數(shù)統(tǒng)計 numk.

34、first=sum/pow(10.0,(double)(w-1); /處理浮點數(shù) numk.second=0; if(si-1='-' && (i-1=0 | si-2='(')numk.first=-numk.first; k+; i=j-1; else /為符號,直接存入,特殊考慮負數(shù) if(si='-' && (i=0 | si-1='(')continue; numk.first=(double)si; numk+.second=GetKey(si); /* 雙棧,sta1存放后綴表達式,s

35、ta2存放運算符符號*/ stack<pair<double,int> > sta1,sta2; for(i=0;i<k;i+) if(!numi.second) /為數(shù)據(jù),直接放入sta1 sta1.push(numi); else if(numi.second=4) /為'(',直接放入sta2 sta2.push(numi); else if(numi.second=5) /為')',從sta2中取出運算符,push到sta1中,直到遇到')' while(sta2.top().second!=4) sta1.push(sta2.top(); sta2.pop(); sta2.pop(); /取出'('括號 /*為'+','-','*'或者'/'運算符,取出sta2中的運算符, push到sta1中,直到比sta2棧頂中的優(yōu)先級大*/ else while(!sta2.empty() && sta2.top().second>=numi.second && sta2.top().second