算术表达式求值演示-课程设计报告

桂林电子科技大学综合设计说明书用纸课程设计说明书题目：表达式的求值学院：专业：姓名：学号：指导教师：2011年7月1日桂林电子科技大学综合设计说明书用纸算术表达式求值演示目录第一章概述……………………………………………………………1第二章系统分析………………………………………………………2第三章概要设计………………………………………………………2第四章详细设计………………………………………………………5第五章运行与测试……………………………………………………13第六章总结与心得……………………………………………………16参考文献………………………………………………………………16桂林电子科技大学综合设计说明书用纸1第一章概述在信息管理与信息系统专业中发现了我们专业的学生应该掌握的知识，而课程设计是实践性教学中的一个重要环节，它以某一课程为基础，比如我们大一和大二的时候做过的C，以及JAVA这些课程设计，它可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。《数据结构C++版》是一门重要的专业基础课，是计算机理论和应用的核心基础课程。在学习的过程中，我发现在数据结构课程设计过程中，它要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，都必须加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。对于我们专业来说，虽然说对技术要求不是很高，但是在实际操作过程中，没有足够的专业知识对于编程来说是远远不可以达到要求的，所以对于这次的课程设计，我们必须要通过自己额外补充知识来完成它。在这次的课程设计中我选择的题目是表达式的求值演示。它的基本要求是：以字符序列的形式从终端输入语法正确的，不含变量的整数表达式。利用算符优先关系，实现对算术四则混合运算表达式的求值，并演示在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。表达式计算是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。设计一个程序，演示用算符优先法对算术表达式求值的过程。深入了解栈和队列的特性，以便在解决实际问题中灵活运用它们，同时加深对这种结构的理解和认识。对于表示出栈在每执行一个过程中都要输出它的变化，这点我认为在编程中是比较困难的，以我自身的能力，是不可能在规定的时间内完成任务的，所以我参考了很多有价值的书籍来帮助我完成我的程序设计。第二章系统分析1．算法基本思想：为了实现算符优先算法，可以使用两个工作栈。一个称做OPTR，用以寄存运算符；另一个称做OPND，用以寄存操作数或运算结果。算法的基本思想是：桂林电子科技大学综合设计说明书用纸22．（1）首先置操作数栈为空栈，表达式起始符“＃”作为运算符栈的栈底元素3．（2）依次读入表达式的每个字符，若是操作数则进入OPND栈，若是运算符，则和OPTR栈的栈顶运算符比较优先权后做相应操作（栈顶元素优先权低则压栈，栈顶元素优先权高或者相等（比如5*6/9）则退栈并将运算结果入栈，“＃”优先级最低），直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为“＃”）4．以字符列的形式从终端输入语法正确的、不含变量的整数表达式。利用已知的算符优先关系，实现对算术四则混合运算表达式的求值，并仿照参考书中的例子在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。5．一般来说，计算机解决一个具体问题时，需要经过几个步骤：首先要从具体问题抽象出一个适当的数学模型，然后设计一个解决此数学模型的算法，最后编出程序，进行测试，调试直至得到想要的答案。对于算术表达式这个程序，主要利用栈，把运算的先后步骤进行分析并实现简单的运算！为实现算符优先算法，可以使用两个栈，一个用以寄存运算符，另一个用以寄存操作数和运算结果。6．演示程序是以用户于计算机的对话方式执行，这需要一个模块来完成使用者与计算机语言的转化。7．程序执行时的命令：本程序为了使用具体，采用菜单式的方式来完成程序的演示，几乎不用输入什么特殊的命令，只需按提示输入表达式即可。（要注意输入时格式，否者可能会引起一些错误）8.测试数据。第三章概要设计一个算术表达式中除了括号、界限符外，还包括运算数据和运算符。由于运算符有优先级别之差，所以一个表达式的运算不可能总是从左至右的循序执行。每次操作的数据或运算符都是最近输入的，这与栈的特性相吻合，故本课程设计借助栈来实现按运算符的优先级完成表达式的求值计算。算法设计1、算符的优先级比较函数Compare(charm,charn)桂林电子科技大学综合设计说明书用纸3算法的基本思想：通过已知的算符间的优先关系写出算符的优先级算法。任意两个相继出现的算符c1和c2之间的优先关系至多是下面3种关系之一：c1c2c1的优先权低于c2c1=c2c1的优先权等于c2c1c2c1的优先权高于c2算法步骤:Step1:如果输入符号为“+”或“-”1.1如果栈顶元素为“(”、“#”,此时栈顶符号优先级低，返回“”1.2否则，栈顶符号优先级高,返回“”Step2:如果输入符号为“*”或“/”2.1如果栈顶元素为“)”、“*”、“/”,此时栈顶符号优先级高，返回“”2.2否则，栈顶符号优先级低,返回“”Step3:如果输入符号为“(”,则直接返回“”Step4:如果输入符号为“)”4.1如果栈顶元素为“(”,此时优先级同，返回“=”4.2否则，栈顶符号优先级高,返回“”Step5:输入符号为其他5.1栈顶元素为“#”,此时优先级同，返回“=”5.2否则，栈顶符号优先级高,返回“”2、确定如何入栈函数evaluate(SqStack1&S1,SqStack2&S2)算法的基本思想：（1）首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素；（2）依次读入表达式中每个字符，若是操作数则进运算数栈，若是运算符则和运算符栈的栈顶运算符比较优先后作相应操作，直至整个表达式求值完毕（即运算符的栈顶元素和当前读入的字符均为“#”）。算法步骤:Step1:将‘#’入栈，作为低级运算符Step2:输入不含变量的表达式（以#结束!）Step3:如果c!='#'||GetTop1(S1)!='#'3.1如果输入的字符如果不是运算符号，则继续输入直到输入的是运算符为止，将非运算符转换成浮点数3.2如果输入的是运算符a、遇到运算符，则将之前输入的操作数进栈桂林电子科技大学综合设计说明书用纸4b、比较运算符的优先级1)栈顶元素优先级低，则入栈且继续输入2)栈顶元素优先级相等，脱括号并接收下一字符3)栈顶元素优先级高，则退栈并将运算结果入栈Step4:显示表达式最终结果程序包含三个模块(1)主程序模块，其中主函数为voidmain{输入表达式；根据要求进行转换并求值；输出结果；}(2)表达式求值模块——实现具体求值。(3)表达式转换模块——实现转换。各个函数之间的调用关系栈的抽象数据类型定义ADTSqStack{数据对象：D={ai|ai∈ElemSet,i=1,2,3……，n,n≥0}数据关系：R1={ai-1,ai|ai-1,ai∈D,i=1,2,3,……，n}约定其中ai端为栈底，an端为栈顶。主函数表达式转换表达式求值数据输入输出输出桂林电子科技大学综合设计说明书用纸5操作集合：(1)voidInitStack1(SqStack1&S1);//声明栈建立函数(2)voidInitStack2(SqStack2&S2);//声明栈建立函数(3)voidevaluate(SqStack1&S1,SqStack2&S2);//确定如何入栈函数(4)voidPush1(SqStack1&S1,chare);//声明入栈函数(5)voidPush2(SqStack2&S2,floate);//声明入压栈函数(6)charGetTop1(SqStack1&S1);//声明取栈顶元素函数(7)floatGetTop2(SqStack2&S2);//声明取栈顶元素函数(8)charPop1(SqStack1&S1);//声明出栈函数(9)floatPop2(SqStack2&S2);//声明出栈函数(10)charCompare(charm,charn);//声明比较函数(11)floatOperate(floata,charrheta,floatb);//声明运算函数(12)voidDispStack1(SqStack1&S1);//从栈底到栈顶依次输出各元素(13)voidDispStack2(SqStack2&S2);//从栈底到栈顶依次输出各元素}ADTSqStack第四章详细设计源程序#includeiostreamusingnamespacestd;#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefstruct//运算符栈{char*base;char*top;intstacksize;}SqStack1;typedefstruct//运算数栈{桂林电子科技大学综合设计说明书用纸6float*base;float*top;intstacksize;}SqStack2;voidInitStack1(SqStack1&S1);//声明栈建立函数voidInitStack2(SqStack2&S2);//声明栈建立函数voidevaluate(SqStack1&S1,SqStack2&S2);//确定如何入栈函数voidPush1(SqStack1&S1,chare);//声明入栈函数voidPush2(SqStack2&S2,floate);//声明入压栈函数charGetTop1(SqStack1&S1);//声明取栈顶元素函数floatGetTop2(SqStack2&S2);//声明取栈顶元素函数charPop1(SqStack1&S1);//声明出栈函数floatPop2(SqStack2&S2);//声明出栈函数charCompare(charm,charn);//声明比较函数floatOperate(floata,charrheta,floatb);//声明运算函数voidDispStack1(SqStack1&S1);//从栈底到栈顶依次输出各元素voidDispStack2(SqStack2&S2);//从栈底到栈顶依次输出各元素/*主函数*/voidmain(){SqStack1S1;//定义运算符栈SqStack2S2;//定义运算数栈InitStack1(S1);//调用栈建立函数InitStack2(S2);//调用栈建立函数evaluate(S1,S2);//调用确定如何入栈函数cout按任意键结束!endl;}/*运算符栈函数*/voidInitStack1(SqStack1&S1)//构造一个空栈S1{S1.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char));if(!S1.base)cout存储分配失败！;//存储分配失败桂林电子科技大学综合设计说明书用纸7S1.top=S1.base;S1.stacksize=STACK_INIT_SIZE;}voidPush1(SqStack1&S1,chare)//入栈{if(S1.top-S1.base=S1.stacksize)//如果栈满，追加存储空间{S1.base=(char*)realloc(S1.base,(S1.stacksize+STACKINCREMENT)*sizeof(char));if(!S1.base)cout存储分配失败！;else{S1.top=S1.base+S1.stacksize;S1.stacksize=S1.stacksize+STACKINCREMENT;}}*S1.top=e;S1.top=S1.top+1;//将元素压入