表达式求值的实现3.docx

《表达式求值的实现3.docx》由会员分享，可在线阅读，更多相关《表达式求值的实现3.docx（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、河南工程学院数据结构与算法课程设计成果报告表达式求值的实现2014年12月29日#初始化堆栈73利用该算法对算术表达式3*(7-2)求值操作过程如下:步骤OPTR 栈OPND 栈输入字符主要操作1#3*(7-2)#Push(OPND/3,)2#3士(7-2)#Push(OPTR/*z)3#*3(7-2)#Push(ORNR/C)4#*(3Z-2)#Push(0PND/7)5#*(37二 2)#Rush(OPNR/-/)6#*(-372)#Push(OPND/2,)7#*(-372)#Operate(z77-/2,)8#*(35)#Pop(OPTR)9#*35#Operate(z3,/*5,)1

2、0#15#Return(GetTop2(OPND)表3.求值操作表3程序清单ttinclude ttinclude #include #include #define true 1#define false 0ttdefine OPSETSIZE 8typedef int Status;unsigned char Prior8 8 typedef struct StackChar (char c;struct StackChar *next;SC; /StackChar 类型的结点 SC typedef struct StackFloat (float f;struct StackFloat

3、*next;SF; /StackFloat 类型的结点 SFSC *Push(SC *s, char c)SC类型的指针Push,返回pSC *p=(SC*)malloc(sizeof(SC);p-c=c;p-next=s;return p;SF *Push(SF *s,float f)SF类型的指针Push,返回pSF *p=(SF*)malloc(sizeof(SF);p-f=f；p-next=s;return p;SC *Pop(SC *s)SC *Pop(SC *s)SC类型的指针PopSC *q=s;s=s-next;free (q);return s;SF *Pop(SF *s)S

4、F *Pop(SF *s)SF类型的指针PopSF *q=s;s=s-next;free (q);return s;计算函数计算函数float Operate(float a, unsigned char theta, float b)Operateswitch(theta)case:returncase:returncase:returna*b;case:returna/b;case:returnpow (a, b);iodefault : return 0;char OPSET OPSETSIZE = ，Status In(char Test, char *TestOp)int Find=

5、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; ic!=)if (!In(*c, OPSET) Dr0=*c;strcat (TempData, Dr) ;/字符串连接函数c+;if (In(*c, OPSET) (Data=atof (TempData);字符串转换函数(double)OPND=Push(OPND, Data);strcpy (TempData, 0); els

6、e /不是运算符那么进栈switch (precede(0PTR-c, *c) case 栈顶元素优先级低OPTR=Push (OPTR, *c);12C+；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; /

7、EvaluateExpressionint main(void)(char s128;puts (请输入表达式:);gets(s);puts (该表达式的值为:);printf (/%sb=%gn/z, s, EvaluateExpression (s);system(pause);return 0;134测试4.1测试结果分析图4.1运行结果在程序的运行后出现了：请输入表达式的字样。之后输入了表达式：1+2*3-7 最后的输出了结果：1+2*3-7=0,我们可以很容易的知道计算的结果是正确的。我 们可以初步判断程序满足要求。以上调试结果是正确的。能够实现各个符号优先级先后顺序的运算，根据符

8、号优先级（、）、+、-、*、/ ,如此顺序进行运算，实现了基本表达式运算的 功能。a.可以完成四那么混合运算b.可以完成实数的四那么运算c.可以检查表达式的输入是否正确d.演示表达式的求值的操作过程145总结这次课程设计让我更加了解大一学到的c和这个学期学到的数据结构。这次 的课程设计也让我体会到什么是细节决定成败。在编程上，往往一个小的错误就 会导致整个程序运行不了，自己检查老半天后发现错误总出现在那些小细节。这 让我深深地感觉到编程者最需要的是一颗严谨的心。在程序设计时，我发现了许多自己的缺乏之处，也收获了却多知识。同时也 让我感觉到程序的神奇，一堆字符组合在一起，就能得到我们想要的结果，

9、感觉 程序设计很有意思。15参考文献朱战立.数据结构（第四版）电子工业出版社周海英.马巧梅数据结构与算法设计（第二版）国际工业出版社吴跃.数据结构和算法机械工业出版社严蔚敏.吴伟民数据结构：C语言版清华大学出版社16题目表达式求值的实现考核工程考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、 基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答以下问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版

10、总评成绩指导教师评语:日期:1课程设计目标与任务11.1 课程设计目标11.2 课程设计内容及要求11. 3课程设计思想12分析与设计21.1 题目分析。21.2 ADT 描述42. 3各个模块的主要功能53. 4程序流程图63程序清单94测试144.1测试结果分析145总结15参考文献161课程设计目标与任务1.1 课程设计目标表达式求值是程序设计语言编译中的一个最基本的问题。我们要设计一个算 法能够求表达式的值并且能够确认表达式是否出现语法错误。1.2 课程设计内容及要求表达式求值问题。任何一个表达式都是由操作数（operand）、运算符 （operator）和界限符（delimiter）

11、组成的，我们称之为单词。为实现算符优先 算法，可以使用两个工作栈。一个称作OPTR,用以寄存运算符；另外一个叫做 OPND,用以寄存操作数或运算结果。1. 3课程设计思想这个程序的关键是对数字与运算符的判断和运算符优先级的判断，以及出 栈的运算。建立两个栈，分别存储数字与运算符，栈1存运算符，栈2存数字。 依次读取表达式的字符串，先判断是数字还是运算符，如果是数字不能马上压入 栈2,因为可能是大于10的数字，应该继续循环，如果还是数字，那么利用计算 保存数值，直到指到运算符时停止，将计算后的数字压入栈2。压入运算符之前 先将要压入的与栈顶的运算符优先级相比拟，如果栈顶是（而当前不是）， 那么不

12、需比拟优先级，直接压入；如果栈顶是（，当前是），那么抵消（弹 出（，指向表达式下一个字符）；假设当前的运算符优先级大于栈顶的，那么压 入；假设当前的运算符优先级小于栈内时，弹出栈顶的运算符，同时弹出两组数字, 经过运算符的运算后再重新压到栈内。为了方便判断运算结束，在存储运算符之 前先将#压入栈1中，在输入表达式时以“旷 结束，所以可以以运算符=并且栈1顶=#，来结束运算，弹出栈2的数值，即为表达式求值的最终 结果。2分析与设计2.1 题目分析。设计一个程序，演示用算符优先法对算术表达式求值的过程。利用算符优先 关系，实现对算术四那么混合运算表达式的求值。(1)输入的形式：表达式，例如2*(3

13、+4)包含的运算符只能有(2)输出的形式:运算结果，例如2*(3+4)=14；(3)程序所能到达的功能：对表达式求值并输出系统设计1.程序结构模型ADT Stack数据对象：D=ai|ai ElemSet,i=l,2,n,nO数据关系：Rl=| ai-lzai e D,i=2/-,n约定an端为栈顶，ai端为栈底基本操作：Push(&Sze)初始条件：栈S已存在操作结果：插入元素e为新的栈顶元素Pop(&S,&e)初始条件：栈S已存在且非空操作结果：删除S的栈顶元素，并用e返回其值ADT Stack2判断操作数的函数isnum()判断当前所指字符是否属于数字，是就返回1，不是返回O。3求运算符

14、优先级函数priority()为了方便判断运算符优先级，先利用switch函数将不同的运算符返回不同 的整型数字，再根据数字的大小判断优先级。+、优先级相同，返回相 同数字，*、 /也是。4表达式求值函数infix_value()此函数是直接按照设计思路完成问题要求的函数，其中要调用到判断操作符 的函数isrwm()和求运算符优先级的函数priority()o循环结束弹出栈2的数值， 并返回。5主函数main()定义一个数组存储表达式整个字符串，将返回的数值直接赋到浮点型的 result, 输出 resulto6两个栈的函数设计：栈的初始化函数charlnit_SeqStack()lnit_S

15、eqStack()判栈空Empty_SeqStack()charEmpty_SeqStack()入栈函数Push_SeqStack()charPush_SeqStack()出栈函数Pop_SeqStack()charPop_SeqStack()取栈顶函数GetTop_SeqStack()charGetTop_SeqStack()7.算法的操作步骤：(1)初始化算符S1,数字栈S2;,将#，压入算符栈S1中。读表达式字符=/。(3)当栈顶为并且w也是#，时结束；否那么循环做以下步骤：(3-1)如果w是数字，存储到m,再经过计算存储到num中。m=w-0 ;num=num*pow(10,n)+m;

16、n+;读下一个字符=w,如果是运算符，那么跳出循 环；转3-2。(3-2) w假设是运算符,那么:(3-2-1)如果栈顶为(并且w为D 那么(出栈，读下一个 字符。W；转(3)。(3-2-2)如果栈顶为(或者栈顶优先级小于w优先级，那么 W入栈，读下一个字符二W；转(3)。否那么：从算符栈中出栈，并从数字栈中弹出两组数字进行运算，将结果重新压入数字栈，转(3)。2. 2 ADT描述ADT Stack数据对象：D=6Z/ | a eElemSet, i=l, 2, , n, n = 0数据对象：,n约定明端为栈顶，端为栈底。基本操作：InitStack(&S)操作结果：构造一个空栈S。GetTo

17、p (S)初始条件：栈S已存在。操作结果：用P返回S的栈顶元素。Push (&.S, ch)初始条件：栈S已存在。操作结果：插入元素ch为新的栈顶元素。Pop (&S)初始条件：栈S已存在。操作结果：删除S的栈顶元素。In(ch)操作结果：判断字符是否是运算符，运算符即返回1。Precede (cl, c2)初始条件：cl, c2为运算符。操作结果：判断运算符优先权，返回优先权高的。Operate (a, op, b)初始条件：a, b为整数，op为运算符。操作结果：a与b进行运算，op为运算符，返回其值。num(n)操作结果：返回操作数的长度。EvalExpr ()初始条件：输入表达式合法。

18、操作结果：返回表达式的最终结果。ADT Stack2. 3各个模块的主要功能*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)：根据

19、运算符优先级表返回Aop与Bop之间的优先级Evaluat eExpress ion (*MyExpression)：用算符优先法对算术表达式求值 算法伪代码如下：char Precede(char cl, char c2)static char array49 = switch (cl)(/* i为下面array的横标*/case + : i=0;break;case - ： i=l;break;case :i=2;break;case / : i=3;break;case ( : i=4;break;case ) : i=5;break;case : i=6;break;switch(c2)(/* j为下面array的纵标*/case + : j=0;break;case - : j=l;break;case :j=2;break;case / : j=3;break;case ( : j=4;break;case: j=5;break;case : j=6;break;return (array 7*i+j) ; /* 返回运算符 array 7*i+j为对应的 cl, c2 优先关系*/2. 4程序流程图1. Precede (char cl, char c2)判断运算符优先权，返回优先权高的。算符间的优先关系如下：+*/()+*/(6