數(shù)據結構課程設計-計算器

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

case:case'9'{

'1':case:case '0'

'2':case

:case'.':

'3'

:case'4'

:case

'5'

:case

'6'

:case'7'

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

'+'

||*(it+1)==

'-'

||*(it+1)==

'*'

||*(it+1)==

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

"輸入錯誤：運算符號連續(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;}遇到“（”時，直接將其加入操作符棧，并且檢測輸入錯誤，并且當括號后的第一個符號為 -時，說明用戶試圖輸入負號，這種情況我們向目標表達式輸出一個 0，以達到處理負號的目的：case '(' :{if((it+1)==from.end()){cout<<"輸入錯誤：表達式以左括號結尾 "<<endl;returnfalse;}//若以+或者-開頭，則按照正負號看待，向目標表達式中加入一個0if(*(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)!= '+' &&*(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)!=+1)!='%'&&*(it+1)!= ')' )

'+'

&&*(it+1)!=

'-'

&&*(it+1)!=

'*'

&&*(it+1)!=

'/'

&&*(it{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.empty()){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;}．計算后綴表達式的主要思想：逐個字符的掃描后綴表達式， 遇到單個數(shù)字或小數(shù)點時則先將其將其存到一個字符串中，當遇到后綴表達式中的分隔符（這里使用空格）時，則將這個字符串轉化為數(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<<"輸入錯誤：小數(shù)點數(shù)目超出： "+numtemp<<endl;return false;}strm.str(numtemp);strm>>d;numstack.push(d);numtemp="";strm.str( "");strm.clear();break;}break;}遇到操作符+，-，*，/，%時，將堆棧numstack中的棧頂?shù)膬蓚€數(shù)取出來，進行相應操作的運算，并將結果加入到堆棧 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<<"輸入錯誤：除數(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<<"輸入錯誤：求模操作只能作用于整數(shù) "<<endl;return false ;}}3.直到后綴表達式掃描完并且堆棧 numstack 中只有一個數(shù)值，則此數(shù)值為計算的最終結果，否則說明輸入有誤 。分析與探討：1、測試結果分析：測試結果見本篇開始的實際輸入輸出結果。該計算器幾乎實現(xiàn)了所有相關功能，包括簡單計算、負數(shù)小數(shù)處理，容錯，并且健壯性好，對于錯誤的表達式可以給出適當提示，不會導致程序崩潰。2、算法分析1、對于中綴表達式轉換成后綴表達式： 時間復雜性為O(n)2、對于后綴表達式的計算：時間復雜性為 O(n)綜上，該程序算法的時間復雜度為 O(n)3、算法改進該程序存在的主要問題是命令行式的用戶界面不夠友好。Windows 下的用戶圖形界面需要 MFC方面的知識，因為時間關系沒有進行這方面的深入學習。附錄：源代碼文件一.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<<"輸入錯誤：運算符號右邊缺少運算數(shù) "<<endl;return false ;}if((*it== '*' ||*it== '/' )&&it==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.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<<"輸入錯誤：表達式以左括號結尾 "<<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<<"輸入錯誤：左括號右邊不能為運算符號或右括號return false ;

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

'+'

&&*(it-1)!=

'-'

&&*(it-1)!=

'*'

&&*(it-1)!=

'/'

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