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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告實(shí)驗(yàn)一：計(jì)算器設(shè)計(jì)要求1、問題描述：設(shè)計(jì)一個(gè)計(jì)算器，可以實(shí)現(xiàn)計(jì)算器的簡單運(yùn)算，輸出并檢驗(yàn)結(jié)果的正確性，以及檢驗(yàn)運(yùn)算表達(dá)式的正確性。2、輸入：不含變量的數(shù)學(xué)表達(dá)式的中綴形式，可以接受的操作符包括 +、-、*、/、%、(、)。具體事例如下：3、輸出：如果表達(dá)式正確，則輸出表達(dá)式的正確結(jié)果；如果表達(dá)式非法，則輸出錯(cuò)誤信息。具體事例如下：知識點(diǎn)：堆棧、隊(duì)列實(shí)際輸入輸出情況：正確的表達(dá)式對負(fù)數(shù)的處理表達(dá)式括號不匹配表達(dá)式出現(xiàn)非法字符表達(dá)式中操作符位置錯(cuò)誤求余操作符左右出現(xiàn)非整數(shù)其他輸入錯(cuò)誤數(shù)據(jù)結(jié)構(gòu)與算法描述解決問題的整體思路：將用戶輸入的中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式，再利用轉(zhuǎn)換后的后綴表達(dá)式進(jìn)行計(jì)算得出結(jié)果。解決本問題所需要的數(shù)據(jù)結(jié)構(gòu)與算法：用到的數(shù)據(jù)結(jié)構(gòu)是堆棧。主要算法描述如下：．將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式：將中綴表達(dá)式從頭逐個(gè)字符掃描，在此過程中，遇到的字符有以下幾種情況：1）數(shù)字2）小數(shù)點(diǎn)3）合法操作符 +-*/%4）左括號5）右括號6）非法字符2.首先為操作符初始化一個(gè) map<std::string,int> priority，用于保存各個(gè)操作符的優(yōu)先級，其中 +-為0，*/%為1對于輸入的字符串from和輸出的字符串to，采用以下過程：初始化遍歷器 std::string::iteratorit=infix.begin()在當(dāng)it!=from.end() ，執(zhí)行如下操作遇到數(shù)字或小數(shù)點(diǎn)時(shí)將其加入到后綴表達(dá)式：'8'

case:case'9'{

'1':case:case '0'

'2':case

:case'.':

'3'

:case'4'

:case

'5'

:case

'6'

:case'7'

:caseto=to+*it;break;}遇到操作符（+，-，*，/，%）時(shí)，如果此時(shí)棧頂操作符的優(yōu)先級比此時(shí)的操作符優(yōu)先級低，則將其入棧，否則將棧中的操作符從棧頂逐個(gè)加入到后綴表達(dá)式，直到棧空或者遇到左括號，并將此時(shí)的操作符加入到棧中，在此過程中需判斷表達(dá)式中是否出現(xiàn)輸入錯(cuò)誤：case'+' :case'-' :case '*' :case '/' :case '%':{if((it+1)==from.end()){cout<<"輸入錯(cuò)誤：運(yùn)算符號右邊缺少運(yùn)算數(shù) "<<endl;return false ;}if((*it== '*' ||*it== '/' )&&it==from.begin()){cout<<"輸入錯(cuò)誤：運(yùn)算符號左邊缺少運(yùn)算數(shù) "<<endl;return false ;}if((it+1)!=from.end()&&(*(it+1)==

'+'

||*(it+1)==

'-'

||*(it+1)==

'*'

||*(it+1)==

'/'||*(it+1)== '%')){cout<<return

"輸入錯(cuò)誤：運(yùn)算符號連續(xù)出現(xiàn)false ;

"<<endl;}to=to+

""

;if(sym.empty()){sym.push(*it);break;}tem=sym.top();while(pri[*it]<=pri[tem]&&!sym.empty()&&tem!= '(' ){to=to+tem+"" ;sym.pop();if(sym.empty()) break;tem=sym.top();}sym.push(*it);break;}遇到“（”時(shí)，直接將其加入操作符棧，并且檢測輸入錯(cuò)誤，并且當(dāng)括號后的第一個(gè)符號為 -時(shí)，說明用戶試圖輸入負(fù)號，這種情況我們向目標(biāo)表達(dá)式輸出一個(gè) 0，以達(dá)到處理負(fù)號的目的：case '(' :{if((it+1)==from.end()){cout<<"輸入錯(cuò)誤：表達(dá)式以左括號結(jié)尾 "<<endl;returnfalse;}//若以+或者-開頭，則按照正負(fù)號看待，向目標(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ò)誤：左括號右邊不能為運(yùn)算符號或右括號 "<<endl;return false ;}if(it!=from.begin()&&(*(it-1)!= '+' &&*(it-1)!= '-' &&*(it-1)!= '*' &&*(it-1)!= '/' &&*(it-1)!='%'&&*(it-1)!=

'('{

))cout<<"輸入錯(cuò)誤：左括號左邊不能為運(yùn)算數(shù)或右括號 "<<endl;return false ;}sym.push(*it);break;}遇到“）”時(shí)，將棧中的操作符從棧頂逐個(gè)彈出并放入后綴表達(dá)式中，直到在棧中遇到“（”，并將“（”從棧中彈出：case ')' :{if((it+1)!=from.end()&&*(it+1)!=+1)!='%'&&*(it+1)!= ')' )

'+'

&&*(it+1)!=

'-'

&&*(it+1)!=

'*'

&&*(it+1)!=

'/'

&&*(it{cout<<"輸入錯(cuò)誤：右括號右邊不能為運(yùn)算數(shù) "<<endl;return false ;}if(it!=from.begin()&&(*(it-1)==

'+'

||*(it-1)==

'-'

||*(it-1)==

'*'

||*(it-1)==

'/'

||*(it-1)=='%' )){cout<<"輸入錯(cuò)誤：右括號左邊不能為運(yùn)算符號 "<<endl;return false ;}to=to+"" ;if(sym.empty()){cout<<"輸入錯(cuò)誤：表達(dá)式以右括號開始 "<<endl;return false;}tem=sym.top();while(tem!='(' ){to=to+tem+"" ;sym.pop();if(sym.empty()){cout<<"輸入錯(cuò)誤：括號匹配有誤 "<<endl;return false;}tem=sym.top();}sym.pop();break;}．計(jì)算后綴表達(dá)式的主要思想：逐個(gè)字符的掃描后綴表達(dá)式， 遇到單個(gè)數(shù)字或小數(shù)點(diǎn)時(shí)則先將其將其存到一個(gè)字符串中，當(dāng)遇到后綴表達(dá)式中的分隔符（這里使用空格）時(shí)，則將這個(gè)字符串轉(zhuǎn)化為數(shù)字放到堆棧 numstack中；'8'

case:case'9'{

'1':case:case '0'

'2':case

:case'.':

'3'

:case'4'

:case

'5'

:case

'6'

:case'7'

:casenumtemp+=*it;break;}case'' :{if(numtemp!="" ){if(numtemp.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;}遇到操作符+，-，*，/，%時(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=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'%':{d2=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;}else{cerr<<"輸入錯(cuò)誤：求模操作只能作用于整數(shù) "<<endl;return false ;}}3.直到后綴表達(dá)式掃描完并且堆棧 numstack 中只有一個(gè)數(shù)值，則此數(shù)值為計(jì)算的最終結(jié)果，否則說明輸入有誤 。分析與探討：1、測試結(jié)果分析：測試結(jié)果見本篇開始的實(shí)際輸入輸出結(jié)果。該計(jì)算器幾乎實(shí)現(xiàn)了所有相關(guān)功能，包括簡單計(jì)算、負(fù)數(shù)小數(shù)處理，容錯(cuò)，并且健壯性好，對于錯(cuò)誤的表達(dá)式可以給出適當(dāng)提示，不會(huì)導(dǎo)致程序崩潰。2、算法分析1、對于中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式： 時(shí)間復(fù)雜性為O(n)2、對于后綴表達(dá)式的計(jì)算：時(shí)間復(fù)雜性為 O(n)綜上，該程序算法的時(shí)間復(fù)雜度為 O(n)3、算法改進(jìn)該程序存在的主要問題是命令行式的用戶界面不夠友好。Windows 下的用戶圖形界面需要 MFC方面的知識，因?yàn)闀r(shí)間關(guān)系沒有進(jìn)行這方面的深入學(xué)習(xí)。附錄：源代碼文件一.ExpressionHandler.h#include<string>#include<map>#include<stack>#include<iostream>#include<sstream>usingnamespacestd;classExpressionHandler{public:ExpressionHandler( string exp){this->exp=exp;}boolinfixtoprofix( string &exp);booldoprofix( string profix, double &result);private :string exp;};文件二.ExpressionHandler.cpp//CodedByCS_Zhanglin#include "ExpressionHandler.h"bool ExpressionHandler ::infixtoprofix(string from=this->exp;string to="";stack<char>sym;map<char,int >pri;chartem;pri[ '+']=1;pri[ '-' ]=1;pri[ '*' ]=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'8' :case'9' :case '0' :case '.' :{

string'3'

&exp){:case'4'

:case

'5'

:case

'6'

:case'7'

:caseto=to+*it;break;case

}'+'{

:case

'-'

:case

'*'

:case

'/'

:case

'%':if((it+1)==from.end()){cout<<"輸入錯(cuò)誤：運(yùn)算符號右邊缺少運(yùn)算數(shù) "<<endl;return false ;}if((*it== '*' ||*it== '/' )&&it==from.begin()){cout<<"輸入錯(cuò)誤：運(yùn)算符號左邊缺少運(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)算符號連續(xù)出現(xiàn) "<<endl;return false ;}to=to+"" ;if(sym.empty()){sym.push(*it);break;}tem=sym.top();while(pri[*it]<=pri[tem]&&!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á)式以左括號結(jié)尾 "<<endl;return false ;}if(*(it+1)==

'-'

||*(it+1)==

'+'){to=to+'0'

;}if((it+1)!=from.end()&&((*(it+1)==

'*'

||*(it+1)==

'/'

||*(it+1)==

'%'||*(it+1)==

')'

))){cout<<"輸入錯(cuò)誤：左括號右邊不能為運(yùn)算符號或右括號return false ;

"<<endl;}if(it!=from.begin()&&(*(it-1)!=

'+'

&&*(it-1)!=

'-'

&&*(it-1)!=

'*'

&&*(it-1)!=

'/'

&&*(it-1)!='%'&&*(it-1)!= '(' )){cout<<"輸入錯(cuò)誤：左括號左邊不能為運(yùn)算數(shù)或右括號return false ;

"<<endl;}sym.push(*it);break;}case')' :{if((it+1)!=from.end()&&*(it+1)!=+1)!='%'&&*(it+1)!= ')' )

'+'

&&*(it+1)!=

'-'

&&*(it+1)!=

'*'

&&*(it+1)!=

'/'

&&*(it{cout<<"輸入錯(cuò)誤：右括號右邊不能為運(yùn)算數(shù) "<<endl;return false ;}if(it!=from.begin()&&(*(it-1)==

'+'

||*(it-1)==

'-'

||*(it-1)==

'*'

||*(it-1)==

'/'

||*(it-1)=='%' )){cout<<"輸入錯(cuò)誤：右括號左邊不能為運(yùn)算符號 "<<endl;return false ;}to=to+"" ;if(sym.empty()){cout<<"輸入錯(cuò)誤：表達(dá)式以右括號開始 "<<endl;return false;}tem=sym.top();while(tem!='(' ){to=to+tem+"" ;sym.pop();if(sym.empty()){cout<<"輸入錯(cuò)誤：括號匹配有誤 "<<endl;return false;}tem=sym.top();}sym.pop();break;}default :{cout<<"輸入錯(cuò)誤：未知符號 "<<endl;return false ;}}++it;}if(!sym.empty()){to=to+"" ;tem=sym.top();while(!sym.empty()){if(tem=='(' ){cout<<"輸入錯(cuò)誤：括號匹配有誤 "<<endl;return false ;}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 (*it){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( '.' ,(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=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();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=numstac