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

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

在當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)先級低，則將其入棧，否則將棧中的操作符從棧頂逐個加入到后綴表達式，直到?？栈蛘哂龅阶罄ㄌ?，并將此時的操作符加入到棧中，在此過程中需判斷表達式中是否出現(xiàn)輸入錯誤：case'+':case'-':case'*':case'/':case'%': { if((it+1)==from.end()) { cout<<"輸入錯誤：運算符號右邊缺少運算數(shù)"<<endl; returnfalse; } if((*it=='*'||*it=='/')&&it==from.begin()) { cout<<"輸入錯誤：運算符號左邊缺少運算數(shù)"<<endl; returnfalse; } if((it+1)!=from.end()&&(*(it+1)=='+'||*(it+1)=='-'||*(it+1)=='*'||*(it+1)=='/'||*(it+1)=='%')) { cout<<"輸入錯誤：運算符號連續(xù)出現(xiàn)"<<endl; returnfalse; } 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; }6.遇到“（”時，直接將其加入操作符棧，并且檢測輸入錯誤，并且當括號后的第一個符號為-時，說明用戶試圖輸入負號，這種情況我們向目標表達式輸出一個0，以達到處理負號的目的：case'(': { if((it+1)==from.end()) { cout<<"輸入錯誤：表達式以左括號結(jié)尾"<<endl; returnfalse; }//若以+或者-開頭，則按照正負號看待，向目標表達式中加入一個0 if(*(it+1)=='-'||*(it+1)=='+') { to=to+'0'; } if((it+1)!=from.end()&&((*(it+1)=='*'||*(it+1)=='/'||*(it+1)=='%'||*(it+1)==')'))) { cout<<"輸入錯誤：左括號右邊不能為運算符號或右括號"<<endl; returnfalse; } if(it!=from.begin()&&(*(it-1)!='+'&&*(it-1)!='-'&&*(it-1)!='*'&&*(it-1)!='/'&&*(it-1)!='%'&&*(it-1)!='(')) { cout<<"輸入錯誤：左括號左邊不能為運算數(shù)或右括號"<<endl; returnfalse; } sym.push(*it); break; }5.遇到“）”時，將棧中的操作符從棧頂逐個彈出并放入后綴表達式中，直到在棧中遇到“（”，并將“（”從棧中彈出：case')': { if((it+1)!=from.end()&&*(it+1)!='+'&&*(it+1)!='-'&&*(it+1)!='*'&&*(it+1)!='/'&&*(it+1)!='%'&&*(it+1)!=')') { cout<<"輸入錯誤：右括號右邊不能為運算數(shù)"<<endl; returnfalse; } if(it!=from.begin()&&(*(it-1)=='+'||*(it-1)=='-'||*(it-1)=='*'||*(it-1)=='/'||*(it-1)=='%')) { cout<<"輸入錯誤：右括號左邊不能為運算符號"<<endl; returnfalse; } to=to+""; if(sym.empty()) { cout<<"輸入錯誤：表達式以右括號開始"<<endl; returnfalse; } tem=sym.top(); while(tem!='(') { to=to+tem+""; sym.pop(); if(sym.empty()) { cout<<"輸入錯誤：括號匹配有誤"<<endl; returnfalse; } tem=sym.top(); } sym.pop(); break; }B．計算后綴表達式的主要思想：逐個字符的掃描后綴表達式，遇到單個數(shù)字或小數(shù)點時則先將其將其存到一個字符串中，當遇到后綴表達式中的分隔符（這里使用空格）時，則將這個字符串轉(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.find('.')&&numtemp.find('.',(numtemp.find('.')+1))!=string::npos) { cout<<"輸入錯誤：小數(shù)點數(shù)目超出："+numtemp<<endl; returnfalse; } strm.str(numtemp); strm>>d; numstack.push(d); numtemp=""; strm.str(""); strm.clear(); break; } break; }2.遇到操作符+，-，*，/，%時，將堆棧numstack中的棧頂?shù)膬蓚€數(shù)取出來，進行相應操作的運算，并將結(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<<"輸入錯誤：除數(shù)不能為0"<<endl; returnfalse; } 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) { intn1=(int)d1; intn2=(int)d2; numstack.push((double)(n1%n2)); break; } else { cerr<<"輸入錯誤：求模操作只能作用于整數(shù)"<<endl; returnfalse; } } 3.直到后綴表達式掃描完并且堆棧numstack中只有一個數(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)系沒有進行這方面的深入學習。附錄：源代碼文件一.ExpressionHandler.h#include<string>#include<map>#include<stack>#include<iostream>#include<sstream>usingnamespacestd;classExpressionHandler{public: ExpressionHandler(stringexp){ this->exp=exp; } boolinfixtoprofix(string&exp); booldoprofix(stringprofix,double&result);private: stringexp;};文件二.ExpressionHandler.cpp//CodedByCS_Zhanglin#include"ExpressionHandler.h"boolExpressionHandler::infixtoprofix(string&exp){ stringfrom=this->exp; stringto=""; stack<char>sym; map<char,int>pri; chartem; pri['+']=1; pri['-']=1; pri['*']=2; pri['/']=2; pri['%']=2; string::iteratorit=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':case'8':case'9':case'0':case'.': { to=to+*it; break; } case'+':case'-':case'*':case'/':case'%': { if((it+1)==from.end()) { cout<<"輸入錯誤：運算符號右邊缺少運算數(shù)"<<endl; returnfalse; } if((*it=='*'||*it=='/')&&it==from.begin()) { cout<<"輸入錯誤：運算符號左邊缺少運算數(shù)"<<endl; returnfalse; } if((it+1)!=from.end()&&(*(it+1)=='+'||*(it+1)=='-'||*(it+1)=='*'||*(it+1)=='/'||*(it+1)=='%')) { cout<<"輸入錯誤：運算符號連續(xù)出現(xiàn)"<<endl; returnfalse; } 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<<"輸入錯誤：表達式以左括號結(jié)尾"<<endl; returnfalse; } if(*(it+1)=='-'||*(it+1)=='+') { to=to+'0'; } if((it+1)!=from.end()&&((*(it+1)=='*'||*(it+1)=='/'||*(it+1)=='%'||*(it+1)==')'))) { cout<<"輸入錯誤：左括號右邊不能為運算符號或右括號"<<endl; returnfalse; } if(it!=from.begin()&&(*(it-1)!='+'&&*(it-1)!='-'&&*(it-1)!='*'&&*(it-1)!='/'&&*(it-1)!='%'&&*(it-1)!='(')) { cout<<"輸入錯誤：左括號左邊不能為運算數(shù)或右括號"<<endl; returnfalse; } sym.push(*it); break; } case')': { if((it+1)!=from.end()&&*(it+1)!='+'&&*(it+1)!='-'&&*(it+1)!='*'&&*(it+1)!='/'&&*(it+1)!='%'&&*(it+1)!=')') { cout<<"輸入錯誤：右括號右邊不能為運算數(shù)"<<endl; returnfalse; } if(it!=from.begin()&&(*(it-1)=='+'||*(it-1)=='-'||*(it-1)=='*'||*(it-1)=='/'||*(it-1)=='%')) { cout<<"輸入錯誤：右括號左邊不能為運算符號"<<endl; returnfalse; } to=to+""; if(sym.empty()) { cout<<"輸入錯誤：表達式以右括號開始"<<endl; returnfalse; } tem=sym.top(); while(tem!='(') { to=to+tem+""; sym.pop(); if(sym.empty()) { cout<<"輸入錯誤：括號匹配有誤"<<endl; returnfalse; } tem=sym.top(); } sym.pop(); break; } default: { cout<<"輸入錯誤：未知符號"<<endl; returnfalse; } } ++it; } if(!sym.empty()) { to=to+""; tem=sym.top(); while(!sym.empty()) { if(tem=='(') { cout<<"輸入錯誤：括號匹配有誤"<<endl; returnfalse; } to=to+tem+""; sym.pop(); if(sym.empty())break; tem=sym.top(); } } exp=to; returntrue;}boolExpressionHandler::doprofix(stringprofix,double&result){ stringnumtemp; stack<double>numstack; stringstreamstrm; doubled,d1,d2; for(string::iteratorit=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; returnfalse; } 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; returnfalse; } d1=numstack.top(); numstack.pop(); numstack.push(d1/d2); break; } case'