數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-計(jì)算器

1、 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 實(shí)驗(yàn)一：計(jì)算器設(shè)計(jì)要求1、問題描述：設(shè)計(jì)一個(gè)計(jì)算器，可以實(shí)現(xiàn)計(jì)算器的簡(jiǎn)單運(yùn)算，輸出并檢驗(yàn)結(jié)果的正確性，以及檢驗(yàn)運(yùn)算表達(dá)式的正確性。2、輸入：不含變量的數(shù)學(xué)表達(dá)式的中綴形式，可以接受的操作符包括+、-、*、/、%、(、)。具體事例如下：3、 輸出：如果表達(dá)式正確，則輸出表達(dá)式的正確結(jié)果；如果表達(dá)式非法，則輸出錯(cuò)誤信息。具體事例如下： 知識(shí)點(diǎn)：堆棧、隊(duì)列實(shí)際輸入輸出情況：正確的表達(dá)式對(duì)負(fù)數(shù)的處理表達(dá)式括號(hào)不匹配表達(dá)式出現(xiàn)非法字符表達(dá)式中操作符位置錯(cuò)誤求余操作符左右出現(xiàn)非整數(shù)其他輸入錯(cuò)誤數(shù)據(jù)結(jié)構(gòu)與算法描述解決問題的整體思路：將用戶輸入的中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式，再利用轉(zhuǎn)換后

2、的后綴表達(dá)式進(jìn)行計(jì)算得出結(jié)果。解決本問題所需要的數(shù)據(jù)結(jié)構(gòu)與算法：用到的數(shù)據(jù)結(jié)構(gòu)是堆棧。主要算法描述如下：A將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式： 1. 將中綴表達(dá)式從頭逐個(gè)字符掃描，在此過程中，遇到的字符有以下幾種情況：1）數(shù)字2）小數(shù)點(diǎn)3）合法操作符+ - * / %4）左括號(hào)5）右括號(hào)6）非法字符2. 首先為操作符初始化一個(gè)map<std:string,int> priority，用于保存各個(gè)操作符的優(yōu)先級(jí)，其中+ -為0，* / %為13. 對(duì)于輸入的字符串from和輸出的字符串to，采用以下過程：初始化遍歷器 std:string:iterator it=infix.begin()

3、在當(dāng)it!=from.end()，執(zhí)行如下操作4. 遇到數(shù)字或小數(shù)點(diǎn)時(shí)將其加入到后綴表達(dá)式：case '1':case '2':case '3':case'4':case '5':case '6':case'7':case '8':case'9':case '0':case '.':to=to+*it;break;5. 遇到操作符（+，-，*，/，%）時(shí)，如果此時(shí)棧頂操作符的優(yōu)先級(jí)比此時(shí)的操作符優(yōu)先級(jí)低，則將其入棧，否則

4、將棧中的操作符從棧頂逐個(gè)加入到后綴表達(dá)式，直到?？栈蛘哂龅阶罄ㄌ?hào)，并將此時(shí)的操作符加入到棧中，在此過程中需判斷表達(dá)式中是否出現(xiàn)輸入錯(cuò)誤：case '+':case '-':case '*':case '/':case '%':if(it+1)=from.end()cout<<"輸入錯(cuò)誤：運(yùn)算符號(hào)右邊缺少運(yùn)算數(shù)"<<endl;return false;if(*it='*'|*it='/')&&it=from.begin()co

5、ut<<"輸入錯(cuò)誤：運(yùn)算符號(hào)左邊缺少運(yùn)算數(shù)"<<endl;return false;if(it+1)!=from.end()&&(*(it+1)='+'|*(it+1)='-'|*(it+1)='*'|*(it+1)='/'|*(it+1)='%')cout<<"輸入錯(cuò)誤：運(yùn)算符號(hào)連續(xù)出現(xiàn)"<<endl;return false;to=to+" "if(sym.empty()sym.push(

6、*it);break;tem=sym.top();while(pri*it<=pritem&&!sym.empty()&&tem!='(')to=to+tem+" "sym.pop();if(sym.empty()break;tem=sym.top();sym.push(*it);break;6. 遇到“（”時(shí)，直接將其加入操作符棧，并且檢測(cè)輸入錯(cuò)誤，并且當(dāng)括號(hào)后的第一個(gè)符號(hào)為-時(shí)，說明用戶試圖輸入負(fù)號(hào)，這種情況我們向目標(biāo)表達(dá)式輸出一個(gè)0，以達(dá)到處理負(fù)號(hào)的目的：case '(':if(it+1)=from

7、.end()cout<<"輸入錯(cuò)誤：表達(dá)式以左括號(hào)結(jié)尾"<<endl;return false;/若以+或者-開頭，則按照正負(fù)號(hào)看待，向目標(biāo)表達(dá)式中加入一個(gè)0if(*(it+1)='-'|*(it+1)='+')to=to+'0'if(it+1)!=from.end()&&(*(it+1)='*'|*(it+1)='/'|*(it+1)='%'|*(it+1)=')')cout<<"輸入錯(cuò)誤：左括號(hào)右邊

8、不能為運(yùn)算符號(hào)或右括號(hào)"<<endl;return false;if(it!=from.begin()&&(*(it-1)!='+'&&*(it-1)!='-'&&*(it-1)!='*'&&*(it-1)!='/'&&*(it-1)!='%'&&*(it-1)!='(')cout<<"輸入錯(cuò)誤：左括號(hào)左邊不能為運(yùn)算數(shù)或右括號(hào)"<<endl

9、;return false;sym.push(*it);break;5.遇到“）”時(shí)，將棧中的操作符從棧頂逐個(gè)彈出并放入后綴表達(dá)式中，直到在棧中遇到“（”，并將“（”從棧中彈出：case ')':if(it+1)!=from.end()&&*(it+1)!='+'&&*(it+1)!='-'&&*(it+1)!='*'&&*(it+1)!='/'&&*(it+1)!='%'&&*(it+1)!='

10、)')cout<<"輸入錯(cuò)誤：右括號(hào)右邊不能為運(yùn)算數(shù)"<<endl;return false;if(it!=from.begin()&&(*(it-1)='+'|*(it-1)='-'|*(it-1)='*'|*(it-1)='/'|*(it-1)='%')cout<<"輸入錯(cuò)誤：右括號(hào)左邊不能為運(yùn)算符號(hào)"<<endl;return false;to=to+" "if(sym.empt

11、y()cout<<"輸入錯(cuò)誤：表達(dá)式以右括號(hào)開始"<<endl;return false; tem=sym.top();while(tem!='(')to=to+tem+" "sym.pop();if(sym.empty()cout<<"輸入錯(cuò)誤：括號(hào)匹配有誤"<<endl;return false;tem=sym.top();sym.pop();break;B計(jì)算后綴表達(dá)式的主要思想：逐個(gè)字符的掃描后綴表達(dá)式，遇到單個(gè)數(shù)字或小數(shù)點(diǎn)時(shí)則先將其將其存到一個(gè)字符串中，當(dāng)遇到后

12、綴表達(dá)式中的分隔符（這里使用空格）時(shí)，則將這個(gè)字符串轉(zhuǎn)化為數(shù)字放到堆棧numstack中；case '1':case '2':case '3':case'4':case '5':case '6':case'7':case '8':case'9':case '0':case '.':numtemp+=*it;break;case ' ':if(numtemp!="")if(numtemp

13、.find('.')&&numtemp.find('.',(numtemp.find('.')+1)!=string:npos)cout<<"輸入錯(cuò)誤：小數(shù)點(diǎn)數(shù)目超出："+numtemp<<endl;return false;strm.str(numtemp);strm>>d;numstack.push(d);numtemp=""strm.str("");strm.clear();break;break;2.遇到操作符+，-，*，/，%

14、時(shí)，將堆棧numstack中的棧頂?shù)膬蓚€(gè)數(shù)取出來，進(jìn)行相應(yīng)操作的運(yùn)算，并將結(jié)果加入到堆棧numstack中；case '+':d2=numstack.top();numstack.pop();d1=numstack.top();numstack.pop();numstack.push(d1+d2);break;case '-':d2=numstack.top();numstack.pop();d1=numstack.top();numstack.pop();numstack.push(d1-d2);break;case '*':d2=numsta

15、ck.top();numstack.pop();d1=numstack.top();numstack.pop();numstack.push(d1*d2);break;case '/':d2=numstack.top();numstack.pop();if(fabs(d2)<0.0000001)cout<<"輸入錯(cuò)誤：除數(shù)不能為0"<<endl;return false;d1=numstack.top();numstack.pop();numstack.push(d1/d2);break;case '%':d2=

16、numstack.top();numstack.pop();d1=numstack.top();numstack.pop();if(fabs(d2-(int)d2)<0.0000001&&(fabs(d1-(int)d1)<0.0000001)int n1=(int)d1;int n2=(int)d2;numstack.push(double)(n1%n2);break;elsecerr<<"輸入錯(cuò)誤：求模操作只能作用于整數(shù)"<<endl;return false;3.直到后綴表達(dá)式掃描完并且堆棧numstack中只有一個(gè)

17、數(shù)值，則此數(shù)值為計(jì)算的最終結(jié)果，否則說明輸入有誤。分析與探討：1、測(cè)試結(jié)果分析：測(cè)試結(jié)果見本篇開始的實(shí)際輸入輸出結(jié)果。該計(jì)算器幾乎實(shí)現(xiàn)了所有相關(guān)功能，包括簡(jiǎn)單計(jì)算、負(fù)數(shù)小數(shù)處理，容錯(cuò)，并且健壯性好，對(duì)于錯(cuò)誤的表達(dá)式可以給出適當(dāng)提示，不會(huì)導(dǎo)致程序崩潰。2、算法分析 1、對(duì)于中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式： 時(shí)間復(fù)雜性為O(n) 2、對(duì)于后綴表達(dá)式的計(jì)算：時(shí)間復(fù)雜性為O(n)綜上，該程序算法的時(shí)間復(fù)雜度為O(n)3、算法改進(jìn) 該程序存在的主要問題是命令行式的用戶界面不夠友好。Windows下的用戶圖形界面需要MFC方面的知識(shí)，因?yàn)闀r(shí)間關(guān)系沒有進(jìn)行這方面的深入學(xué)習(xí)。附錄：源代碼文件一.Expressio

18、nHandler.h#include<string>#include<map>#include<stack>#include<iostream>#include<sstream>using namespace std;class ExpressionHandlerpublic:ExpressionHandler(string exp)this->exp=exp;bool infixtoprofix(string& exp);bool doprofix(string profix,double &result);p

19、rivate:string exp;文件二.ExpressionHandler.cpp/Coded By CS_Zhanglin#include"ExpressionHandler.h"bool ExpressionHandler:infixtoprofix(string& exp)string from=this->exp;string to=""stack<char> sym;map<char,int> pri;char tem;pri'+'=1;pri'-'=1;pri'

20、*'=2;pri'/'=2;pri'%'=2;string:iterator it=from.begin();if(*it='+'|*it='-')to+='0'while(it!=from.end()/cout<<1<<endl;switch(*it)case '1':case '2':case '3':case'4':case '5':case '6':case'7':

21、case '8':case'9':case '0':case '.':to=to+*it;break;case '+':case '-':case '*':case '/':case '%':if(it+1)=from.end()cout<<"輸入錯(cuò)誤：運(yùn)算符號(hào)右邊缺少運(yùn)算數(shù)"<<endl;return false;if(*it='*'|*it='/')&&it

22、=from.begin()cout<<"輸入錯(cuò)誤：運(yùn)算符號(hào)左邊缺少運(yùn)算數(shù)"<<endl;return false;if(it+1)!=from.end()&&(*(it+1)='+'|*(it+1)='-'|*(it+1)='*'|*(it+1)='/'|*(it+1)='%')cout<<"輸入錯(cuò)誤：運(yùn)算符號(hào)連續(xù)出現(xiàn)"<<endl;return false;to=to+" "if(sym.e

23、mpty()sym.push(*it);break;tem=sym.top();while(pri*it<=pritem&&!sym.empty()&&tem!='(')to=to+tem+" "sym.pop();if(sym.empty()break;tem=sym.top();sym.push(*it);break;case '(':if(it+1)=from.end()cout<<"輸入錯(cuò)誤：表達(dá)式以左括號(hào)結(jié)尾"<<endl;return false;i

24、f(*(it+1)='-'|*(it+1)='+')to=to+'0'if(it+1)!=from.end()&&(*(it+1)='*'|*(it+1)='/'|*(it+1)='%'|*(it+1)=')')cout<<"輸入錯(cuò)誤：左括號(hào)右邊不能為運(yùn)算符號(hào)或右括號(hào)"<<endl;return false;if(it!=from.begin()&&(*(it-1)!='+'&&

25、;*(it-1)!='-'&&*(it-1)!='*'&&*(it-1)!='/'&&*(it-1)!='%'&&*(it-1)!='(')cout<<"輸入錯(cuò)誤：左括號(hào)左邊不能為運(yùn)算數(shù)或右括號(hào)"<<endl;return false;sym.push(*it);break;case ')':if(it+1)!=from.end()&&*(it+1)!='+'&

26、amp;&*(it+1)!='-'&&*(it+1)!='*'&&*(it+1)!='/'&&*(it+1)!='%'&&*(it+1)!=')')cout<<"輸入錯(cuò)誤：右括號(hào)右邊不能為運(yùn)算數(shù)"<<endl;return false;if(it!=from.begin()&&(*(it-1)='+'|*(it-1)='-'|*(it-1)='*

27、'|*(it-1)='/'|*(it-1)='%')cout<<"輸入錯(cuò)誤：右括號(hào)左邊不能為運(yùn)算符號(hào)"<<endl;return false;to=to+" "if(sym.empty()cout<<"輸入錯(cuò)誤：表達(dá)式以右括號(hào)開始"<<endl;return false; tem=sym.top();while(tem!='(')to=to+tem+" "sym.pop();if(sym.empty()cout&

28、lt;<"輸入錯(cuò)誤：括號(hào)匹配有誤"<<endl;return false;tem=sym.top();sym.pop();break;default:cout<<"輸入錯(cuò)誤：未知符號(hào)"<<endl;return false;+it;if(!sym.empty()to=to+" "tem=sym.top();while(!sym.empty()if(tem='(')cout<<"輸入錯(cuò)誤：括號(hào)匹配有誤"<<endl;return fal

29、se;to=to+tem+" "sym.pop();if(sym.empty()break;tem=sym.top();exp=to;return true;bool ExpressionHandler:doprofix(string profix,double& result)string numtemp;stack<double> numstack;stringstream strm;double d,d1,d2;for(string:iterator it=profix.begin();it!=profix.end();+it)switch (*i

30、t)case '1':case '2':case '3':case'4':case '5':case '6':case'7':case '8':case'9':case '0':case '.':numtemp+=*it;break;case ' ':if(numtemp!="")if(numtemp.find('.')&&numtemp.find(&#

31、39;.',(numtemp.find('.')+1)!=string:npos)cout<<"輸入錯(cuò)誤：小數(shù)點(diǎn)數(shù)目超出："+numtemp<<endl;return false;strm.str(numtemp);strm>>d;numstack.push(d);numtemp=""strm.str("");strm.clear();break;break;case '+':d2=numstack.top();numstack.pop();d1=numsta

32、ck.top();numstack.pop();numstack.push(d1+d2);break;case '-':d2=numstack.top();numstack.pop();d1=numstack.top();numstack.pop();numstack.push(d1-d2);break;case '*':d2=numstack.top();numstack.pop();d1=numstack.top();numstack.pop();numstack.push(d1*d2);break;case '/':d2=numstack.top();numstack.pop();if(fabs(d2)<0.0000001)cout<<"輸入錯(cuò)誤：除數(shù)不能為0"<<endl;return false;d1=numstack.top();numstack.pop();numstack.push(d1/d2);break;case '%':