数据结构课程设计-计算器.doc

数据结构课程设计报告 实验一：计算器设计要求1、问题描述：设计一个计算器，可以实现计算器的简单运算，输出并检验结果的正确性，以及检验运算表达式的正确性。2、输入：不含变量的数学表达式的中缀形式，可以接受的操作符包括+、-、*、/、%、(、)。具体事例如下：3、 输出：如果表达式正确，则输出表达式的正确结果；如果表达式非法，则输出错误信息。具体事例如下： 知识点：堆栈、队列实际输入输出情况：正确的表达式对负数的处理表达式括号不匹配表达式出现非法字符表达式中操作符位置错误求余操作符左右出现非整数其他输入错误数据结构与算法描述解决问题的整体思路：将用户输入的中缀表达式转换成后缀表达式，再利用转换后的后缀表达式进行计算得出结果。解决本问题所需要的数据结构与算法：用到的数据结构是堆栈。主要算法描述如下：A将中缀表达式转换为后缀表达式： 1. 将中缀表达式从头逐个字符扫描，在此过程中，遇到的字符有以下几种情况：1）数字2）小数点3）合法操作符+ - * / %4）左括号5）右括号6）非法字符2. 首先为操作符初始化一个map priority，用于保存各个操作符的优先级，其中+ -为0，* / %为13. 对于输入的字符串from和输出的字符串to，采用以下过程：初始化遍历器 std:string:iterator it=infix.begin()在当it!=from.end()，执行如下操作4. 遇到数字或小数点时将其加入到后缀表达式：case 1:case 2:case 3:case4:case 5:case 6:case7:case 8:case9:case 0:case .:to=to+*it;break;5. 遇到操作符（+，-，*，/，%）时，如果此时栈顶操作符的优先级比此时的操作符优先级低，则将其入栈，否则将栈中的操作符从栈顶逐个加入到后缀表达式，直到栈空或者遇到左括号，并将此时的操作符加入到栈中，在此过程中需判断表达式中是否出现输入错误：case +:case -:case *:case /:case %:if(it+1)=from.end()cout输入错误：运算符号右边缺少运算数endl;return false;if(*it=*|*it=/)&it=from.begin()cout输入错误：运算符号左边缺少运算数endl;return false;if(it+1)!=from.end()&(*(it+1)=+|*(it+1)=-|*(it+1)=*|*(it+1)=/|*(it+1)=%)cout输入错误：运算符号连续出现endl;return false;to=to+ ;if(sym.empty()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;6. 遇到“（”时，直接将其加入操作符栈，并且检测输入错误，并且当括号后的第一个符号为-时，说明用户试图输入负号，这种情况我们向目标表达式输出一个0，以达到处理负号的目的：case (:if(it+1)=from.end()cout输入错误：表达式以左括号结尾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输入错误：左括号右边不能为运算符号或右括号endl;return false;if(it!=from.begin()&(*(it-1)!=+&*(it-1)!=-&*(it-1)!=*&*(it-1)!=/&*(it-1)!=%&*(it-1)!=()cout输入错误：左括号左边不能为运算数或右括号endl;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)!=)cout输入错误：右括号右边不能为运算数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;B计算后缀表达式的主要思想：逐个字符的扫描后缀表达式，遇到单个数字或小数点时则先将其将其存到一个字符串中，当遇到后缀表达式中的分隔符（这里使用空格）时，则将这个字符串转化为数字放到堆栈numstack中；case 1:case 2:case 3:case4:case 5:case 6:case7:case 8:case9:case 0:case .:numtemp+=*it;break;case :if(numtemp!=)if(numtemp.find(.)&numtemp.find(.,(numtemp.find(.)+1)!=string:npos)cout输入错误：小数点数目超出：+numtempd;numstack.push(d);numtemp=;strm.str();strm.clear();break;break;2.遇到操作符+，-，*，/，%时，将堆栈numstack中的栈顶的两个数取出来，进行相应操作的运算，并将结果加入到堆栈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输入错误：除数不能为0endl;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;elsecerr输入错误：求模操作只能作用于整数endl;return false;3.直到后缀表达式扫描完并且堆栈numstack中只有一个数值，则此数值为计算的最终结果，否则说明输入有误。分析与探讨：1、测试结果分析：测试结果见本篇开始的实际输入输出结果。该计算器几乎实现了所有相关功能，包括简单计算、负数小数处理，容错，并且健壮性好，对于错误的表达式可以给出适当提示，不会导致程序崩溃。2、算法分析 1、对于中缀表达式转换成后缀表达式： 时间复杂性为O(n) 2、对于后缀表达式的计算：时间复杂性为O(n)综上，该程序算法的时间复杂度为O(n)3、算法改进 该程序存在的主要问题是命令行式的用户界面不够友好。Windows下的用户图形界面需要MFC方面的知识，因为时间关系没有进行这方面的深入学习。附录：源代码文件一.ExpressionHandler.h#include#include#include#include#includeusing namespace std;class ExpressionHandlerpublic:ExpressionHandler(string exp)this-exp=exp;bool infixtoprofix(string& exp);bool doprofix(string profix,double &result);private:string exp;文件二.ExpressionHandler.cpp/Coded By CS_Zhanglin#includeExpressionHandler.hbool ExpressionHandler:infixtoprofix(string& exp)string from=this-exp;string to=;stack sym;map pri;char tem;pri+=1;pri-=1;pri*=2;pri/=2;pri%=2;string:iterator it=from.begin();if(*it=+|*it=-)to+=0;while(it!=from.end()/cout1endl;switch(*it)case 1:case 2:case 3:case4:case 5:case 6:case7:case 8:case9:case 0:case .:to=to+*it;break;case +:case -:case *:case /:case %:if(it+1)=from.end()cout输入错误：运算符号右边缺少运算数endl;return false;if(*it=*|*it=/)&it=from.begin()cout输入错误：运算符号左边缺少运算数endl;return false;if(it+1)!=from.end()&(*(it+1)=+|*(it+1)=-|*(it+1)=*|*(it+1)=/|*(it+1)=%)cout输入错误：运算符号连续出现endl;return false;to=to+ ;if(sym.empty()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输入错误：表达式以左括号结尾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输入错误：左括号右边不能为运算符号或右括号endl;return false;if(it!=from.begin()&(*(it-1)!=+&*(it-1)!=-&*(it-1)!=*&*(it-1)!=/&*(it-1)!=%&*(it-1)!=()cout输入错误：左括号左边不能为运算数或右括号endl;return false;sym.push(*it);break;case ):if(it+1)!=from.end()&*(it+1)!=+&*(it+1)!=-&*(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)=%)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 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:case4:case 5:case 6:case7:case 8:case9:case 0:case .:numtemp+=*it;break;case :if(numtemp!=)if(numtemp.find(.)&numtemp.find(.,(numtemp.find(.)+1)!=string:npos)cout输入错误：小数点数目超出：+numtempd;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输入错误：除数不能为0endl;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;elsecerr输入错误：求模操作只能作用于整数endl;return false;if(numtemp!=)if(numtemp.find(.)&numtemp.find(.,(numtemp.find(.)+1)!=string:npos)cout输入错误：小数点数目超出：+numtempd;numstack.push(d);if(numstack.empty()cout输入错误：表达式中没有合法运算数endl;return false;result=numstack.top();return true;文件三. Main.cpp#include ExpressionHandler.hint main()string str;double r;cout请输入一个含有加、减、乘、除或求模运算的表达式，中间不能有空格str;cout运算结果：endl;ExpressionHandler eh(str);string result;if(eh.infixtoprofix(result)if(eh.doprofix(result,r)coutrendl;else cout程序终止endl;else cout程序终止endl;system(pause);