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

1目录1．前言·································································································22．问题描述·································································································33．总体设计··········································································错误!未定义书签。3.1概要设计······································································错误!未定义书签。3.1.1数据结构的选择················································································33.1.2相关功能函数···················································································33.1.3函数模块调用关系·············································································43.2详细设计和编码·····················································································54．运行与测试······························································································94.1上机调试····························································································94.2算法时间和空间性能分析·····································································104.3程序运行测试结果···············································································115.总结与心得·····························································································135.1设计中难点的总结以及其它解决方案·····················································135.2实验心得···························································································146.用户使用说明·························································································167.参考文献································································································168.附录1（源代码清单）············································································169.附录2（成绩评定表）············································································2521.前言课程设计是实践性教学中的一个重要环节，它以某一课程为基础，它可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。《数据结构》是一门重要的专业基础课，是计算机理论和应用的核心基础课程。在数据结构的学习和课程设计过程中，我发现它要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，都必须加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。对于我们专业来说，虽然说对技术要求不是特别高，但是在实际操作过程中，没有足够的专业知识对于编程来说是远远不可以达到要求的，所以对于这次的课程设计，我们必须要通过自己额外补充知识来完成它。在这次的课程设计中我选择的题目是表达式的求值演示。它的基本要求是：以字符序列的形式从终端输入语法正确的，不含变量的表达式。利用算符优先关系，实现对算术四则混合运算表达式的求值，并演示在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。表达式计算是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。设计一个程序，演示用算符优先法对算术表达式求值的过程。深入了解栈和队列的特性，以便在解决实际问题中灵活运用它们，同时加深对这种结构的理解和认识。对于表示出栈在每执行一个过程中都要输出它的变化，这点我认为在编程中是比较困难的，以我自身的能力，是不可能在规定的时间内完成任务的，所以我参考了很多有价值的书籍来帮助我完成我的程序设计。32.问题描述（问题分析和任务定义）在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因此，要求设计一个程序，利用栈演示运算符优先法对算术表达式求值的过程，利用算符有限关系，实现对算数混合四则运算表达式的求值。程序输入：一个算术表达式，由常量、运算符和括号组成（以字符串形式输入，不含变量）。为了简化，操作数只能为浮点数，操作符为“+”、“-”、“*”、“/”、“（”、“）”，用“#”表示结束。程序输出：表达式运算结果，运算符栈、运算数栈、输入字符和主要操作变化过程。测试数据：1024/(4*8)、(20+2)*(6/2)（用于正确性检测的合法输入数据）9/0（用于健壮性检测的非法输入数据）3.总体设计3.1概要设计3.1.1数据结构的选择任何一个表达式都是由操作符，运算符和界限符组成的。我们分别用顺序栈来寄存表达式的操作数和运算符。栈是限定于紧仅在表尾进行插入或删除操作的线性表。为了实现算符优先算法，可以使用两个工作栈。一个称做OPTR，用以寄存运算符；另一个称做OPND，用以寄存操作数或运算结果。首先置操作数栈为空栈，表达式起始符“＃”作为运算符栈的栈底元素，然后依次读入表达式的每个字符，若是操作数则进入OPND栈，若是运算符，则和OPTR栈的栈顶运算符比较优先权后做相应操作，直至整个表达式求值完毕。栈的抽象数据类型定义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端为栈顶。操作集合：见如下相关功能函数}ADTSqStack3.1.2相关功能函数运算符栈的功能函数OPTR栈voidOptr_InitStack(Optr_Stack&S1)运算符栈的初始化voidOptr_Push(Optr_Stack&S1,chare)运算符栈的栈顶插入新的数据元素4charOptr_Pop(Optr_Stack&S1)运算符的栈顶元素出栈charOptr_GetTop(Optr_Stack&S1)取出运算符栈的栈顶元素voidOptr_DispStack(Optr_Stack&S1)从栈底到栈顶依次输出各运算符运算数栈的功能函数算术表达式的相关功能函数charPrecede(charm,charn)运算符的优先级比较函数floatCalculate(floata,charrheta,floatb)运算函数voidEvaluate(Optr_Stack&S1,Opnd_Stack&S2)判断算术表达式各字符如何入栈函数3.1.3函数模块调用关系OPND栈voidOpnd_InitStack(Opnd_Stack&S2)运算数栈的初始化intGetTop2(SqStack2&S2)获取运算数栈的栈顶元素voidOptr_Push(Optr_Stack&S1,chare)运算数栈的栈顶插入新的数据元素floatOpnd_Pop(Opnd_Stack&S2)运算数栈的栈顶元素出栈voidOpnd_DispStack(Opnd_Stack&S2)从栈底到栈顶依次输出各运算数5主程序模块栈的建立及初始化模块判断输入是否结束模块判断字符类型模块输入结束输出结果运算数进栈模块运算符优先级比较模块运算符进栈模块运算符运算数出栈模块运算模块3.2详细设计和编码首先本程序定义两个顺序栈：运算符栈（OPTR）和运算数栈（OPND）；OPTR栈定义如下：typedefstruct{char*base;//算符栈的栈底char*top;//算符栈的栈顶intstacksize;//算符栈的最大长度}Optr_Stack;OPND栈定义如下：typedefstruct{float*base;//操作数栈的栈底float*top;//操作数栈的栈顶intstacksize;//操作数栈的最大长度}Opnd_Stack;然后是主要功能函数的详细设计：（1）charPrecede(charm,charn)判断运算符优先权，返回优先权高的算符间的优先关系如下：θ1θ2+-*/（）#+-6函数实现如下：charPrecede(charm,charn)//运算符的优先级比较{if(n=='+'||n=='-')//输入符号为+、-{if(m=='('||m=='#')return'';//栈顶元素为(、#,此时栈顶符号优先级低，返回elsereturn'';//否则，栈顶符号优先级高,返回}elseif(n=='*'||n=='/')//输入的符号为*、/{if(m==')'||m=='*'||m=='/')return'';//栈顶元素为)、*、/,此时栈顶符号优先级高，返回elsereturn'';//否则，栈顶符号优先级低,返回}elseif(n=='(')return'';//输入的符号为(,则直接返回elseif(n==')')//输入的符号为){if(m=='(')return'=';//栈顶元素为(,此时优先级同，返回=elsereturn'';//否则，栈顶符号优先级高,返回}else//输入符号为其他{if(m=='#')return'=';//栈顶元素为#,此时优先级同，返回=elsereturn'';//否则，栈顶符号优先级高,返回}}（2）voidEvaluate(Optr_Stack&S1,Opnd_Stack&S2)以字符串形式输入算数表达式，根据是运算符还是运算数来判断如何入栈函数实现如下：voidEvaluate(Optr_Stack&S1,Opnd_Stack&S2){charc;floatt,e;intn=0,i=1,j=0,k=0,l=0;charch[STACK_INIT_SIZE];ints=1;intflag=0,flag2=0;floatp1,p2;*