數(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ì)算器的簡(jiǎn)單運(yùn)算，輸出并檢驗(yàn)結(jié)果的正確性，以及檢驗(yàn)運(yùn)算表達(dá)式的正確性。2、輸入：不含變量的數(shù)學(xué)表達(dá)式的中綴形式，可以接受的操作符包括+、-、*、/、%、(、)。具體事例如下：輸出：如果表達(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)換后的后綴表達(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::iteratorit=infix.begin()

在當(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í)低，則將其入棧，否則將棧中的操作符從棧頂逐個(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; returnfalse; } if((*it=='*'||*it=='/')&&it==from.begin()) { cout<<"輸入錯(cuò)誤：運(yùn)算符號(hào)左邊缺少運(yùn)算數(shù)"<<endl; returnfalse; } 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; 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.遇到“（”時(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.end()) { cout<<"輸入錯(cuò)誤：表達(dá)式以左括號(hào)結(jié)尾"<<endl; returnfalse; }//若以+或者-開頭，則按照正負(fù)號(hào)看待，向目標(biāo)表達(dá)式中加入一個(gè)0 if(*(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; returnfalse; } 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; returnfalse; } 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)!=')') { cout<<"輸入錯(cuò)誤：右括號(hào)右邊不能為運(yùn)算數(shù)"<<endl; returnfalse; } if(it!=from.begin()&&(*(it-1)=='+'||*(it-1)=='-'||*(it-1)=='*'||*(it-1)=='/'||*(it-1)=='%')) { cout<<"輸入錯(cuò)誤：右括號(hào)左邊不能為運(yùn)算符號(hào)"<<endl; returnfalse; } to=to+""; if(sym.empty()) { cout<<"輸入錯(cuò)誤：表達(dá)式以右括號(hào)開始"<<endl; returnfalse; } tem=sym.top(); while(tem!='(') { to=to+tem+""; sym.pop(); if(sym.empty()) { cout<<"輸入錯(cuò)誤：括號(hào)匹配有誤"<<endl; returnfalse; } tem=sym.top(); } sym.pop(); break; }B．計(jì)算后綴表達(dá)式的主要思想：逐個(gè)字符的掃描后綴表達(dá)式，遇到單個(gè)數(shù)字或小數(shù)點(diǎn)時(shí)則先將其將其存到一個(gè)字符串中，當(dāng)遇到后綴表達(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.find('.')&&numtemp.find('.',(numtemp.find('.')+1))!=string::npos) { cout<<"輸入錯(cuò)誤：小數(shù)點(diǎn)數(shù)目超出："+numtemp<<endl; returnfalse; } strm.str(numtemp); strm>>d; numstack.push(d); numtemp=""; strm.str(""); strm.clear(); break; } break; }2.遇到操作符+，-，*，/，%時(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; 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<<"輸入錯(cuò)誤：求模操作只能作用于整數(shù)"<<endl; returnfalse; } } 3.直到后綴表達(dá)式掃描完并且堆棧numstack中只有一個(gè)數(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í)。附錄：源代碼文件一.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<<"輸入錯(cuò)誤：運(yùn)算符號(hào)右邊缺少運(yùn)算數(shù)"<<endl; returnfalse; } if((*it=='*'||*it=='/')&&it==from.begin()) { cout<<"輸入錯(cuò)誤：運(yùn)算符號(hào)左邊缺少運(yùn)算數(shù)"<<endl; returnfalse; } 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; 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<<"輸入錯(cuò)誤：表達(dá)式以左括號(hào)結(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<<"輸入錯(cuò)誤：左括號(hào)右邊不能為運(yùn)算符號(hào)或右括號(hào)"<<endl; returnfalse; } 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; returnfalse; } sym.push(*it); break; } case')': { if((it+1)!=from.end()&&*(it+1)!='+'&&*(it+1)!='-'&&*(it+1)!='*'&&*(it+1)!='/'&&*(it+1)!='%'&&*(it+1)!=')') { cout<<"輸入錯(cuò)誤：右括號(hào)右邊不能為運(yùn)算數(shù)"<<endl; returnfalse; } if(it!=from.begin()&&(*(it-1)=='+'||*(it-1)=='-'||*(it-1)=='*'||*(it-1)=='/'||*(it-1)=='%')) { cout<<"輸入錯(cuò)誤：右括號(hào)左邊不能為運(yùn)算符號(hào)"<<endl; returnfalse; } to=to+""; if(sym.empty()) { cout<<"輸入錯(cuò)誤：表達(dá)式以右括號(hào)開始"<<endl; returnfalse; } tem=sym.top(); while(tem!='(') { to=to+tem+""; sym.pop(); if(sym.empty()) { cout<<"輸入錯(cuò)誤：括號(hào)匹配有誤"<<endl; returnfalse; } tem=sym.top(); } sym.pop(); break; } default: { cout<<"輸入錯(cuò)誤：未知符號(hào)"<<endl; returnfalse; } } ++it; } if(!sym.empty()) { to=to+""; tem=sym.top(); while(!sym.empty()) { if(tem=='(') { cout<<"輸入錯(cuò)誤：括號(hào)匹配有誤"<<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<<"輸入錯(cuò)誤：小數(shù)點(diǎn)數(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<<"輸入錯(cuò)誤：除數(shù)不能為0"<<endl; returnfalse; } d1=numstack.top(); numstack.pop(); numstack.push(d1/d2); break; } case'