数据结构课程设计-模拟计算器程序(共31页).doc

精选优质文档-倾情为你奉上数据结构课程设计题目名称：模拟计算器程序 计算机科学与技术学院课程设计任务书一、 设计任务设计一个模拟计算器的程序二、 设计要求1、 要求对包含加、减、乘、除、括号运算符及SQR和ABS函数的任意整型表达式进行求解2、程序基本功能要求实现完整，并有简单的验证。3、设计报告要求格式规范，符合学校课程设计报告要求。4、报告中流程图要求描述规范，算法设计清楚正确。 三、 设计期限2018年3月5日到2018年3月30日前言利用本学期所学的数据结构课程，运用相关知识，查阅相关资料，编写C语言程序，设计一个简单计算器，要求编写的简单计算器能够模拟windows系统的计算器，用户能够用键盘输入相关数据，要求对包含加、减、乘、除、括号运算符及SQR和ABS函数的任意整型表达式进行求解，并且在程序运行过程中能够正常的退出程序。这个程序实际上就是对一个表达式进行计算。而一个算术表达式中包含各种运算符，每个运算符的等级可能会不同，这就成了本程序需要解决的一个主要的问题之一了。另外计算器中需要有各种数学函数，比如：abs sqrt sin cos tan等，如何对这些函数进行处理，也是本程序能成功的一个关键。还有一个问题就是如何处理操作符和操作数之间的关系也是一个要点。例如：1+2*(3-2/1)，经过怎么样的变换和处理能得出结果。数据的输入这里应该要用字符，然后通过字符和整形之间的关系进行转换即可，这样处理的话，就方便很多了。在计算器程序运行中，输入数据时如果遇到输入错误的情况，能够能过键盘上的退格键进行删除，并且重新输入正确的数据。在数据输入完成后，如果需要放弃本次计算操作，可以利用程序中设置好的按键进行清零，并为下一次运算作准备。本课程设计主要解决的是传统计算器中，不能对表达式进行运算的问题，通过制作该计算器模拟程序，可以做到快速的求解表达式的值，并且能够判定用户输入的表达式是否合法。该模拟计算器的核心部分就在用户输入的中缀表达式的转化，程序中用到了“栈”的后进先出的基本性质。目录第1章 需求分析 5 1.1 系统设计流程图 5 1.2 主要功能表 6第2章 总体设计 7 2.1 数据结构的选择 7 2.2 程序实现流程图 8第3章 详细设计和编码 9 3.1 表达式的判断 10 3.2 栈的定义及存储 113.3 表达式的嵌套处理 143.4 中缀表达式转化为后缀表达式 14第 4章 编码与调试 17 4.1 系统测试 17 4.2 调试 17 4.3错误原因分析 17 4.4 调试结果 19第 5章 总结 21参考文献 22 附录 23第1章 需求分析1.1系统流程图本课程设计主要解决的是传统计算器中，不能对表达式进行运算的问题，通过制作该计算器模拟程序，可以做到快速的求解表达式的值，并且能够判定用户输入的表达式是否合法。该模拟计算器的核心部分就在用户输入的中缀表达式的转化，程序中用到了“栈”的后进先出的基本性质。利用两个“栈”，一个“数据栈”，一个“运算符栈”来把中缀表达式转换成后缀表达式。最后利用后缀表达式来求解表达式的值。该算法的复杂度为O(n)，能够高效、快速地求解表达式的值，提高用户的效率。本次课程设计为计算器模拟程序，主要解决表达式计算的问题，实现分别按表达式处理的过程分解为几个子过程，详细的求解过程如下：1 、用户输入表达式。2 、判定表达式是否合法。3 、把中缀表达式转化为后缀表达式。4 、求出后缀表达式的结果。5 、输出表达式的结果。通过设计该程序，从而做到方便的求出一个表达式的值，而不需要一步一步进行运算。输入第一个操作数加法减法乘法除法清零ABSSQRT显示结果输入第二个操作数结束开始 1.1系统设计流程图1.2主要功能表序号文件名主要功能备注1+加法两个操作数2-减法两个操作数3*乘法两个操作数4/除法两个操作数5aqrt开方一个操作数6abs绝对值一个操作数7Enter等于8Tab清零90退出除了实现基本的功能外，我还增加了其它一些功能，比如支持输入数据为浮点数，更重要的是本程序还支持表达式的嵌套运算，例如：A(1+2*S(2)我的实现方法是利用函数的递归调用来解决此问题，即把1+2*S(2)看成一个子表达式，这个子表达式中2也看成子表达式。这样使得程序的适用范围更加的广泛，适应性更强，能支持更复杂的表达式的运算。这也是本程序的优点之一。第2章 总体设计2.1 数据结构选择输入的时候将一个算术表达式用一个字符数组来接收，故需要对这个数组进行处理，让操作数和操作符分开，这里我想把开始的算术表达式转换成一个后缀表达式，这样在进行计算的时候就简单多了。而在转换的过程中，对运算符的处理极为重要，这里运用堆栈，用堆栈的先进后出的特点，来处理运算符优先级的问题，让其成功转换成后缀表达式。而在对后缀表达式进行处理的时候，又需要一个堆栈，这个堆栈存放操作数的。并将运算结果存入该栈中。两个堆栈的数据结构如下：struct char dataMaxlen; int top; optr; /定义运算符栈struct double dataMaxlen; int top; opnd; /定义操作数栈这里定义了类型，并且一起定义了两者类型的对象optr,opnd。在将算术表达式转换成后缀表达式，定义change函数；在对后缀表达式进行处理时，定义jisuan函数，另外本程序有个欢迎界面，由meun函数实现。因此主函数于各函数之间的关系为： meun()main() change() jisuan() 2.2程序实现流程图 2.2程序设计流程图这里的两个主要的函数具体算法在详细设计中有说明本课程设计需要考虑许多的问题，首先是表达式的合法判断，然后是字符串表达式提取分离的问题，核心部分就是中缀表达式转化为后缀表达式。对于第一个问题，我是分步来判断，首先表达式中是否含有其它非法字符，然后判断括号是否合法，接着判断运算法两边是否合法比如除法时，除数不能为零。对于第二个问题，我是直接转换的，从左到右遍历中缀表达式，把数据全部取出来。对于核心问题，利用了“栈”这种“后进先出”的数据结构，利用两个“栈”，一个“数据栈”，一个“运算符栈”来把中缀表达式转换成后缀表达式。最后利用后缀表达式来求解表达式的值。本程序用户界面总共分为3个模块，分别是操作提示，数据输入，数据输出。如图2.3所示。 2.3用户界面第3章 详细设计和编码3.1表达式的判断表达式的合法判定过程如图3.1所示首先是其它字符的判定，从左到右遍历中缀表达式，看是否存在其它非法的。然后是判定括号是否的匹配是否和合法，首先把“(”对应为1，相应的“)”对应为-1。从左到右遍历表达式，如果遇到括号就加上其对应的值，用sum来保存其累加值。如果在中途出现小于零的情况，即出现“. )”那么的情况，即非法。在遍历的最后，还要判断sum的值是否为零，如果为零就是合法，否则就是非法。代码如下： for(i=0;i<s.length();i+) /检验括号是否合法，以及是否存在非法字符 if(!IsNum(si) && !IsSign(si) && si!='(' && si!=')' && si!='A' && si!='S' && si!='.')return false; if(si='(')sum+=1; else if(si=')')sum-=1; if(sum<0)return false; /括号匹配不合法 运算符判断是否合法，也是遍历一遍表达式，遇到“/”，看其后面的除数是否为零。这里要考虑表达式中出现负数的情况，因此特殊考虑“-”号，判断它的前面是“(”还是没有字符了，那么就是负数。3.2栈的定义、存储然后定义两个数组，p400用来存放算术表达式，q400用来存放后缀表达式。由前面的数据结构定义两个对象，。当输入一个表达式后，定义i作为q的下标，定义dh=1表示是负号，初始化运算符栈optr.top=-1;让后对进行扫描，当指向的为数字字符，则将此字符如，后在往中输入，具体为：while (*p>='0' && *p<='9') qi=*p;i+; p+; if (*p='.') qi='.' i+; p+; while (*p>='0' && *p<='9') qi=*p;i+; p+; qi='#' i+; dh=0; p后移，继续扫描，当遇到或时，执行if (dh=1) if (*p='-') optr.top+;optr.dataoptr.top='' p+; break; while (optr.top!=-1 && optr.dataoptr.top!='(') qi=optr.dataoptr.top; optr.top-; i+; optr.top+;optr.dataoptr.top=*p; p+; dh=0; break;当遇到*或/时，先查看操作符栈中是否有优秀级比它大的或者一样大的运算符，有的话就将其他的出栈，最后自己入栈。执行：while (optr.dataoptr.top='*' | optr.dataoptr.top='/'| optr.dataoptr.top='s') qi=optr.dataoptr.top; optr.top-; i+; optr.top+;optr.dataoptr.top=*p; p+; dh=0; break;当遇到（时，此时不需要别的其他的操作，只需将其入操作符栈，并将dh=0;当遇到）时，此时需要将（之前的操作符全部出栈，具体操作如下：while (optr.dataoptr.top!='(') qi=optr.dataoptr.top; optr.top-; i+; optr.top-; p+; dh=0; break;当遇到时，根据运算符的优先级，执行：while (optr.dataoptr.top='') qi=optr.dataoptr.top; optr.top-;i+; optr.top+;optr.dataoptr.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.dataoptr.top='s' p+=3; dh=0; break; else if(*(p+1)='q'| *(p+1)='Q')&&(*(p+2)='r' | *(p+2)='R')&&(*(p+3)='t' | *(p+3)='T') optr.top+;optr.dataoptr.top='q' p+=4;dh=0;break; else cout<<endl<<"有错误符号"<<endl; return error; 其他的数学函数的操作都是类似的，这里就不一一说明了。这里值得注意的是，当将扫描完时，操作符栈并未一定为空，故需要将操作符栈里的数据全部出栈：while (optr.top!=-1) qi=optr.dataoptr.top; i+; optr.top-; 以上是将算术表达式转换成后缀表达式。还要对后缀表达式进行计算，才能得到结果。首先还是对表达式进行扫描，遇到数字符时，先将其转换成整形后，再判断是否有小数点存在，继续扫描直到遇到运算符，让后通过运算，将次数转换成小数，最后入栈。具体程序实现：d=0; while (*q>='0' && *q<='9') d=10*d+(*q-'0'); q+; x=0.1; if (*q='.') q+; while (*q>='0' && *q<='9') d=d+x*(*q-'0'); x*=0.1; q+; 当遇到操作符时，为双目运算符时，只需要将操作数栈的栈顶和次栈顶数拿出来进行相应的计算，并将其压入次栈顶。为单目运算符时，只需将操作数栈顶元素进行运算即可，并将运算符压入栈即可。这里以/和为例。 其余的均和此类似。if (opnd.dataopnd.top!=0) opnd.dataopnd.top-1=opnd.dataopnd.top-1/opnd.dataopnd.top; else cout<<endl<<"除数不能为零!"<<endl; return error; 和 opnd.top-;break;opnd.dataopnd.top=sin(opnd.dataopnd.top);当q都扫描完时， 返回操作数栈顶元素就是计算的结果。3.3表达式嵌套处理如果遇到A()和S()中含有表达式,而不是单纯的数字，例如A(1.1+3.4*S(2.5),那么就需要对其字表达式“1.1+3.4*S(2.5)”进行递归处理,这个子表达式中还含有子表达式“2.5”,然后再递归处理,依次类推下去。其核心代码如下if(si='A' | si='S') /遇到Abs()或者Sqrt()递归处理子表达式 Expression temp; /创建子表达式 temp.Init(); for(j=0;i+j+2<Posi+1;j+) /复制表达式 stj=si+j+2; stj=0; temp.s=st; /复制表达式 temp.SloveExp(); /得到子表达式的值 numk.first=(si='A'?fabs(temp.Ans):sqrt(temp.Ans); numk.second=0; /标记为数据 if(si-1='-' && (i-1=0 | si-2='(')numk.first=-numk.first; k+,i=Posi+1; 3.4 中缀表达式转化为后缀表达式中缀表达式转化为后缀表达式，利用两个“栈”，一个“数据栈”，一个“运算符栈”来把中缀表达式转换成后缀表达式。最后利用后缀表达式来求解表达式的值。设一个stack存后缀数据，一个rout栈存运算符。 算法流程如下： （1）从右向左依次取得数据ch。 （2）如果ch是操作数，直接加进stack中。 （3）如果ch是运算符（含左右括号），则： a：如果ch = '('，放入堆栈rou中。 b：如果ch = ')'依次输出堆栈rout中的运算符，直到遇到'('为止。 c：如果ch不是')'或者'('，那么就和堆栈rout顶点位置的运算符top做优先级比较。 1：如果ch优先级比rtop高，那么将ch放入堆栈rout。 2：如果ch优先级低于或者等于rtop，那么输出top到stack中（直到！top或者满足 1），然后将ch放入堆栈rout。 可以看出算法复杂度是O(n）的，因此效率是比较高的，能够在1s内处理百万级别长度的表达式。算法的主要思想是利用“栈”的后进先出的特性，以及运算符的优先级，这里我们定义运算符的优先级；代码如下：int GetKey(char c) /定义运算符的关键字 int key; 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; return key; 第 4章 编码与调试程序的调试是指对程序的差错和排错，为了便于差错、阅读，在设计该程序的过程中我们采用了结构化程序方法编辑，添加了尽可能多的注释，这就为接下来的调试过程带来了很多方便。经过仔细检查之后进行上机调试。进行编译，如果在编译和连接过程中发现错误，屏幕上显示了出错信息，根据提示找到出错的位置，加以改正，在进行编译如此反复,直到顺利通过编译和连接为止。在本次实习过程中碰到的编译、连接的错误主要有：缺少变量定义、定义为置不正确、语法错误、转义字符漏用、逻辑错误等。4.1 系统测试 4.1系统测试图4.2 调试根据电脑所给的提示出现语法错误，缺少变量的定义大多的语法错误在通过书本参考下能够修改。主要是平时看书不仔细、不太注意而产生的，如没有注意具体数据使用是有一定的范围限定；过分重视分号的重要性而在for、if、while语句中画蛇添足加分号；在使用文件的时候忘记将文件先打开，对打开的方式与使用的情况不太注意而造成不匹配；还有漏掉形参的定义是值不能传递等等。这些语法错误有信息框的提示一般是能够排除的。另外还有部分注释的位置也错了，最重要的是逻辑上的错误，一般电脑不容易发现。所以更对程序仔细的检查。经认真修改之后重新保存文件。4.3 错误原因分析4.3.1 缺少变量定义，定义位置不正确由于该程序相对来讲稍有些长，前后有些变量不容易联系起来，但是在错误信息的提示下一般还是很容易找到，不过需要注意的是在定义的时候有些函数使用同样的变量名而表示不同的作用，因而使用要很小心，定义及定义的位置特别留意。为减少这样的错误我后来还是用不同的变来名来表示，结果引起的那些错误解决了。4.3.2 语法错误大多的语法错误在通过书本参考下能够修改。主要是平时缺乏锻炼、不太注意而产生的。如没有注意具体数据使用是有一定的范围限定；过分重视分号的重要性而在for、if、while语句中画蛇添足加分号。4.3.3 注释的位置程序设计中在注释的时候不能同我们平常写字一样随心所欲，我们应该注意注释的格式。注释中不能含有C语言可执行的语句。4.3.4 逻辑错误编译、连接的成功并不意味着程序的最终成功，逻辑上的错误机器不易检查出来，这时需要多数据结果进行分析。这种错误的查找是最难的，需要有相当的耐心和细心去把问题找出来，这也是本次程序编辑过程中碰到的最大的难题。往往运行之后得不到令人满意的结果。此时解决的方法一则用“分段检查”的方法，在程序的不同位置设几个printf函数语句，输出有关变量的值，逐段往下检查，对检查出的错误进行修改，当调试完毕将设置的printf都删去，若在程序中找不到问题，则再来考虑算法是否逻辑严谨，再进行修改，如此循环往复，直到最后程序运行成功。在本次程序编辑过程中，我就是这样处理这个问题的。所以到最后我找到了错误，及时改正，终于把程序完成了，一切功能显示正常。在逻辑上的错误，主要就是算法中出现的问题，本程序中的算法有点复杂，在表达式转换成后缀表达式的过程中就出现了很多的错误。这里举出一个简单的错误，由于本程序在写的时候，定义了derror=在程序中就不能出现这个计算结果，虽然它超过了本程序的能处理的范围，可是其结果还是，故返回主函数时，在if (change(p,q)=1) k=jisuan(q); if(k=derror)cout<<"" else cout<<"计算结果为："<<k<<endl;这里就会出错。导致图中的错误。解决办法，这里我对这中情况没有做特殊的处理。应为在实际的运算过程中，很少有这个结果出现，几乎是不出现的。如何去定义这个数，一直是个问题。本程序的，在定义的时用了两个数组，故其空间复杂度是n，在算法上，这里我用了一个死循环，当输入不为0时，会一直运行。所以只讨论运行一次的时间复杂度。在转换的函数中，有个while()循环，这里的复杂度是n，而在这个循环里，还存在while()循环，故其时间复杂度是n的平方。在计算函数中，其复杂度也是n的平方。故可知本程序的时间复杂度是n平方。4.4调试结果4.4.1普通计算图4.4.2Abs函数计算图4.4.3Aqrt函数计算图4.4.4嵌套计算图4.4.5输入错误提示图4.4.6输入错误提示图4.4.7输入错误提示图4.4.8结束程序图经过人工计算，可知以上结果是正确的第5章 总结通过两周的课程设计，我学会了如何写一个精简、快速、健壮的程序。一个好的程序应该是一个所占空间小、运行时间短、其他性能也好的程序。而要做出一个好的程序则应该通过对算法与其数据结构的时间复杂度和空间复杂度进行实现与改进。然而，实际上很难做到十全十美，原因是各要求有时相互抵触，要节约算法的执行时间往往要以牺牲更多的存储空间为代价：而为了节省存储空间又可能要以更多的时间为代价。因此，只能根据具体情况有所侧重：如果程序的使用次数较少，则应该力求算法简明易懂，而易于转换为上机程序；如果程序反复多次使用，则应该尽可能选用快速算法；如果解决问题的数据量极大，机器的内存空间较小，则在编写算法时应该考虑如何节省空间。 本次课程设计培养了了我们独立思考的能力，提高了我们的动手操作水平。在具体设计操作中，我们巩固了本学期所学的数据结构与算法的理论知识，进一步提高了自己的编程能力。这也是课程设计的最终目的所在。通过实际操作，开发了自己的逻辑思维能力，培养了分析问题、解决问题的能力。 但在程序设计的过程中我也深刻的感受到自己实力的不足，无法灵活的运用各种工具和函数，对于课程所讲的东西也无法在脱离课本的情况中完成，我意识到自己在今后的学习生活中，一定要勤于思考，扎实掌握理论知识，灵活运用课上所学的东西，做一个优秀的程序员。参考文献1 谢希仁. 计算机网络（第五版）M. 北京：电子工业出版社，2008年2月2 胡小强 计算机网络M 北京：北京邮电大学出版社2005年1月3 李丽娟 C语言程序设计教程（第2版）M，人民邮电出版社 2009年3月4 王昆仑，李红. 数据结构与算法. 北京：中国铁道出版社，2006年5月。5 郑莉 ，董渊，张瑞丰 c+语言程序设计 北京：清华大学出版社，2004附录（源程序代码）#include "iostream"#include "math.h"#include "string"#include "stdlib.h"#include "windows.h"#define derror #define Maxlen 400using namespace std; struct char dataMaxlen; int top; optr;/定义运算符栈，并定义全局变量struct double dataMaxlen; int top; opnd;/定义操作数栈，并定义全局变量void main() char p400,q400; double k;void meun(); /声明菜单函数int change(char *p, char q);/声明转换函数double jisuan(char *q);/声明计算函数meun();for(;) /循环执行 cout <<"请输入:" cin>>p; if (strcmp(p,"0")=0) return; if (change(p,q)=1) k=jisuan(q); if(k=derror)cout<<"" else cout<<"计算结果为："<<k<<endl;system("pause"); /控制输出格式system("cls"); meun(); void meun()system("color 0a"); cout<<"tt *"<<endl; cout<<" 欢迎使用本计算器"<<endl; cout<<"tt *"<<endl;cout<<endl;cout<<"按0结束本程序"<<endl;int change(char *p, char q) /将算术表达式p转换成表达式后缀表达式q int i=0; /i作为q的下标 int dh=1; /dh=1表示是负号 optr.top=-1; /初始化运算符栈 while (*p!='0') /p表达式未扫描完时循环 switch(*p) /判断各种情况,并做相应的处理 case '(': optr.top+;optr.dataoptr.top=*p; dh=1;p+;break; case ')': while (optr.dataoptr.top!='(') qi=optr.dataoptr.top; optr.top-; i+; optr.top-; p+; dh=0; break; case '+': case '-': if (dh=1) / +,-是正负号 if (*p='-') optr.top+;optr.dataoptr.top='' p+; break; while (optr.top!=-1 && optr.dataoptr.top!='(') qi=optr.dataoptr.top; optr.top-; i+; optr.top+;optr.dataoptr.top=*p; p+; dh=0; break; case '*': case '/': while (optr.dataoptr.top='*' | optr.dataoptr.top='/'| optr.dataoptr.top='s') qi=optr.dataoptr.top; optr.top-; i+; optr.top+;optr.dataoptr.top=*p; p+; dh=0; break; case '': while (optr.dataoptr.top='') qi=optr.dataoptr.top; optr.top-;i+; optr.top+;optr.dataoptr.top=*p;p+;dh=0;break; case '%': while (optr.dataoptr.top='%') qi=optr.dataoptr.top; optr.top-;i+; optr.top+;optr.dataoptr.top=*p;p+;dh=0;break; case ' ': p+; break; /消除空格 case 's': case 'S': if(*(p+1)='i' | *(p+1)='I')&&(*(p+2)='n' | *(p+2)='N') optr.top+;optr.dataoptr.top='s' p+=3; dh=0; bre