表达式求值算法实现3.docx

河南工程学院数据结构与算法课程设计成果报告表达式求值算法实现2014年12月29日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;)计算函数Operatefloat Operate(float a,unsigned char theta, float b)(switch(theta)case '+1: return a+b;casereturn a-b;case return a*b;case return a/b;case，A，: return pow(a,b);default: return 0;)charOPSETOPSETSIZE=,+,-,*,7，,(7),#,，A，;Status ln(char Test,char *TestOp)(int Find=false;for (int i=0; i< OPSETSIZE; i+)(if (Test = TestOpi) Find= true;)return Find;)Status ReturnOpOrd(char op,char *TestOp)(for(int i=0; i< OPSETSIZE; i+) if (op = TestOpi) return i;)char precede(char Aop, char Bop)return PriorReturnOpOrd(Aop/OPSET)ReturnOpOrd(Bop,OPSET); )float EvaluateExpression(char* MyExpression) (/算术表达式求值的算符优先算法/设OPTR和OPND分别为运算符栈和运算数栈，0P为运算符集合SC*OPTR=NULL;运算符栈，字符元素SF*OPND=NULL;运算数栈，实数元素char TempData20;float Data,a,b;char theta,*c,Dr='#,0'；OPTR = Push(OPTR#')；c=strcat(MyExpression,Dr);strcpy(TempData J0");字符串拷贝函数while (*c!=| OPTR->c!='#')(if (!ln(*c, OPSET) (Dr0=*c;strcat(TempData,Dr);字符串连接函数C+；if (ln(*c, OPSET) (Data=atof(TempData); 字符串转换函数(double)OPND=Push(OPND, Data);strcpy(TempData,"O"); )else /不是运算符那么进栈(switch (precede(OPTR->c, *c)(case '<':/栈顶元素优先级低 OPTR=Push(OPTR, *c);C+； break;case '=':/脱括号并接收下一字符 OPTR=Pop(OPTR);C+； break;case '>':/退栈并将运算结果入栈theta=OPTR->c;OPTR=Pop(OPTR); b=OPND->f;OPND=Pop(OPND); a=OPND->f;OPND=Pop(OPND);OPND=Push(OPND, Operate(a, theta, b); break; /switch/whilereturn OPND->f; /EvaluateExpressionint main(void)(char s128;puts(“请输入表达式gets(s);puts("该表达式的值为:")；printf(H%sb=%gn",s,EvaluateExpression(s);system("pause");return 0;)4测试4.1测试数据下面执行加法运算:图1T加法运算测试结果图下面执行减法运算：F:学习生'程序炼习题6Debug6.exe情输入表达式：10-9该表达式的值为：10-9=1番按任意键继续图1-2减法运算测试结果图10下面执行乘法运算:图1-3乘法运算测试结果图下面执行除法运算:吓:学习无'程序练习题6Debug6.exe，请输入表达式：8/4该表达式的值为：8/4=2请按任意键继续.图1-4除法运算测试结果图11下面执行混合运算:F:学习那程序炼习题5Debug5.exe'请输入表达式： <<2+2>*3-2>/5 该表达式的宿为： <<2+2>*3-2>/5=2 请按任意键继续.图1-5混合运算测试结果图4. 2测试结果分析程序经过测试之后，主要的功能可以实现，可以完成实验的要求，并仿照教 科书的例子在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程进行 四那么混合运算。但是也存在一些小问题，就是在计算完一个表达式之后，不可以 直接进行下一运算，必须再一次启动程序进行计算。但它的优点是，用户输入方 便，没有过多的输入要求，直接输入想计算的表达式即可，没有过多的格式要求。 以字符列的形式从终端输入语法正确的、不含变量的整数表达式。利用的运 算符优先关系，实现对算术四那么混合运算表达式的求值。125总结一个星期完成的这课程设计。虽然之前对栈已经有了一些认识和了解，但是 通过这次课程设计，我发现之前对栈的了解不值一提，这次课程设计让我对栈有 了更深刻的理解，对它的运用也更熟练。对程序的设计也有了很多自己的思维方 式和想法。开始有许多课程给我选择，可是我凭着自认为对栈比拟了解，所以选 了栈这个课题，可是开始弄的时候却不知道该从何下手，经过同学和老师的帮助 才慢慢的设计这个课程，然后经过一个星期的努力才把这个课程完成。但是我觉 得我对栈的理解远远不够。还要像老师和同学们多多学习，去游览各种资料，让 我对栈有更深的理解。13参考文献1朱福喜.Java语言程序设计（第二版）.科学出版社2陈国君等.Java程序设计基础（第二版）.清华大学出版社3 Deitel.Java大学基础教程（第六版）.电子工业出版社4 MaryCampione.Java语言导学（第四版）.机械工业出版社5 Y. Daniel Liang.Java语言程序设计基础篇（第六版）.机械 工业出版社6 Kathy Sierra.Head First Java（第二版）.东南大学出版社1415题目表达式求值算法实现考核工程考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、 基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答下列问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总评成绩指导教师评语:日期:1课程设计目标与任务11.1课程设计目标11. 2课程设计任务12分析与设计22.1题目分析22. 2存储结构设计22. 3算法描述22.5测试程序说明43程序清单74.1测试数据104. 2测试结果分析125总结131课程设计目标与任务1.1课程设计目标数据结构课程设计是在学完数据结构课程之后的实践教学环节。该实践教学 是软件设计的综合训练,包括问题分析，总体结构设计，用户界面设计，程序设 计基本技能和技巧。要求学生在设计中逐步提高程序设计能力培养科学的软件工 作方法学生通过数据结构课程设计各方面得到锻炼：(1)能根据实际问题的具体情况结合数据结构课程中的基本理论和基本算 法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决 问题的有效算法；(2)通过上机实习，验证自己设计的算法的正确性，学会有效利用基本调试 方法，迅速找出程序代码中的错误并且修改；(3)培养算法分析能力，分析所设计算法的时间复杂度和空间复杂度，进 一步提高程序设计水平；(4)尽可能借助语言环境实现图形显示功能，以便将抽象的数据结构以图 形方式显示出来,将复杂的运行过程以动态方式显示出来，获得算法的直观感受。 1. 2课程设计任务设计一个表达式求值的程序。该程序必须可以接受包含(,),+, -，*, /, %,和八(求塞运算符a-b=a)的中缀表达式 并求出结果。如果表达式 正确那么输出表达式的结果如果表达式非法那么输出错误信息。2分析与设计1 .1题目分析利用栈设计一个程序，该程序能够用于表达式求值，程序能够处理以字符序 列的形式输入的不含变量的实数表达式，能正确处理负数与小数，判断表达式是 否语法正确，包含分母不能为零的情况。正确实现对算术四那么混合运算表达式的 求值，将计算中遇到的问题和结果予以输出。2 . 2存储结构设计本程序使用了两个栈，一个为OPTR,用以存放运算符，另一个为OPND,用 以存放操作数或运算的中间结果。首先初始化操作数栈OPTR和运算符栈OPND, 并将表达式起始符“ "压入运算符栈，依次读入表达式中的每个字符,假设是操 作数那么直接进入操作数栈OPTR,假设是运算符，那么与运算符栈OPND的栈顶运算符 进行优先权比拟，并做如下处理：(1)假设栈顶运算符的优先级低于刚读入的运算符，那么让刚读入的运算符进 OPTR 栈。(2)假设栈顶运算符的优先级高于刚读入的运算符，那么将栈顶运算符退栈，同 时接收下一个运算符，最后将运算结果推入OPND栈。(3)假设栈顶运算符的优先级与刚读入的运算符的优先级相同，说明左右括号 相遇，只需将栈顶运算符“左括号”退栈即可。当输入完一个完整的表达式之后 (没有遇到最后一个是运算符输入时)程序结束。2. 3算法描述在计算机中，算术表达式的计算往往是通过使用栈来实现的。所以，求值程 序的最主要的数据结构就是栈。本程序就是使用栈来存储输入表达式的操作符和 操作数。输入的表达式是由操作数和运算符以及改变运算次序的圆括号连接而成 的式子。任何一个表达式都是由操作数(OPTR)、运算符(OPND)和界限(delimiter) 组成的。(1)首先是创立了一个运算符优先级表，用于比拟运算符，然后创立两个 栈，再设计3个指针，用于指向结点。然后是计算函数Operate的设计，它也是利用栈来实现运算。利用创立的两个栈直接对表达式进行计算。分别构建一个 char类型和一个double类型的栈函数。(2)在main函数中让用户进行输入，将用户输入的字符串进行循环、判断， 并将判断后的字符串传递到新的数组中，循环结束后，再将数组传递给中缀表达 式转后缀表达式函数。(3)在Operate。函数中先创立一个数字栈和一个符号栈，对表达式进行循 环，直到元素为'0'。在循环中如果元素为数字，将元素赋给新的数组s口， 再判断下一个元素，假设是那么利用函数将数组中的字符串转换成double类型的数 字，然后数字进栈，清空数组s 口；否那么，继续判断。假设元素不为数字，那么先看 栈顶，如果栈为空或栈顶元素为('或者栈顶元素为'+ '或'一'并且现有 元素为*'、'/'或又或是现有元素为，那么现有元素进栈；否那么，再对 现有元素进行判断：如果现有元素为)'，运算符出栈直到'('出栈；否那么， 运算符出栈直到栈空或者栈顶元素的优先级低于现有运算符，现有运算符才进 栈。每当有一个运算符出栈，就从数栈中取两个数与运算符一起传递给Operate。 函数,并将函数的返回值压入栈中。循环结束后，将栈中的运算符全部依次输出， 每当有一个运算符出栈，就从数栈中取两个数与运算符一起传递给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)：根据 theta 对 a 和 b 进行'+''、' *'、'/' > 操作In (Test, *TestOp)：假设Test为运算符那么返回true,否那么返回false ReturnOpOrd (op, *TestOp)：假设Test为运算符，那么返回此运算符在数组中的下标precede (Aop, Bop)：根据运算符优先级表返回Aop与Bop之间的优先级 EvaluateExpression (*MyExpression)：用算符优先法对算术表达式求值2. 4程序流程图下面是一个程序流程图，通过它可以更直观的了解程序的原理，程序主要使用两个栈实现主要功能，一开始初始化栈，接下来就是计算算法的设计:计曾图1-1表达式求值算法程序流程图3. 5测试程序说明1 . 一般来说，计算机解决一个具体问题时，需要经过几个步骤：首先要从 具体问题抽象出一个适当的数学模型，然后设计一个解决此数学模型的算法，最 后编出程序，进行测试，调试直至得到想要的答案。对于算术表达式这个程序， 主要利用栈，把运算的先后步骤进行分析并实现简单的运算！为实现算符优先算 法，可以使用两个栈，一个用以寄存运算符，另一个用以寄存操作数和运算结果。2 .演示程序是以用户于计算机的对话方式执行，这需要一个模块来完成使用者与计算机语言的转化。3 .程序块的功能介绍：(1)栈的抽象数据类型定义：ADT Stack数据对象：D=ai | ai EElemSet, i=l, 2,，n, n20数据关系：Rl=<ai-1, ai>|ai-l, ai eD, i=2,，n约定an端为栈顶，ai端为栈底(2 )基本操作：Push (&S, e)初始条件：栈S已存在操作结果：插入元素e为新的栈顶元素Pop (&S, &e)初始条件：栈S已存在且非空操作结果：删除S的栈顶元素，并用e返回其值ADT Stack3程序清单#include"stdio.h"#include"stdlib.h"#include”string.h”#include,math.h"#define true 1#define false 0#define OPSETSIZE 8 typedef int Status;unsigned char Prior88=/运算符优先级表5八，/*1);typedef struct StackCharchar 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;)SF类型的指针Push,返回pSF *Push(SF *s,float f)SF *p=(SF*)malloc(sizeof(SF); p->f=f； p->next=s;