模拟计算器程序-课程设计报告书

..模拟计算器学生__****指导****摘要本课程设计的课题是设计一个模拟计算器的程序,能够进行表达式的计算,并且表达式中可以包含Abs<>和Sqrt<>运算。在课程设计中,系统开发平台为Windows,程序设计设计语言采用C++,程序运行平台为Windows或*nix。本程序的关键就是表达式的分离和处理,在程序设计中,采用了将输入的中缀表达式转化为后缀表达式的方法,具有可靠的运行效率。本程序做到了对输入的表达式〔表达式可以包含浮点数并且Abs<>和Sqrt<>中可以嵌套子表达式进行判定表达式是否合法并且求出表达式的值的功能。经过一系列的调试运行,程序实现了设计目标,可以正确的处理用户输入的表达式,对海量级数据都能够通过计算机运算快速解决。关键词C++程序设计；数据结构；表达式运算；栈；中缀表达式；后缀表达式；字符串处理；表达式合法判定；目录TOC\o"1-3"\h\u271421引言275631.1课程设计目的3243881.2课程设计内容31752设计思路与方案3139113详细实现478293.1表达式的合法判定452423.2中缀表达式转化为后缀表达式5190663.3处理后缀表达式736003.4表达式嵌套处理892134运行环境与结果8194174.1运行环境8133884.2运行结果8174175结束语1115872参考文献121861附录1：模拟计算器源程序清单 141引言本课程设计主要解决的是传统计算器中,不能对表达式进行运算的问题,通过制作该计算器模拟程序,可以做到快速的求解表达式的值,并且能够判定用户输入的表达式是否合法。该模拟计算器的核心部分就在用户输入的中缀表达式的转化,程序中用到了"栈"的后进先出的基本性质。利用两个"栈",一个"数据栈",一个"运算符栈"来把中缀表达式转换成后缀表达式。最后利用后缀表达式来求解表达式的值。该算法的复杂度为O<n>,能够高效、快速地求解表达式的值,提高用户的效率。1.1课程设计目的数据结构主要是研究计算机存储,组织数据,非数值计算程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程,它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础,广泛的应用于信息学、系统工程等各种领域。学习数据结构是为了将实际问题中涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力,促进学生的综合应用能力和专业素质的提高。模拟计算器程序主要利用了"栈"这种数据结构来把中缀表达式转化为后缀表达式,并且运用了递归的思想来解决Abs<>和Sqrt<>中嵌套表达式的问题,其中还有一些统计的思想来判定表达式是否合法的算法。1.2课程设计内容本次课程设计为计算器模拟程序,主要解决表达式计算的问题,实现分别按表达式处理的过程分解为几个子过程,详细的求解过程如下：1用户输入表达式。2判定表达式是否合法。3把中缀表达式转化为后缀表达式。4求出后缀表达式的结果。5输出表达式的结果。通过设计该程序,从而做到方便的求出一个表达式的值,而不需要一步一步进行运算。2设计思路与方案本课程设计需要考虑许多的问题,首先是表达式的合法判断,然后是字符串表达式提取分离的问题,核心部分就是中缀表达式转化为后缀表达式。对于第一个问题,我是分步来判断,首先表达式中是否含有其它非法字符,然后判断括号是否合法,接着判断运算法两边是否合法,比如除法时,除数不能为零。对于第二个问题,我是直接转换的,从左到右遍历中缀表达式,把数据全部取出来。对于核心问题,利用了"栈"这种"后进先出"的数据结构,利用两个"栈",一个"数据栈",一个"运算符栈"来把中缀表达式转换成后缀表达式。最后利用后缀表达式来求解表达式的值。上面是数据处理的算法部分。本程序用户界面总共分为3个模块,分别是操作提示,数据输入,数据输出。如图2.1所示。图2.1用户界面除了实现基本的功能外,我还增加了其它一些功能,比如支持输入数据为浮点数,更重要的是本程序还支持表达式的嵌套运算,例如：A<1+2*S<2>>我的实现方法是利用函数的递归调用来解决此问题,即把1+2*S<2>看成一个子表达式,这个子表达式中2也看成子表达式。这样使得程序的适用范围更加的广泛,适应性更强,能支持更复杂的表达式的运算。这也是本程序的优点之一。3详细实现3.1表达式的合法判定表达式的合法判定过程如图3.1所示是否存在其它字符括号是否合法是否存在其它字符括号是否合法运算符是否合法图3.1表达式的合法判定过程首先是其它字符的判定,从左到右遍历中缀表达式,看是否存在其它非法的。然后是判定括号是否的匹配是否和合法,首先把"<"对应为1,相应的">"对应为-1。从左到右遍历表达式,如果遇到括号就加上其对应的值,用sum来保存其累加值。如果在中途出现sum小于零的情况,即出现">"那么的情况,即非法。在遍历的最后,还要判断sum的值是否为零,如果为零就是合法,否则就是非法。代码如下：for<i=0;i<s.length<>;i++>{//检验括号是否合法,以及是否存在非法字符if<!IsNum<s[i]>&&!IsSign<s[i]>&&s[i]!='<'&&s[i]!='>'&&s[i]!='A'&&s[i]!='S'&&s[i]!='.'>returnfalse;if<s[i]=='<'>sum+=1;elseif<s[i]=='>'>sum-=1;if<sum<0>returnfalse;//括号匹配不合法}运算符判断是否合法,也是遍历一遍表达式,遇到"/",看其后面的除数是否为零。这里要考虑表达式中出现负数的情况,因此特殊考虑"-"号,判断它的前面是"<"还是没有字符了,那么就是负数。3.2中缀表达式转化为后缀表达式中缀表达式转化为后缀表达式,利用两个"栈",一个"数据栈",一个"运算符栈"来把中缀表达式转换成后缀表达式。最后利用后缀表达式来求解表达式的值。设一个stack存后缀数据,一个rout栈存运算符。算法流程如下：〔1从右向左依次取得数据ch。〔2如果ch是操作数,直接加进stack中。〔3如果ch是运算符〔含左右括号,则：a：如果ch='<',放入堆栈rout中。b：如果ch='>',依次输出堆栈rout中的运算符,直到遇到'<'为止。c：如果ch不是'>'或者'<',那么就和堆栈rout顶点位置的运算符top做优先级比较。1：如果ch优先级比rtop高,那么将ch放入堆栈rout。2：如果ch优先级低于或者等于rtop,那么输出top到stack中〔直到！top或者满足1,然后将ch放入堆栈rout。可以看出算法复杂度是O<n的,因此效率是比较高的,能够在1s内处理百万级别长度的表达式。算法的主要思想是利用"栈"的后进先出的特性,以及运算符的优先级,这里我们定义运算符的优先级；代码如下：intGetKey<charc>{//定义运算符的关键字intkey;switch<c>{case'+':key=1;break;case'-':key=1;break;case'*':key=2;break;case'/':key=2;break;case'<':key=4;break;case'>':key=5;break;}returnkey;}中缀转化为后缀处理的核心代码如下：/*双栈,sta1存放后缀表达式,sta2存放运算符符号*/stack<pair<double,int>>sta1,sta2;for<i=0;i<k;i++>{if<!num[i].second>sta1.push<num[i]>;//为数据,直接放入sta1elseif<num[i].second==4>sta2.push<num[i]>;//为'<',直接放入sta2/*为'>',从sta2中取出运算符,push到sta1中,直到遇到'>'*/elseif<num[i].second==5>{while<sta2.top<>.second!=4>{sta1.push<sta2.top<>>;sta2.pop<>;}sta2.pop<>;//取出'<'括号}/*为'+','-','*'或者'/'运算符,取出sta2中的运算符,push到sta1中,直到比sta2栈顶中的优先级大*/else{while<!sta2.empty<>&&sta2.top<>.second>=num[i].second&&sta2.top<>.second!=4>{sta1.push<sta2.top<>>;sta2.pop<>;}sta2.push<num[i]>;//放入当前运算符}}最后,后缀表达式就存放在sta1栈中,把sta1栈中的结果存放到SufExp中就得到了后缀表达式。3.3处理后缀表达式这里也是运用"栈"来处理,运用栈模板在求值过程顺序扫描后缀表达式,每次遇到操作数便将它压入堆栈；遇到运算符,则从栈中弹出两个操作数进行计算,然后再把结果压入堆栈,等到扫描结束时,则表达式的结果就求出来了。算法流程如图3.3所示：后缀表达式扫描并判定数据类型从栈中取出数字进行运算数字压入栈中栈结果压入栈中输出最终结果图3.3处理后缀表达式流程核心代码如下：doubleExpression::GetAns<>{inti;doubletemp,num1,num2;//num1和num2为运算符两遍的操作数stack<double>sta;//数据栈for<i=0;i<Size;i++>{if<!SufExp[i].second>{//为数据sta.push<SufExp[i].first>;}else{//为运算符num1=sta.top<>;//取出第一个操作数sta.pop<>;num2=sta.top<>;//取出第二个操作数sta.pop<>;temp=Cal<<char>SufExp[i].first,num2,num1>;sta.push<temp>;//放入操作数结果}}Ans=sta.top<>;returnAns;//返回最终结果}3.4表达式嵌套处理如果遇到A<>和S<>中含有表达式,而不是单纯的数字,例如A<1.1+3.4*S<2.5>>,那么就需要对其字表达式"1.1+3.4*S<2.5>"进行递归处理,这个子表达式中还含有子表达式"2.5",然后再递归处理,依次类推下去。其核心代码如下：if<s[i]=='A'||s[i]=='S'>{//遇到Abs<>或者Sqrt<>递归处理子表达式Expressiontemp;//创建子表达式temp.Init<>;for<j=0;i+j+2<Pos[i+1];j++>//复制表达式st[j]=s[i+j+2];st[j]=0;temp.s=st;//复制表达式temp.SloveExp<>;//得到子表达式的值num[k].first=<s[i]=='A'?fabs<temp.Ans>:sqrt<temp.Ans>>;num[k].second=0;//标记为数据if<s[i-1]=='-'&&<i-1==0||s[i-2]=='<'>>num[k].first=-num[k].first;k++,i=Pos[i+1];}4运行环境与结果4.1运行环境运行环境：WindowsXP/Windows7/LinuxUbuntu13.044.2运行结果表达式中含非法字符判断如图4.1所示：图4.1非法字符判断表达式中非法括号匹配判断如图4.2所示：图4.2非法括号匹配判断表达式中运算符判断如图4.3所示：图4.3运算符判断表达式中有浮点数如图4.4所示：图4.4表达式中有浮点数A<>运算符中嵌套表达式如图4.5所示：图4.5A<>运算符中嵌套表达式S<>运算符中嵌套表达式如图4.6所示：图4.6S<>运算符中嵌套表达式复杂的表达式运算如图4.7所示：图4.7复杂的表达式运算5结束语通过两周的课程设计,我学会了如何写一个精简、快速、健壮的程序。一个好的程序应该是一个所占空间小、运行时间短、其他性能也好的程序。而要做出一个好的程序则应该通过对算法与其数据结构的时间复杂度和空间复杂度进行实现与改进。然而,实际上很难做到十全十美,原因是各要求有时相互抵触,要节约算法的执行时间往往要以牺牲更多的存储空间为代价：而为了节省存储空间又可能要以更多的时间为代价。因此,只能根据具体情况有所侧重：如果程序的使用次数较少,则应该力求算法简明易懂,而易于转换为上机程序；如果程序反复多次使用,则应该尽可能选用快速算法；如果解决问题的数据量极大,机器的内存空间较小,则在编写算法时应该考虑如何节省空间。本次课程设计培养了了我们独立思考的能力,提高了我们的动手操作水平。在具体设计操作中,我们巩固了本学期所学的数据结构与算法的理论知识,进一步提高了自己的编程能力。这也是课程设计的最终目的所在。通过实际操作,开发了自己的逻辑思维能力,培养了分析问题、解决问题的能力。但在程序设计的过程中我也深刻的感受到自己实力的不足,无法灵活的运用各种工具和函数,对于课程所讲的东西也无法在脱离课本的情况中完成,我意识到自己在今后的学习生活中,一定要勤于思考,扎实掌握理论知识,灵活运用课上所学的东西,做一个优秀的程序员。参考文献[1]ThomasH.Cormen,CharlesE.Leiserson,RonaldL.Rivest.北京.算法导论<第三版>[M].机械工业出版社:ThomasH.Cormen,2013[2]刘汝佳,黄亮.北京.清华大学出版社.算法艺术与信息学竞赛.[3]王晓东.北京.清华大学出版社.算法设计与分析〔第二版.附录1：模拟计算器源程序清单//程序名称：Calculator.cpp//程序功能：模拟计算器//程序****//学号:****//最后修改日期：2013-7-5/*课题4：设计一个模拟计算器的程序,要求能对包含加、减、乘、除、括号运算符及SQR和ABS函数的任意整型表达式进行求解。要求：要检查有关运算的条件,并对错误的条件产生报警。我的代码在此基础上增加了几个功能：不仅支持整数运算,还支持浮点数运算可支持表达式的嵌套,Ex：A<1+2*S<3>*/#include<iostream>#include<cstdlib>#include<cstring>#include<string>#include<cstdio>#include<stack>#include<cmath>usingnamespacestd;#definemem<a,b>memset<a,b,sizeof<a>>constintMaxLength=1010;//数组的最大存储空间boolIsNum<charc>//判断是否是数字{if<c>='0'&&c<='9'>returntrue;returnfalse;}boolIsSign<charc>//判断是否是运算符号{if<c=='+'||c=='-'||c=='*'||c=='/'>returntrue;returnfalse;}intGetKey<charc>//定义运算符的关键字{intkey;switch<c>{case'+':key=1;break;case'-':key=1;break;case'*':key=2;break;case'/':key=2;break;case'<':key=4;break;case'>':key=5;break;}returnkey;}doubleCal<charc,doublea,doubleb>//根据运算符来计算运算结果{switch<c>{case'+':returna+b;case'-':returna-b;case'*':returna*b;case'/':returna/b;}return0;}classGraph//图形界面类{public:voidWindow<>;//图形窗口函数};voidGraph::Window<>{cout<<"|===============欢迎使用本计算器===============|"<<endl;cout<<"|1.本计算器支持表达式计算,输入数据为实数|"<<endl;cout<<"|2.可支持表达式的嵌套,Ex:A<1+2*S<3>>|"<<endl;cout<<"||"<<endl;cout<<"|789+/|"<<endl;cout<<"|456-A<abs>|"<<endl;cout<<"|123*S<sqrt>|"<<endl;cout<<"||"<<endl;}classExpression{public:voidInput<>;//表达式输入voidInit<>;//表达式数据初始化boolSloveExp<>;//表达式处理过程boolCheckExp<>;//检查表达式是否合法voidGetSuffix<>;//得到后缀表达式doubleGetAns<>;//根据后缀表达式来得到结果voidDisplay<>;//输出表达式结果private:intSize;//后缀表达式的长度strings;//表达式存储boolHaveAns;//表达式是否有结果doubleAns;//表达式结果pair<double,int>SufExp[MaxLength];//后缀表达式存储intPos[MaxLength];//中缀表达式中'<'对应的'>'数组下标位置};voidExpression::Input<>//表达式输入{cout<<"请输入您的表达式:";cin>>s;}voidExpression::Init<>//表达式数据初始化{HaveAns=false;mem<Pos,-1>;}boolExpression::SloveExp<>{if<<HaveAns=CheckExp<>>==0>returnHaveAns=false;//表达式不合法,退出GetSuffix<>;//得到后缀表达式GetAns<>;//根据后缀表达式来得到结果returntrue;}boolExpression::CheckExp<>//检查表达式是否合法{inti,j,cnt;intsum=0;for<i=0;i<s.length<>;i++>{//检验括号是否合法,以及是否存在非法字符if<!IsNum<s[i]>&&!IsSign<s[i]>&&s[i]!='<'&&s[i]!='>'&&s[i]!='A'&&s[i]!='S'&&s[i]!='.'>returnfalse;if<s[i]=='<'>sum+=1;elseif<s[i]=='>'>sum-=1;if<sum<0>returnfalse;//括号匹配不合法}if<sum!=0>returnfalse;for<i=0;i<s.length<>;i++>{if<IsSign<s[i]>>{if<s[i]=='/'&&s[i+1]=='0'>//判断除法的被除数是不是为零returnfalse;}}for<i=0;i<s.length<>;i++>{//括号匹配,获取'<'对应的'>'的下标if<s[i]!='>'>continue;for<j=i;j>=0;j-->{//遇到'>'括号if<s[j]=='>'>sum+=1;elseif<s[j]=='<'>sum-=1;if<sum==0>{//如果sum的值为0,那么找到'>'的匹配括号Pos[j]=i;break;}}}returntrue;//表达式正确}voidExpression::GetSuffix<>//得到后缀表达式{inti,j,w,k=0;charst[MaxLength];pair<double,int>num[MaxLength];//保存后缀表达式,double为数据,int标记符号for<i=0;i<s.length<>;i++>{if<s[i]=='A'||s[i]=='S'>{//遇到Abs<>或者Sqrt<>递归处理子表达式Expressiontemp;//创建子表达式temp.Init<>;for<j=0;i+j+2<Pos[i+1];j++>{//复制表达式st[j]=s[i+j+2];}st[j]=0;temp.s=st;//复制表达式temp.SloveExp<>;//得到子表达式的值num[k].first=<s[i]=='A'?fabs<temp.Ans>:sqrt<temp.Ans>>;num[k].second=0;//标记为数据if<s[i-1]=='-'&&<i-1==0||s[i-2]=='<'>>num[k].first=-num[k].first;k++;i=Pos[i+1];}elseif<IsNum<s[i]>>{//处理数据doublesum=0;intok=0,w=1;/*把数据提取出来*/for<j=i;j<s.length<>&&<IsNum<s[j]>||s[j]=='.'>;j++>{if<s[j]!='.'>sum=sum*10+<double><s[j]-'0'>;elseok=1,w=0;if<ok>w++;//小数点位数统计}num[k].first=sum/pow<10.0,<double><w-1>>;//处理浮点数num[k].second=0;if<s[i-1]=='-'&&<i-1==0||s[i-2]=='<'>>num[k].first=-num[k].first;k++;i=j-1;}else{//为符号,直接存入,特殊考虑负数if<s[i]=='-'&&<i==0||s[i-1]=='<'>>continue;num[k].first=<double>s[i];num[k++].second=GetKey<s[i]>;}}/*双栈,sta1存放后缀表达式,sta2存放运算符符号*/stack<pair<double,int>>sta1,sta2;for<i=0;i<k;i++>{if<!num[i].second>{//为数据,直接放入sta1sta1.push<num[i]>;}elseif<num[i].second==4>{//为'<',直接放入sta2sta2.push<num[i]>;}elseif<num[i].second==5>{//为'>',从sta2中取出运算符,push到sta1中,直到遇到'>'while<sta2.top<>.second!=4>{sta1.push<sta2.top<>>;sta2.pop<>;}sta2.pop<>;//取出'<'括号}/*为'+','-','*'或者'/'运算符,取出sta2中的运算符,push到sta1中,直到比sta2栈顶中的优先级大*/else{while<!sta2.empty<>&&sta2.top<>.second>=num[i].second&&sta2.top<>.second!=4>{sta1.push<sta2.top<>>;sta2.pop<>;}sta2.push