数据结构算术表达式求值课程设计.docx

《数据结构算术表达式求值课程设计.docx》由会员分享，可在线阅读，更多相关《数据结构算术表达式求值课程设计.docx（24页珍藏版）》请在第壹文秘上搜索。

1、1 .前言22 .问题描述33 .总体设计错误!未定义书签。3.1 概要设计错误!未定义书签。3.1.1 数据结构的选择33.1.2 相关功能函数33.1.3 函数模块调用关系432详细设计和编码54 .运行与测试94.1 上机调试94.2 算法时间和空间性能分析104.3 程序运行测试结果115 .总结与心得135.1 设计中难点的总结以及其它解决方案135.2 实验心得146 .用户使用说明167 .参考文献168 .附录1（源代码清单）16.附录2（成绩评定表）251.前言课程设计是实践性教学中的一个重要环节，它以某一课程为根底，它可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊

2、课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。数据结构是一门重要的专业根底课，是计算机理论和应用的核心根底课程。在数据结构的学习和课程设计过程中，我发现它要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，都必须加深对课程根本内容的理解。同时，在程序设计方法以及上机操作等根本技能和科学作风方面受到比拟系统和严格的训练。对于我们专业来说，虽然说对技术要求不是特别高，但是在实际操作过程中，没有足够的专业知识对于编程来说是远远不可以到达要求的，所以对于这次的课程设计，我们必须要通过自己额外补充知识来完成它。在这次的课程设计中我选

3、择的题目是表达式的求值演示。它的根本要求是：以字符序列的形式从终端输入语法正确的，不含变量的表达式。利用算符优先关系，实现对算术四那么混合运算表达式的求值，并演示在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。表达式计算是实现程序设计语言的根本问题之一，也是栈的应用的一个典型例子。设计一个程序，演示用算符优先法对算术表达式求值的过程。深入了解栈和队列的特性，以便在解决实际问题中灵活运用它们，同时加深对这种结构的理解和认识。对于表示出栈在每执行一个过程中都要输出它的变化，这点我认为在编程中是比拟困难的，以我自身的能力，是不可能在规定的时间内完成任务的，所以我参考了很多有价值的书籍来帮助

4、我完成我的程序设计。2 .问题描述（问题分析和任务定义）在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因此，要求设计一个程序，利用栈演示运算符优先法对算术表达式求值的过程，利用算符有限关系，实现对算数混合四那么运算表达式的求值。程序输入：一个算术表达式，由常量、运算符和括号组成（以字符串形式输入，不含变量）。为了简化，操作数只能为浮点数，操作符为“+”、“/、“（、，），用，铲，表示结束。程序输出：表达式运算结果，运算符栈、运算数栈、输入字符和主要操作变化过程。测试数据：1024/（4*8）

5、、（20+2）*（62）（用于正确性检测的合法输入数据）9/0（用于健壮性检测的非法输入数据）3 .总体设计3.1 概要设计3.1.1 数据结构的选择任何一个表达式都是由操作符，运算符和界限符组成的。我们分别用顺序栈来存放表达式的操作数和运算符。栈是限定于紧仅在表尾进行插入或删除操作的线性表。为了实现算符优先算法，可以使用两个工作栈。一个称做OPTR,用以存放运算符；另一个称做OPND,用以存放操作数或运算结果。首先置操作数栈为空栈，表达式起始符“井”作为运算符栈的栈底元素，然后依次读入表达式的每个字符，假设是操作数那么进入OPND栈，假设是运算符，那么和OpTR栈的栈顶运算符比拟优先权后做相

6、应操作，直至整个表达式求值完毕。栈的抽象数据类型定义ADTSqStack数据对象：D=aiaiElemSet,i=1,2,3,n,nO数据关系：Rl=ai-l,aiDj=1,2,3,，11约定其中ai端为栈底，an端为栈顶。操作集合：见如下相关功能函数ADTSqStack3.1.2 相关功能函数运算符栈的功能函数OpTR栈voidOptr_InitStack(Optr_Stack&S1)运算符栈的初始化voidOptr_Push(Optr_Stack&Sl,chare)运算符栈的栈顶插入新的数据元素charOptr_Pop(Optr_Stack&S1)运算符的栈顶元素出栈charOplr_Ge

7、tTop(Optr_Stack&S1)取出运算符栈的栈顶元素voidOptr_DispStack(Optr_Stack&S1)从栈底到栈顶依次输出各运算符运算数栈的功能函数OPND栈voidOpnd_InitStack(Opnd_Stack&S2)运算数栈的初始化intGetTop2(SqStack2&S2)获取运算数栈的栈顶元素voidOplr_Push(Optr_Stack&S1,chare)运算数栈的栈顶插入新的数据元素floatOpnd_Pop(Opnd_Stack&S2)运算数栈的栈顶元素出栈voidOpnd_DispStack(Opnd_Stack&S2)从栈底到栈顶依次输出各运算

8、数算术表达式的相关功能函数charPrecede(charm,charn)运算符的优先级比拟函数floatCalculate(floata,charrheta,floatb)运算函数voidEvaluate(Optr_Stack&S1,Opnd_Stack&S2)判断算术表达式各字符如何入栈函数3.1.3函数模块调用关系主程序模块:式王：栈的建立及初始化模块判断输入是否结束模块Uft-运算数进栈模块运算符优先级比较模块*王Vf,运算符进栈模块运算符运算数出栈模块,0、运算模块3.2详细设计和编码首先本程序定义两个顺序栈：运算符栈（OPTR）和运算数栈（OPND）；OPTR栈定义如下：typed

9、efstructchar*base;char*top;intstacksize;Optr_Stack;OPND栈定义如下：typedefstructfloat*base;算符栈的栈底算符栈的栈顶算符栈的最大长度操作数栈的栈底float*top;操作数栈的栈顶intstacksize;操作数栈的最大长度Opnd_Stack;然后是主要功能函数的详细设计：(1) charPrecede(charm,charn)判断运算符优先权，返回优先权高的算符间的优先关系如下：r-4U+-*/()#+-*/(#函数实现如下：charPrecede(charm,charn)运算符的优先级比拟(if(n=中n=)输

10、入符号为if(m=*m=*)returnV;栈顶元素为此时栈顶符号优先级低，返回Velsereturn否那么，栈顶符号优先级高,返回)elseif(n=*n=7)输入的符号为”*”、“/(if(m=,),m=*,m=,)retum栈顶元素为此时栈顶符号优先级高,返回，elsereturnY;否那么，栈顶符号优先级低,返回)elseif(n=*)returnY;输入的符号为“那么直接返回elseif(n=h)/输入的符号为(if(m=+C)retum1;栈顶元素为“(,此时优先级同，返回“二”elsereturn否那么，栈顶符号优先级高,返回)else输入符号为其他(if(m=罪)return-

11、;栈顶元素为此时优先级同，返回“二”elsereturn少;否那么，栈顶符号优先级高,返回(2) VOidEVaIUate(OPtjStaCk&SIQpncLStack&S2)以字符串形式输入算数表达式,根据是运算符还是运算薪来判断如何入庙函数实现如下：voidEvaluate(Optr_Stack&S1,Opnd_Stack&S2)charc;floatt,e;intn=0,i=l,j=O,k=O,l=O;charchSTACKJNIT_SIZE;ints=1;intflag=0,flag2=0;floatpl,p2;charchi;OPtr_Push(SlW);将考入栈,作为低级运算符Co

12、Utch;c=ch0;coutn病表达式求值的操作过程如下：*nvv”步骤t运算符栈Slt运算数栈S2t字符表达式tt栈操作过程”；While(CPtJGetToP(S1)!=1#)couti+t;Optr_DispStack(Sl);coutttn;Opnd_DispStack(S2);couttt;if(flag=l)flag=O;)if(flag2)k=flag2;flag2=0;)for(l=0;lk;l+)cout,;for(j=k;chj!=,0,;j+)cout=0)小数点前面的数e=float(c-48);n+;if(n=l)t=e;elseif(nl)t=t*10+e;转换小

13、数点前面的局部c=chs+;)if(n=-1)小数点后面的数e=float(c-48);转换小数点后面的局部t=t+e1O;c=chs+;最终将转换后的两局部加起来，转换成浮点数)if(c=.)(n=-l;c=chs+;)if(c=,0,fcfec=9,)c=J)flag2+;gotoas;)if(c,9,)(Opnd_Push(S2,t)；)coutttOpnd.Push(S2tn);)else输入的是运算符n=0；非运算型数据计数器清零SWitCh(PreCede(OPtLGetTOP(Sl),c)比拟运算符的优先级(CaSey:栈顶元素优先级低，那么入栈且继续输入Optr_Push(Sl,c);coutMttOptr_Push(S1,c);c=chs+;breakcase=:/履顶元素优先级相等，脱括号并接