表达式求值课程设计.docVIP

. . . . 数据结构课程设计 设计说明书 算术表达式求值问题 学生姓名 白子健 学号 1318014057 班级 计本1302 成绩 指导教师 李军 计算机科学与技术系 2015年9月10日 数据结构课程设计评阅书 题 目 算术表达式求值算法的实现 学生姓名 白子健 学号 1318014057 指导教师评语及成绩 成绩： 教师签名： 年 月 日 教研室意见 总成绩： 室主任签名： 年 月 日 课程设计任务书 2015—2016学年第一学期 专业： 计算机科学与技术 学号： 1318014057 姓名： 白子健 课程设计名称： 课程设计Ⅰ---数据结构课程设计 设 计 题 目： 表达式求值算法的实现 完 成 期 限：自 2015 年 9 月 1 日至 2015 年 9 月 12 日共 2 周 设计内容及要求: 算术表达式求值是程序设计语言编译中的一个基本问题，通过栈实现表达式运算优先级的匹配和运算。用C/C++语言编程实现任意算术表达式的求值，设计内容要求如下： （1）表达式共有三种基本表示方法：前缀法、中缀法、后缀法。从表达式的这三种基本方法中任选一种方法进行编程求值。 （2）分析所选的表示方法，根据选定的表示方法确定对应的存储结构和相关算法。 （3）算法要能正确处理算术运算的优先级规则，即: 先括号内，后括号外的规则；运算先乘除，后加减；同级运算从左到右。 如下表达式： 50+（6*3+2） 要求： (1)用C/C++语言编写一个程序将这组学生成绩输入到计算机中，数据运算的存储逻辑结构为栈。 (2)程序要能正确处理表达式的优先级、输出正确运算结果。 最终设计成果形式为： 设计好的软件一套； 撰写一份课程设计说明书一份，打印并装订成册。 指导教师（签字）： 教研室主任（签字）： 批准日期： 年 月 日 目 录 1 课题描述…………………………………………………………………………………………1 2 设计思路…………………………………………………………………………………………2 3 算法设计…………………………………………………………………………………………3 4 程序代码…………………………………………………………………………………………5 5 测试及分析……………………………………………………………………………………..12 6 总结……………………………………………………………………………………………..13 参考文献…………………………………………………………………………………………..13 1 课题描述 表达式求值是程序设计语言编译中的一个最基本问题。表达式求值在计算机中的实现是栈结构在计算机中的一个典型应用。这里使用“算符优先算法”实现表达式求值。 要把一个表达式翻译成正确求值的一个机器指令序列，或者直接对表达式求值，首先要能够正确解释表达式。例如对表达式求值： 50+（6*3+2） 首先要了解算术四则运算的规则。即：先算括号内，后算括号外；先乘除后加减；同级运算顺序从左到右；所以，这个表达式的运算顺序为： 50+（6*3+2）=50+（18+2）=50+20=70 算符优先算法就是根据这个运算优先关系来编译或者解释执行的。 2 设计思路 2.1表达式的输入： 表达式从键盘输入，存入字符串数组中。 2.2运算的实现： 任何一个表达式都是由操作数（operand）、运算符（operator）和界限符（delimiter）组成的。可以把运算符和界限符统称为算符，根据算术运算规则，在运算的每一步中，任意两个相继出现的算符opt1和opt2之间的优先关系至多是下面三种关系之一： opt1opt2，即opt1的优先级低于opt2； opt1=opt2，即opt1的优先级等于opt2； opt1opt2，即opt1的优先级高于opt2。 表1定义了算符间的优先关系： Opt2 Opt1 + - * / （ ） # + - * / （ = NULL ） NULL # NULL = 表1 输入的表达式（包含运算符和操作数）以字符串的形式输入，故需要一个字符串数组存储键盘的输入。在对输入的表达式求值前，应先检查输入的合法性