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

《数据结构算术表达式求值课程设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、目录1．前言22．问题描述33．总体设计33.1概要设计33.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（成绩评定表）25251.前言课程设计是实践性教学中的一个重要环节，它以某一课程为基础，它可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们

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

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

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

5、式运算结果，运算符栈、运算数栈、输入字符和主要操作变化过程。测试数据：1024/(4*8)、(20+2)*(6/2)（用于正确性检测的合法输入数据）9/0（用于健壮性检测的非法输入数据）3.总体设计3.1概要设计3.1.1数据结构的选择任何一个表达式都是由操作符，运算符和界限符组成的。我们分别用顺序栈来寄存表达式的操作数和运算符。栈是限定于紧仅在表尾进行插入或删除操作的线性表。为了实现算符优先算法，可以使用两个工作栈。一个称做OPTR，用以寄存运算符；另一个称做OPND，用以寄存操作数或运算结果。首先置操作数栈为空栈，表达式起始符“＃”作为运算符栈的栈底元素，然后

6、依次读入表达式的每个字符，若是操作数则进入OPND栈，若是运算符，则和OPTR栈的栈顶运算符比较优先权后做相应操作，直至整个表达式求值完毕。栈的抽象数据类型定义ADTSqStack{数据对象：D={ai

7、ai∈ElemSet,i=1,2,3……，n,n≥0}数据关系：R1={

8、ai-1,ai∈D,i=1,2,3,……，n}约定其中ai端为栈底，an端为栈顶。操作集合：见如下相关功能函数}ADTSqStack3.1.2相关功能函数运算符栈的功能函数OPTR栈voidOptr_InitStack(Optr_Stack&S1)运算符栈的初始化voidO

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

10、S1,ch