数据结构——算术表达式求值算法

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

1、.沈阳航空航天大学课程设计报告课程设计名称：数据结构课程设计课程设计题目：算术表达式求值算法院（系）：计算机学院专业：计算机科学与技术班级：学号：姓名：指导教师：丁国辉完成日期：2013年01月11日word教育资料.目录第1章概要设计11.1题目的内容与要求11.2总体结构1第2章详细设计32.1栈的顺序存储模块32.2进栈模块32.3出栈模块42.4运算模块42.5判断优先级模块52.6处理表达式主体模块6第3章调试分析8第4章运行结果9参考文献11附录（程序清单）12word教育资料.第1章概要设计1.1题目

2、的内容与要求内容：设计程序，其能够求解任意给定算数表达式的值，算数表达式中的操作符来自于集合{+，－，*，＼}，表达式允许包括小括号“（）”，表达式的输入以“#”作为结束标志。要求：1)利用栈结构实现表达式求值算法，即在约定的条件下，正确输入表达式，经过程序的运行之后，给出表达式的值；2)系统利用C语言实现；3)独立完成系统的设计、编码和调试。1.2总体结构本程序主要分为六个模块（主要算法模块图见图1.1）：栈的顺序存储模块、进栈模块、出栈模块、运算模块、判断优先级模块、处理表达式主体模块。栈的顺序存储模块：分别建

3、立两个栈，第一个用来存储运算符，第二个是用来存储数字。进栈模块：运算符和数字分别存储在运算符栈和数字栈中，以便运算时的调用。出栈模块：由于运算的需要，就必须把运算符和数字分别从运算符栈和数字栈中取出来。运算模块：程序在遇到运算符的时候，根据此模块的要求进行运算。判断优先级模块：找出栈顶算符和即将入栈算符的对应的下标，然后根据算符间的优先关系表判断出算符的优先关系。处理表达式主体模块：结合运算模块和判断优先级模块，对表达式进行系统处理，求出算数表达式的值。word教育资料.算术表达式求值算法出栈模块判断优先级模块处理

4、表达式主体模块栈的顺序存储模块运算模块进栈模块图1.1主要算法模块图word教育资料.第2章详细设计在本次课程设计中，我们用到了栈这个重要的数据结构。在实现程序的功能的时候，有很多重要的程序段是涉及栈方面的：有栈的结构建立，入栈，出栈。另外还有就是对表达式进行运算，判断运算符的优先级，对表达式的主体进行处理。重要的程序段如下。2.1栈的顺序存储模块本课程设计是通过栈为载体来实现程序的功能的，因此栈结构的建立是必不可少的。分别建立两个栈，第一个用来存储运算符，第二个用来存储数字。2.2进栈模块主要是把运算符和数字分别

5、存储在运算符栈和数字栈里面。首先判断栈是否满，若不满就进栈，把e插入为新的栈顶元素；否则就追加存储空间。流程图如图2.1所示。FT开始判断栈是否满追加存储空间e进栈为新的栈顶元素结束图2.1进栈模块流程图word教育资料.2.3出栈模块主要是把运算符和数字分别从运算符栈和数字栈中取出来。由于运算的需要，此时就必须把运算符和数字从栈中取出来，即出栈。运算符和数字的出栈，是先取出栈顶元素an。由于取出元素之后，原先的栈顶元素的位置为空了。此时an-1就成了栈顶元素了，所以原先的栈顶指针就减一，指向现在的栈顶元素an-1

6、。第一个函数是运算符的出栈，第二个函数是数字的出栈。首先判断栈是否为空，若栈不空，则删除S的栈顶元素，用e返回其值；否则返回ERROR。流程图如图2.2所示。FT开始判断栈是否空返回ERROR栈顶元素出栈结束图2.2出栈模块流程图2.4运算模块当程序在遇到运算符的时候，就要进行运算。函数中a和b就是代表数字，而theta就是代表运算符。当出栈时栈顶元素是“+”（加），程序就执行加法运算，最后的结果是a和b两数之和；当出栈时栈顶元素是“-”（减），程序就执行减法运算，最后的结果是a和b两数之差；当出栈时栈顶元素是“*

7、”word教育资料.（乘），程序就执行乘法运算，最后的结果是a和b两数之积；当出栈时栈顶元素是“/”（除），程序就执行除法运算，最后的结果是a和b两数之商。函数的返回值就是函数最后的结果。流程图如图2.3所示。default/*-+case开始theta（运算符）a+ba-ba*ba/b错误结束图2.3运算模块流程图2.5判断优先级模块由于我们输入的是四则运算，因此就不得不考虑算符的优先级问题。先调用函数ReturnOpOrd()找出栈顶算符和即将入栈算符的对应的下标，然后再调用precede()函数，根据算符间的

8、优先关系表（如表2.4所示）判断出算符的优先关系：a1a2a1的优先权高于a2。上述函数就是判断优先级的函数。经过运算之后，函数返回值即为优先权高低。word教育资料.a2a1＋－*／（）#＋>><<<>>－>><<<>>*>>>><>>／>>>><>>（<<<<<=）>>>>>>#<<<<<