表达式求值算法实现1.docVIP

河南工程学院《数据结构与算法》课程设计 成果报告 表达式求值算法实现 2014 年 12 月 29 日 题 目 表达式求值算法实现 考核项目 考核内容 得分 平时考核 （30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力 系统设计 （20分）分析系统的功能模块 编程调试 （20分）实现系统的各个功能模块，并完成调试 回答问题 （15分）回答老师针对课程设计提出的问题 课程设计报告撰写 （10分）严格按照规范要求完成课程设计报告 源代码 （5分）按照规范要求完成课程设计源代码的排版 总 评 成 绩 指导教师评语： 日期： 年 月 日 目 录 TOC \o 1-3 \h \z \u 1 课程设计目标与任务 1 1.1 课程设计目标 1 1.2 课程设计任务 1 1.3 程序设计思想 1 2 分析与设计 2 2.1 题目分析 2 2.2 算法描述 3 2.3 储存结构设计 4 2.4程序流程图 5 3 程序清单 6 4 测试 14 4.1 测试数据 14 4.2 测试结果分析 15 5 总结 16 参考文献 17 PAGE 5 1 课程设计目标与任务 根据课堂讲授的内容，做相应的自主练习，消化课堂所讲解的内容，通过调试典型例题或习题积累调试c程序的经验，通过完成辅助教材中的编程题，逐渐培养学生的编程能力，用计算机解决实际问题的能力。 1.1 课程设计目标 数据结构课程设计的目标是，通过设计掌握数据结构课程中学到的基本理论和算法并综合运用于解决实际问题中，它是理论与实践相结合的重要过程。设计要求学会如何对实际问题定义相关数据结构，并采用恰当的设计方法和算法解决问题，同时训练进行复杂程序设计的技能和培养良好的程序设计习惯。 1.2 课程设计任务 设计表达式的相关函数库，以便在程序设计中调用。对于输入的表示式（涉及加减乘除，带括弧的混合运算），设计程序求表达式的值。最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来。给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。 1.3 程序设计思想 任何一个表达式都是有操作数、运算符和界限符组成的，我们称为单词。我们把运算符和界限符统称为操作符。为了实现算符优先，我们可以使用两个工作栈。一个可以用来寄存运算符，另外一个可以用来寄存操作符或者运算结果。 首先置操作符栈为空栈表达式起始符为运算符的栈底元素。一次读入每一个字符，若是操作符则进操作符栈，若是运算符则和栈顶运算符比较优先权后作出相应操作，直至整个表达式求值完毕。 2 分析与设计 我们对程序的分析是很重要的步奏，分析程序的要求可以让我们对程序有一定的框架，让我们可以根据分析更好的设计程序，让我们的设计可以根据对程序的分析一步步来完成对程序的设计。所以程序的分析和设计是不可缺少的一部分。 2.1 题目分析 利用栈求解表达式的值。题目涉及加减乘除，带括弧的混合运算。要用栈求解一个表达式,就要将这个表达式翻译成正确求值的一个机器指令序列,即正确解释表达式,了解算术四则混合运算的规则。为实现运算符优先，可以使用两个操作栈，操作栈st,用于存放操作数及运算结果，操作栈op，用于存放。把输入表达式分为两部分数字和操作符分放入两个栈中，符号栈识别符号的优先等级再按照优先等在操作栈中级计算出结果并输出最后的计算结果。 实现表达式的求值：要用栈求解一个表达式,就要将这个表达式翻译成正确求值的一个机器指令序列,即正确解释表达式,了解算术四则混合运算的规则：先乘除,后加减;从左算到右;先括号内,后括号外。再根据这个运算优先的规定来实现对表达式的编译或解释执行.任何一个表达式都是由操作数(st)和操作符(op)组成的，根据四则运算基本法则，在运算的每一步中，任意两个相继出现的操作符op1和op2之间的优先关系最多有以下3种： 1.op1的优先级低于op2 2.op1的优先级等于op2 3.op1的优先级小于op2 为实现运算符优先，可以使用两个操作栈，操作栈st,用于存放操作数及运算结果；操作栈op，用于存放操作符。 2.2 算法描述 1、首先将中缀表达式转换成后缀表达式： (1)从左至右依次扫描中缀表达式的每一个字符，如果是数字字符和“.” ，则直接将它们写入后缀表达式中。 (2)如果遇到的是开括号“（”，则将它压入一个操作符栈中，它表明一个新的计算层次的开始，在遇到和它匹配的闭括号时，将栈中元素弹出并放入后缀表达式中，直到栈顶元素为开括号“