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

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

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

3、在當it!=from.end()，執(zhí)行如下操作4. 遇到數(shù)字或小數(shù)點時將其加入到后綴表達式：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. 遇到操作符（+，-，*，/，%）時，如果此時棧頂操作符的優(yōu)先級比此時的操作符優(yōu)先級低，則將其入棧，否則

4、將棧中的操作符從棧頂逐個加入到后綴表達式，直到棧空或者遇到左括號，并將此時的操作符加入到棧中，在此過程中需判斷表達式中是否出現(xiàn)輸入錯誤：case '+':case '-':case '*':case '/':case '%':if(it+1)=from.end()cout<<"輸入錯誤：運算符號右邊缺少運算數(shù)"<<endl;return false;if(*it='*'|*it='/')&&it=from.begin()co

5、ut<<"輸入錯誤：運算符號左邊缺少運算數(shù)"<<endl;return false;if(it+1)!=from.end()&&(*(it+1)='+'|*(it+1)='-'|*(it+1)='*'|*(it+1)='/'|*(it+1)='%')cout<<"輸入錯誤：運算符號連續(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. 遇到“（”時，直接將其加入操作符棧，并且檢測輸入錯誤，并且當括號后的第一個符號為-時，說明用戶試圖輸入負號，這種情況我們向目標表達式輸出一個0，以達到處理負號的目的：case '(':if(it+1)=from

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

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

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

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

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

12、綴表達式中的分隔符（這里使用空格）時，則將這個字符串轉(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<<"輸入錯誤：小數(shù)點數(shù)目超出："+numtemp<<endl;return false;strm.str(numtemp);strm>>d;numstack.push(d);numtemp=""strm.str("");strm.clear();break;break;2.遇到操作符+，-，*，/，%

14、時，將堆棧numstack中的棧頂?shù)膬蓚€數(shù)取出來，進行相應(yīng)操作的運算，并將結(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<<"輸入錯誤：除數(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<<"輸入錯誤：求模操作只能作用于整數(shù)"<<endl;return false;3.直到后綴表達式掃描完并且堆棧numstack中只有一個

17、數(shù)值，則此數(shù)值為計算的最終結(jié)果，否則說明輸入有誤。分析與探討：1、測試結(jié)果分析：測試結(jié)果見本篇開始的實際輸入輸出結(jié)果。該計算器幾乎實現(xiàn)了所有相關(guān)功能，包括簡單計算、負數(shù)小數(shù)處理，容錯，并且健壯性好，對于錯誤的表達式可以給出適當提示，不會導致程序崩潰。2、算法分析 1、對于中綴表達式轉(zhuǎn)換成后綴表達式： 時間復雜性為O(n) 2、對于后綴表達式的計算：時間復雜性為O(n)綜上，該程序算法的時間復雜度為O(n)3、算法改進 該程序存在的主要問題是命令行式的用戶界面不夠友好。Windows下的用戶圖形界面需要MFC方面的知識，因為時間關(guān)系沒有進行這方面的深入學習。附錄：源代碼文件一.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<<"輸入錯誤：運算符號右邊缺少運算數(shù)"<<endl;return false;if(*it='*'|*it='/')&&it

22、=from.begin()cout<<"輸入錯誤：運算符號左邊缺少運算數(shù)"<<endl;return false;if(it+1)!=from.end()&&(*(it+1)='+'|*(it+1)='-'|*(it+1)='*'|*(it+1)='/'|*(it+1)='%')cout<<"輸入錯誤：運算符號連續(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<<"輸入錯誤：表達式以左括號結(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<<"輸入錯誤：左括號右邊不能為運算符號或右括號"<<endl;return false;if(it!=from.begin()&&(*(it-1)!='+'&&

25、;*(it-1)!='-'&&*(it-1)!='*'&&*(it-1)!='/'&&*(it-1)!='%'&&*(it-1)!='(')cout<<"輸入錯誤：左括號左邊不能為運算數(shù)或右括號"<<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<<"輸入錯誤：右括號右邊不能為運算數(shù)"<<endl;return false;if(it!=from.begin()&&(*(it-1)='+'|*(it-1)='-'|*(it-1)='*

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

28、lt;<"輸入錯誤：括號匹配有誤"<<endl;return false;tem=sym.top();sym.pop();break;default:cout<<"輸入錯誤：未知符號"<<endl;return false;+it;if(!sym.empty()to=to+" "tem=sym.top();while(!sym.empty()if(tem='(')cout<<"輸入錯誤：括號匹配有誤"<<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<<"輸入錯誤：小數(shù)點數(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<<"輸入錯誤：除數(shù)不能為0"<<endl;return false;d1=numstack.top();numstack.pop();numstack.push(d1/d2);break;case '%':