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

沈阳航空航天大学 课课 程程 设设 计计 报报 告告 课程设计名称 数据结构课程设计数据结构课程设计 课程设计题目 算术表达式求值算法算术表达式求值算法 院 系 计算机学院 专 业 计算机科学与技术 班 级 学 号 姓 名 指导教师 丁国辉 完成日期 2013年01月11日 沈阳航空航天大学课程设计报告 目目 录录 第第 1 章章 概要设计概要设计 1 1 1 题目的内容与要求 1 1 2 总体结构 1 第第 2 章章 详细设计详细设计 3 2 1 栈的顺序存储模块 3 2 2 进栈模块 3 2 3 出栈模块 4 2 4 运算模块 4 2 5 判断优先级模块 5 2 6 处理表达式主体模块 6 第第 3 章章 调试分析调试分析 8 第第 4 章章 运行结果运行结果 9 参考文献参考文献 11 附附 录 程序清单 录 程序清单 12 沈阳航空航天大学课程设计报告 第 1 章 概要设计 0 第 1 章 概要设计 1 1 题目的内容与要求题目的内容与要求 内容 设计程序 其能够求解任意给定算数表达式的值 算数表达式中的操 作符来自于集合 表达式允许包括小括号 表达式的输入 以 作为结束标志 要求 1 利用栈结构实现表达式求值算法 即在约定的条件下 正确输入表达 式 经过程序的运行之后 给出表达式的值 2 系统利用 C 语言实现 3 独立完成系统的设计 编码和调试 1 2 总体结构总体结构 本程序主要分为六个模块 主要算法模块图见图 1 1 栈的顺序存储模块 进栈模块 出栈模块 运算模块 判断优先级模块 处理表达式主体模块 栈的 顺序存储模块 分别建立两个栈 第一个用来存储运算符 第二个是用来存储数 字 进栈模块 运算符和数字分别存储在运算符栈和数字栈中 以便运算时的调 用 出栈模块 由于运算的需要 就必须把运算符和数字分别从运算符栈和数字 栈中取出来 运算模块 程序在遇到运算符的时候 根据此模块的要求进行运算 判断优先级模块 找出栈顶算符和即将入栈算符的对应的下标 然后根据算符间 的优先关系表判断出算符的优先关系 处理表达式主体模块 结合运算模块和判 断优先级模块 对表达式进行系统处理 求出算数表达式的值 沈阳航空航天大学课程设计报告 第 1 章 概要设计 1 算术表达式求值算法 出 栈 模 块 判 断 优 先 级 模 块 处 理 表 达 式 主 体 模 块 栈 的 顺 序 存 储 模 块 运 算 模 块 进 栈 模 块 图图 1 1 主要算法模块图主要算法模块图 沈阳航空航天大学课程设计报告 第 2 章 详细设计 2 第 2 章 详细设计 在本次课程设计中 我们用到了栈这个重要的数据结构 在实现程序的功能 的时候 有很多重要的程序段是涉及栈方面的 有栈的结构建立 入栈 出栈 另外还有就是对表达式进行运算 判断运算符的优先级 对表达式的主体进行处 理 重要的程序段如下 2 1 栈的顺序存储模块栈的顺序存储模块 本课程设计是通过栈为载体来实现程序的功能的 因此栈结构的建立是必不 可少的 分别建立两个栈 第一个用来存储运算符 第二个用来存储数字 2 2 进栈模块进栈模块 主要是把运算符和数字分别存储在运算符栈和数字栈里面 首先判断栈是否 满 若不满就进栈 把 e 插入为新的栈顶元素 否则就追加存储空间 流程图如 图 2 1 所示 FT 开始 判断栈是否满 追加存储空间e 进栈为新的栈顶元素 结束 图图 2 12 1 进栈进栈模块流程图模块流程图 沈阳航空航天大学课程设计报告 第 2 章 详细设计 3 2 3 出栈模块出栈模块 主要是把运算符和数字分别从运算符栈和数字栈中取出来 由于运算的需要 此时就必须把运算符和数字从栈中取出来 即出栈 运算符和数字的出栈 是先 取出栈顶元素an 由于取出元素之后 原先的栈顶元素的位置为空了 此时an 1就 成了栈顶元素了 所以原先的栈顶指针就减一 指向现在的栈顶元素an 1 第一个 函数是运算符的出栈 第二个函数是数字的出栈 首先判断栈是否为空 若栈不 空 则删除S的栈顶元素 用e返回其值 否则返回ERROR 流程图如图2 2所示 FT 开始 判断栈是否空 返回 ERROR栈顶元素出栈 结束 图图2 22 2 出栈出栈模块流程图模块流程图 2 4 运算模块运算模块 当程序在遇到运算符的时候 就要进行运算 函数中a和b就是代表数字 而 theta就是代表运算符 当出栈时栈顶元素是 加 程序就执行加法运算 最后的结果是a和b两数之和 当出栈时栈顶元素是 减 程序就执行减法 运算 最后的结果是a和b两数之差 当出栈时栈顶元素是 乘 程序就执 沈阳航空航天大学课程设计报告 第 2 章 详细设计 4 行乘法运算 最后的结果是a和b两数之积 当出栈时栈顶元素是 除 程 序就执行除法运算 最后的结果是a和b两数之商 函数的返回值就是函数最后的 结果 流程图如图2 3所示 default case 开始 theta 运算符 a b a b a b a b错误 结束 图图2 32 3 运算运算模块流程图模块流程图 2 5 判断优先级模块判断优先级模块 由于我们输入的是四则运算 因此就不得不考虑算符的优先级问题 先调用 函数ReturnOpOrd 找出栈顶算符和即将入栈算符的对应的下标 然后再调用 precede 函数 根据算符间的优先关系表 如表2 4所示 判断出算符的优先关系 a1a2 a1的优先权高于 a2 上述函数就是判断优先级的函数 经过运算之后 函数返回值即为优先权高 低 沈阳航空航天大学课程设计报告 第 2 章 详细设计 5 a2 a1 T 开始 输入表达式 c GetTop OPTR e e 不是算符 数字进 OPND 栈 存储数 字的栈 运算符进 OPTR 栈 存储算符 的栈 调用 ReturnOpOrd 和 precede 函数判 断优先关系 Pop OPT R x c 出 栈 Pop OPTR theta Pop OPND b Pop OPND a Push OPND Operate a theta b return GetTop O PND d d 结束 图图 2 52 5 处理表达式主体处理表达式主体模块模块流程图流程图 沈阳航空航天大学课程设计报告 第 3 章 调试分析 7 第 3 章 调试分析 1 问题 由于输入时的疏忽遗漏了 等 编译时出现错误 解决方法 通过编译器的错误提示进行修改 添加一些遗漏的信息 2 问题 在运行时提示库函数名为未标识符 解决方法 通过编译器的错误提示进行修改 缺少头文件 添加所需的头文件 3 问题 输出的数只能在97以内 而且只能输入输出整数 不能实现输入输出 小数 当输入小数时出现错误 解决方法 规范输入输出格式 4 问题 操作数和运算符在一起发生冲突 当混合输入数据和运算符 出现 异常 没有结果 解决方法 使用两个工作栈 一个存储数字 一个存储运算符 沈阳航空航天大学课程设计报告 第 4 章 使用说明 8 第 4 章 运行结果 运行操作及结果 1 显示输入表达式 以 号结束 沈阳航空航天大学课程设计报告 第 4 章 使用说明 9 2 正确输入表达式 以 号结束 就能得到表达式的值 沈阳航空航天大学课程设计报告 参考文献 10 参考文献 1 严蔚敏 吴伟明 数据结构 C 语言版 M 北京 清华大学出版社 2007 2 王敬华 林萍 张清国 C 语言程序设计教程 M 第二版 北京 清华大学 出版社 2009 8 3 吴海燕 任午令 章志勇 数据结构 M 杭州 浙江大学出版社 2011 6 4 胡圣荣 周霭如 罗穗萍 数据结构教程与题解 M 北京 清华大学出版社 2011 9 5 谭浩强 C 程序设计试题汇编 M 北京 清华大学出版社 2006 3 6 李兵 崔虹燕 马晓亭 C 语言程序设计 M 北京 科学出版社 2011 沈阳航空航天大学课程设计报告 附录 11 附 录 程序清单 include include include int InitStack StackChar char OPSET 7 float EvaluateExpression char k StackChar OPTR StackFloat OPND char T 20 float Data a b char theta c x str 2 沈阳航空航天大学课程设计报告 附录 12 char e float d InitStack OPTR Push OPTR InitStack OPND c k strcpy T 0 while c GetTop OPTR e e if In c OPSET str 0 c str 1 0 strcat T str c if In c OPSET Data float atof T Push OPND Data strcpy T 0 else switch precede GetTop OPTR e e c case Pop OPTR theta Pop OPND b Pop OPND a Push OPND Operate a theta b break return GetTop OPND d d float Operate float a unsigned char theta float b switch theta case return a b case return a b case return a b case 沈阳航空航天大学课程设计报告 附录 14 return a b default return 0 int In char Test char TestOp int ReturnOpOrd char op char TestOp int i for i 0 i 7 i if op TestOp i return i return 0 char precede char A char B return str ReturnOpOrd A OPSET ReturnOpOrd B OPSET void main char k 100 float result printf 输入表达式 以 号结束 n gets k result EvaluateExpression k printf 2f n result 沈阳航空航天大学课程设计报告 15 课程设计总结 课程设计总结 这次数据结构课程设计 从理论到实践 让我对数据结构有了更深刻的认 识 也学到了很多东西 不仅巩固了以前所学过的知识 而且还学到了很多书 本上所没有的内容 我在此次课程设计中深刻体会到了要写好一个程序必须弄 清它的最基本的思路 除此之外要有算法思路 会写一些基本函数 编程不像 做其它事 它要求编程人员有非常缜密的思维 很好的整体把握能力和很好的 调试程序的能力等 也要特别注重细节 我在编写程序过程中遇到了很多的问 题 一些基本的函数应用不熟练 让我发现了自己的知识的匮乏 掌握的不够 牢固 懂得了只学书本上的东西是远远不够的 只有把所学的理论知识与实践 相结合起来 才能真正的学到东西 才能提高自己的实际动手能力和独立思考 能力 在程序运行成功的时候 我的心里是非常喜悦的 这些天的努力终于有了 回报 在以后的学习过程中要多了解一