数据结构课程设计-模拟计算器程序

第1页共31页数据结构课程设计题目名称：模拟计算器程序计算机科学与技术学院课程设计任务书一、设计任务设计一个模拟计算器的程序二、设计要求1、要求对包含加、减、乘、除、括号运算符及SQR和ABS函数的任意整型表达式进行求解第2页共31页2、程序基本功能要求实现完整，并有简单的验证。3、设计报告要求格式规范，符合学校课程设计报告要求。4、报告中流程图要求描述规范，算法设计清楚正确。三、设计期限2018年3月5日到2018年3月30日前言利用本学期所学的《数据结构》课程，运用相关知识，查阅相关资料，编写C语言程序，设计一个简单计算器，要求编写的简单计算器能够模拟windows系统的计算器，用户能够用键盘输入相关数据，要求对包含加、减、乘、除、括号运算符及SQR和ABS函数的任意整型表达式进行求解，并且在程序运行过程中能够正常的退出程序。第3页共31页这个程序实际上就是对一个表达式进行计算。而一个算术表达式中包含各种运算符，每个运算符的等级可能会不同，这就成了本程序需要解决的一个主要的问题之一了。另外计算器中需要有各种数学函数，比如：abssqrtsincostan等，如何对这些函数进行处理，也是本程序能成功的一个关键。还有一个问题就是如何处理操作符和操作数之间的关系也是一个要点。例如：1+2*(3-2/1)，经过怎么样的变换和处理能得出结果５。数据的输入这里应该要用字符，然后通过字符和整形之间的关系进行转换即可，这样处理的话，就方便很多了。在计算器程序运行中，输入数据时如果遇到输入错误的情况，能够能过键盘上的退格键进行删除，并且重新输入正确的数据。在数据输入完成后，如果需要放弃本次计算操作，可以利用程序中设置好的按键进行清零，并为下一次运算作准备。本课程设计主要解决的是传统计算器中，不能对表达式进行运算的问题，通过制作该计算器模拟程序，可以做到快速的求解表达式的值，并且能够判定用户输入的表达式是否合法。该模拟计算器的核心部分就在用户输入的中缀表达式的转化，程序中用到了“栈”的后进先出的基本性质。目录第1章需求分析‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥51.1系统设计流程图‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥51.2主要功能表‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥6第4页共31页第2章总体设计‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥72.1数据结构的选择‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥72.2程序实现流程图‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥8第3章详细设计和编码‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥93.1表达式的判断‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥103.2栈的定义及存储‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥113.3表达式的嵌套处理‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥143.4中缀表达式转化为后缀表达式‥‥‥‥‥‥‥‥‥‥‥‥‥‥14第4章编码与调试‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥174.1系统测试‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥174.2调试‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥174.3错误原因分析‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥174.4调试结果‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥19第5章总结‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥21参考文献‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥22附录‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥23第1章需求分析1.1系统流程图本课程设计主要解决的是传统计算器中，不能对表达式进行运算的问题，通过制作该计算器模拟程序，可以做到快速的求解表达式的值，并且能够判定用户输入的表达式是否合法。该模拟计算器的核心部分就在用户输入的中缀表达式的转化，程序中用到了“栈”的第5页共31页后进先出的基本性质。利用两个“栈”，一个“数据栈”，一个“运算符栈”来把中缀表达式转换成后缀表达式。最后利用后缀表达式来求解表达式的值。该算法的复杂度为O(n)，能够高效、快速地求解表达式的值，提高用户的效率。本次课程设计为计算器模拟程序，主要解决表达式计算的问题，实现分别按表达式处理的过程分解为几个子过程，详细的求解过程如下：1、用户输入表达式。2、判定表达式是否合法。3、把中缀表达式转化为后缀表达式。4、求出后缀表达式的结果。5、输出表达式的结果。通过设计该程序，从而做到方便的求出一个表达式的值，而不需要一步一步进行运算。1.1系统设计流程图1.2主要功能表输入第一个操作数加法减法乘法除法清零ABSSQRT显示结果输入第二个操作数结束开始第6页共31页序号文件名主要功能备注1+加法两个操作数2-减法两个操作数3*乘法两个操作数4/除法两个操作数5aqrt开方一个操作数6abs绝对值一个操作数7Enter等于8Tab清零90退出除了实现基本的功能外，我还增加了其它一些功能，比如支持输入数据为浮点数，更重要的是本程序还支持表达式的嵌套运算，例如：A(1+2*S(2))我的实现方法是利用函数的递归调用来解决此问题，即把1+2*S(2)看成一个子表达式，这个子表达式中2也看成子表达式。这样使得程序的适用范围更加的广泛，适应性更强，能支持更复杂的表达式的运算。这也是本程序的优点之一。第7页共31页第2章总体设计2.1数据结构选择输入的时候将一个算术表达式用一个字符数组来接收，故需要对这个数组进行处理，让操作数和操作符分开，这里我想把开始的算术表达式转换成一个后缀表达式，这样在进行计算的时候就简单多了。而在转换的过程中，对运算符的处理极为重要，这里运用堆栈，用堆栈的先进后出的特点，来处理运算符优先级的问题，让其成功转换成后缀表达式。而在对后缀表达式进行处理的时候，又需要一个堆栈，这个堆栈存放操作数的。并将运算结果存入该栈中。两个堆栈的数据结构如下：struct{chardata[Maxlen];inttop;}optr;//定义运算符栈struct{doubledata[Maxlen];inttop;}opnd;//定义操作数栈这里定义了类型，并且一起定义了两者类型的对象optr,opnd。在将算术表达式转换成后缀表达式，定义change函数；在对后缀表达式进行处理时，定义jisuan函数，另外本程序有个欢迎界面，由meun函数实现。第8页共31页因此主函数于各函数之间的关系为：meun()main()change()jisuan()2.2程序实现流程图第9页共31页2.2程序设计流程图这里的两个主要的函数具体算法在详细设计中有说明本课程设计需要考虑许多的问题，首先是表达式的合法判断，然后是字符串表达式提取分离的问题，核心部分就是中缀表达式转化为后缀表达式。对于第一个问题，我是分步来判断，首先表达式中是否含有其它非法字符，然后判断括号是否合法，接着判断运算法两边是否合法比如除法时，除数不能为零。对于第二个问题，我是直接转换的，从左到右遍历中缀第10页共31页表达式，把数据全部取出来。对于核心问题，利用了“栈”这种“后进先出”的数据结构，利用两个“栈”，一个“数据栈”，一个“运算符栈”来把中缀表达式转换成后缀表达式。最后利用后缀表达式来求解表达式的值。本程序用户界面总共分为3个模块，分别是操作提示，数据输入，数据输出。如图2.3所示。2.3用户界面第3章详细设计和编码第11页共31页3.1表达式的判断表达式的合法判定过程如图3.1所示首先是其它字符的判定，从左到右遍历中缀表达式，看是否存在其它非法的。然后是判定括号是否的匹配是否和合法，首先把“(”对应为1，相应的“)”对应为-1。从左到右遍历表达式，如果遇到括号就加上其对应的值，用sum来保存其累加值。如果在中途出现小于零的情况，即出现“.....)”那么的情况，即非法。在遍历的最后，还要判断sum的值是否为零，如果为零就是合法，否则就是非法。代码如下：for(i=0;is.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(sum0)returnfalse;//括号匹配不合法}运算符判断是否合法，也是遍历一遍表达式，遇到“/”，看其后面的除数是否为零。这里要考虑表达式中出现负数的情况，因此特殊考虑“-”号，判断它的前面是“(”还是没有字符了，那么就是负数。第12页共31页3.2栈的定义、存储然后定义两个数组，p[400]用来存放算术表达式，q[400]用来存放后缀表达式。由前面的数据结构定义两个对象ｏｐｔｒ，ｏｐｎｄ。当输入一个表达式后，定义i作为q的下标，定义dh=1表示是负号，初始化运算符栈optr.top=-1;让后对ｐ进行扫描，当ｐ指向的为数字字符，则将此字符如ｑ，后在往ｑ中输入＃，具体为：while(*p='0'&&*p='9'){q[i]=*p;i++;p++;}if(*p=='.'){q[i]='.';i++;p++;while(*p='0'&&*p='9'){q[i]=*p;i++;p++;}}q[i]='#';i++;dh=0;p后移，继续扫描，当遇到＋或－时，执行if(dh==1){if(*p=='-')optr.top++;optr.data[optr.top]='@';p++;break;}while(optr.top!=-1&&optr.data[optr.top]!='('){q[i]=optr.data[optr.top];optr.top--;i++;}optr.top++;optr.data[optr.top]=*p;p++;dh=0;break;当遇到*或/时，先查看操作符栈中是否有优秀级比它大的或者一样大的运算符，有的话就将其他的出栈，最后自己入栈。执行：while(optr.data[optr.top]=='*'||optr.data[optr.top]=='/'||optr.data[optr.top]=='s'){q[i]=optr.data[optr.top];第13页共31页optr.top--;i++;}optr.top++;optr.data[optr.top]=*p;p++;dh=0;break;当遇到（时，此时不需要别的其他的操作，只需将其入操作符栈，并将dh=0;当遇到）时，此时需要将（之前的操作符全部出栈，具体操作如下：while(optr.data[optr.top]!='('){q[i]=optr.data[optr.top];optr.top--;i++;}optr.top--;p++;dh=0;break;当遇到^时，根据运算符的优先级，执行：while(optr.data[optr.top]=='^'){q[i]=optr.data[optr.top];optr.top--;i++;}optr.top++;optr.data[optr.top]=*p;p++;dh=0;break;遇到％时的操作和^差不多，这里就不做介绍了。当遇到数学函数的相关符号时，这里以sin为例，当扫描ｓ时，还需要扫描后面的两个字符，当它们是in时，说明就是sin函数的符号，此时将此函数的标志入操作符栈，当其为sqrt时，说明是sqrt函数，此时将sqrt函数的标志入栈，这里的标志是自己定的。如果都不是上面两种情况，说明输入有误，跳回。具体的程序如下：if((*(p+1)=='i'||*(p+1)=='I')&&(*(p+2)=='n'||*(p+2)=='N')){optr.top++;optr.data[optr.top]='s';p+=3;dh=0;break;}elseif((*(p+1)=='q'||*(p+1)=='Q')&&(*(p+2)==