《《数据结构与算法》课程设计-表达式求值算法实现》由会员分享，可在线阅读，更多相关《《数据结构与算法》课程设计-表达式求值算法实现（23页珍藏版）》请在金锄头文库上搜索。
1、河南工程学院数据结构与算法课程设计成果报告表达式求值算法实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目表达式求值算法实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教师评语：
2、 日期： 年 月 日目 录1 课程设计目标与任务11.1课程设计目标11.2 课程设计任务12 分析与设计22.1 题目分析22.2 存储结构设计22.3 算法描述22.5 测试程序说明43 程序清单74.1 测试数据114.2 测试结果分析135 总结141 课程设计目标与任务1.1课程设计目标数据结构课程设计是在学完数据结构课程之后的实践教学环节。该实践教学是软件设计的综合训练,包括问题分析，总体结构设计，用户界面设计，程序设计基本技能和技巧。要求学生在设计中逐步提高程序设计能力培养科学的软件工作方法学生通过数据结构课程设计各方面得到锻炼：（1）能根据实际问题的具体情况结合数据结构课程中的
3、基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法；（2）通过上机实习,验证自己设计的算法的正确性，学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改；（3）培养算法分析能力，分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平；（4）尽可能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来，获得算法的直观感受。1.2 课程设计任务设计一个表达式求值的程序。该程序必须可以接受包含（，），+， -，*，/，%，和（求幂运算符ab=a）的中缀表达式并求出结果。如果表达式正确则输
4、出表达式的结果如果表达式非法则输出错误信息。2 分析与设计2.1 题目分析利用栈设计一个程序，该程序能够用于表达式求值，程序能够处理以字符序列的形式输入的不含变量的实数表达式，能正确处理负数与小数，判断表达式是否语法正确，包含分母不能为零的情况。正确实现对算术四则混合运算表达式的求值，将计算中遇到的问题和结果予以输出。2.2 存储结构设计本程序使用了两个栈，一个为OPTR，用以存放运算符，另一个为OPND，用以存放操作数或运算的中间结果。首先初始化操作数栈OPTR和运算符栈OPND，并将表达式起始符“”压入运算符栈，依次读入表达式中的每个字符,若是操作数则直接进入操作数栈OPTR，若是运算符，
5、则与运算符栈OPND的栈顶运算符进行优先权比较，并做如下处理： (1) 若栈顶运算符的优先级低于刚读入的运算符，则让刚读入的运算符进OPTR栈。 (2) 若栈顶运算符的优先级高于刚读入的运算符，则将栈顶运算符退栈,同时接收下一个运算符，最后将运算结果推入OPND栈。 (3) 若栈顶运算符的优先级与刚读入的运算符的优先级相同，说明左右括号相遇，只需将栈顶运算符“左括号”退栈即可。当输入完一个完整的表达式之后（没有遇到最后一个是运算符输入时）程序结束。2.3 算法描述在计算机中，算术表达式的计算往往是通过使用栈来实现的。所以，求值程序的最主要的数据结构就是栈。本程序就是使用栈来存储输入表达式的操作
6、符和操作数。输入的表达式是由操作数和运算符以及改变运算次序的圆括号连接而成的式子。任何一个表达式都是由操作数(OPTR)、运算符(OPND)和界限(delimiter)组成的。（1）首先是创建了一个运算符优先级表，用于比较运算符，然后创建两个栈，再设计3个指针，用于指向结点。然后是计算函数Operate的设计，它也是利用栈来实现运算。利用创建的两个栈直接对表达式进行计算。分别构建一个char类型和一个double类型的栈函数。（2）在main函数中让用户进行输入，将用户输入的字符串进行循环、判断，并将判断后的字符串传递到新的数组中，循环结束后，再将数组传递给中缀表达式转后缀表达式函数。（3）在
7、Operate()函数中先创建一个数字栈和一个符号栈，对表达式进行循环，直到元素为0。在循环中如果元素为数字，将元素赋给新的数组s，再判断下一个元素，若是则利用函数将数组中的字符串转换成double类型的数字，然后数字进栈，清空数组s；否则，继续判断。若元素不为数字，则先看栈顶，如果栈为空或栈顶元素为（或者栈顶元素为+或并且现有元素为*、/或%又或是现有元素为，则现有元素进栈；否则，再对现有元素进行判断：如果现有元素为），运算符出栈直到（出栈；否则，运算符出栈直到栈空或者栈顶元素的优先级低于现有运算符，现有运算符才进栈。每当有一个运算符出栈，就从数栈中取两个数与运算符一起传递给Operate(
8、)函数,并将函数的返回值压入栈中。循环结束后，将栈中的运算符全部依次输出，每当有一个运算符出栈，就从数栈中取两个数与运算符一起传递给Operate()函数,并将函数的返回值压入栈中，最后输出数字栈中的数字成为表达式的最终结果，再销毁栈。（4）Operate()函数是利用switch语句对传入进来的运算符进行判断，并将传入的两个数进行相应的运算，并返回运算结果。 （5）各模块的主要功能*Push(SC *s,char c)：把字符压栈*Push(SF *s,float f)：把数值压栈*Pop(SC *s)：把字符退栈*Pop(SF *s)：把数值退栈Operate(a,theta,b)：根据t
9、heta对a和b进行+ 、- 、* 、/ 、操作In(Test,*TestOp)：若Test为运算符则返回true，否则返回falseReturnOpOrd(op,*TestOp)：若Test为运算符，则返回此运算符在数组中的下标precede(Aop,Bop)：根据运算符优先级表返回Aop与Bop之间的优先级EvaluateExpression(*MyExpression)：用算符优先法对算术表达式求值2.4 程序流程图下面是一个程序流程图，通过它可以更直观的了解程序的原理，程序主要使用两个栈实现主要功能，一开始初始化栈，接下来就是计算算法的设计:图1-1表达式求值算法程序流程图 2.5 测
10、试程序说明1 一般来说，计算机解决一个具体问题时，需要经过几个步骤：首先要从具体问题抽象出一个适当的数学模型，然后设计一个解决此数学模型的算法，最后编出程序，进行测试，调试直至得到想要的答案。对于算术表达式这个程序，主要利用栈，把运算的先后步骤进行分析并实现简单的运算！为实现算符优先算法，可以使用两个栈，一个用以寄存运算符，另一个用以寄存操作数和运算结果。2 演示程序是以用户于计算机的对话方式执行，这需要一个模块来完成使用者与计算机语言的转化。3程序块的功能介绍：（1）栈的抽象数据类型定义：ADT Stack数据对象：D=ai|aiElemSet,i=1,2,n,n0数据关系：R1=|ai-1
11、,aiD,i=2,n约定an端为栈顶，ai端为栈底（）基本操作：Push(&S,e)初始条件：栈S已存在操作结果：插入元素e为新的栈顶元素Pop(&S,&e)初始条件：栈S已存在且非空操作结果：删除S的栈顶元素，并用e返回其值ADT Stack3 程序清单#includestdio.h#includestdlib.h #includestring.h #includemath.h#define true 1 #define false 0 #define OPSETSIZE 8 typedef int Status; unsigned char Prior88 = / 运算符优先级表 / +
12、- * / ( ) # /*+*/, /*(*/,=, , , /*#*/, ,=, ; typedef struct StackChar char c; struct StackChar *next; SC; /StackChar类型的结点SCtypedef struct StackFloat float f; struct StackFloat *next; SF; /StackFloat类型的结点SFSC *Push(SC *s,char c) /SC类型的指针Push，返回p SC *p=(SC*)malloc(sizeof(SC); p-c=c; p-next=s; return p
13、; SF *Push(SF *s,float f) /SF类型的指针Push，返回p SF *p=(SF*)malloc(sizeof(SF); p-f=f; p-next=s; return p; SC *Pop(SC *s) /SC类型的指针Pop SC *q=s; s=s-next; free(q); return s; SF *Pop(SF *s) /SF类型的指针Pop SF *q=s; s=s-next; free(q); return s; float Operate(float a,unsigned char theta, float b) /计算函数Operate switch(th
