数据结构的表达式求值.doc

1、课 程 设 计 说 明 书课程名称： 数据结构 设计题目： 表达式求值 院 系： 学生姓名： 学 号： 专业班级： 指导教师： 2011年 6 月 25 日 9 课 程 设 计 任 务 书设计题目表达式求值学生姓名所在院系计科学院专业、年级、班设计要求：1. 计算表达式手工录入，计算结果必须正确2. 支持两位以上的整数和浮点数的运算3. 运算符优先级表可在程序中直接通过代码初始化4. 能够检查表达式是否合法，对于错误的表达式要能够给出错误原因。学生应完成的工作： 设计一个能够计算表达式的程序，要求能够对包含加、减、乘、除、括号运算符的表达式进行计算，并能显示出一定的错误及错误分析。参考文献阅读

2、：严蔚敏 吴伟民 编著数据结构（C语言版） 清华大学出版社 2010年10月（美）克林伯格 编著算法设计 清华大学出版社 2007年6月王晓东 编著算法设计与分析（第三版） 电子工业出版社 2007年5月工作计划：1、第一周的第一天：小组布置设计题目；说明进度安排。2、第一周的第二天：小组审题，查阅资料，进行设计前的必要资料准备。3、第一周的第三天、第四天、第五天：程序编写、上机调试4、第二周的第一天至第三天： 上机调试程序、结果分析。5、第二周的第四天： 撰写设计报告。6、第二周的第五天： 设计答辩及成绩评定。任务下达日期： 2011 年 6 月 13 日 任务完成日期： 2011 年 6月

3、 25 日指导教师（签名）： 学生（签名）： 表达式求值摘 要： 表达式求值是程序设计语言编译中的一个最基本的问题。它的实现是栈应用的一个典型例子。我们使用的是一种简单直观，广为使用的算法“算符优先法”。 要把一个表达式翻译成正确求值的一个机器指令序列，或者直接对表达式求值，首先要能够正确解释表达式。要知道算法四则运算即（1）先乘除，后加减；（2）从左到右；（3）先括号内，后括号外。算法优先级法就是根据这个运算优先级的规定来实现对表达式的编译或解释执行的。任何一个表达式都是由操作数，运算符和界限符组成的，我们称之它们为单词。一般地，操作数既可以是常数也可以是被说明为变量或常量的标识符；运算符可

4、以分为算术运算符，关系运算符和逻辑运算符三类；基本界限符有左右括号和表达式结束符等。关键词： 表达式 栈（出战，入栈） 括号匹配 符号优先级 运算目 录一.设计背景31.1目的 31.2背景 3二.设计方案3三. 方案实施 4 3.1运算 4四. 结果与结论 64.1.运算结果64.2.结论7五. 收获与致谢75.1.收获75.2.致谢7 六参考文献 8八指导教师评语 9一. 设计背景1.1目的 通过课程设计，巩固和加深对栈的理论知识的理解；掌握现实复杂问题的分析和解决方法；提高利用计算机分析解决综合性实际问题的基本能力。1.2背景 “数据结构”是计算机程序设计的重要理论技术基础，它不仅是计算

5、机学科的核心课程，而且已成为其他理科专业的热门选修课。栈是重要的线性结构，从数据结构角度看，栈也是线性表，其特点在于栈的基本操作是线性表操作的子集，它的操作受限的线性表，因此，可称为限定性的数据结构。但从数据类型角度看，它是和线性表大不相同的一类重要的抽象数据类型。由于栈广泛应用在各种软件系统中，因此在面向对象的程序设计中，它是多型数据类型。表达式计算是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。二. 设计方案我负责的部分是求值的过程，使OPTR和OPND分别为运算符栈和运算数栈，算法的基本思想是：（1）首先置操作数栈为栈，表达式起始符“=”为运算符栈的栈底元素。（2）依次读入

6、表达式中的每一个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权后做相应操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和读入的字符均为“=”）。三.方案实施3.1.运算SElemType EvaluateExpression()SqStack OPTR,OPND;SElemType a,b,x, theta;char c; / 存放由键盘接收的字符串 char z6; / 存放整数字符串 int i;float f;InitStack(OPTR);/构造一个运算符栈Push(OPTR,=);/将“=”号压入栈底InitStack(OPND);/构造一个运算数

7、栈c=getchar(); while(c!=|GetTop(OPTR)!=)/栈顶不是“=”号且输入不是“=”号if(In(c)/输入的字符为运算符switch(Precede(GetTop(OPTR),c)case:退栈并将运算结果入栈Pop(OPTR,theta); Pop(OPND,b);Pop(OPND,a); Push(OPND,Operate(a,theta,b);else if(c=0&c=0&c=0&c=0;j-) e1=e1*10; d=d+(zj-48)*e1; if(c=.) c=getchar(); float digit=0.0,e=0.1; while(c=0&c

8、=9) digit=digit+(c-48)*e; e=e*0.1; c=getchar(); f=(float)d+digit; Push(OPND,f);else /不能出现除了“+”，“-”，“*”，“/”以及小数点“.”，“=”和操作数以外的非法字符printf(*n);printf(*出现了非法字符或没有以=结尾!*n);printf(*n);exit(0); return GetTop(OPND); return OK;四. 结果与结论4.1运算结果 1.当出现非法字符或者是没有以“=”结尾时： 图.1 图.1表示运算表达式中不能出现非法字符2.没有以“=”号结尾时 图.2 图.2

9、表示运算表达式要以“=”号结尾结论： 在本次课程设计的程序所支持的表达式进行运算时不能出现非法字符，表达式必须要以“=”号结尾。五. 收获与致谢5.1.收获通过这次课程设计，不仅仅让我知道自己的只是还远远不够，复习了我的语言的相关知识、还巩固了数据结构关于栈的算法的知识，更锻炼了我的意志。5.2.致谢 通过这次的课程设计让我知道了老师说的很对，上课认真听下课多多的动手操作很重要，在这里非常感谢孙老师这半年来交给我们的知识，雅瑶感谢我的组员们特别是组长，让我了解到团结真的很重要。 六. 参考文献1 严蔚敏，吴伟民数据结构（C语言版）清华大学出版社2010年10月2（美）克林伯格算法设计 清华大学

10、出版社 2007年6月王晓东算法设计与分析（第三版） 电子工业出版社 2007年5月指导教师评语：1、课程设计报告：a、内容： 不完整 完整 详细 b、方案设计： 较差 合理 非常合理c、实现： 未实现 部分实现 全部实现 d、文档格式： 不规范 基本规范 规范 2、出勤： 全勤 缺勤 次3、答辩： a、未能完全理解题目，答辩情况较差 b、部分理解题目，部分问题回答正确 c、理解题目较清楚，问题回答基本正确 d、理解题目透彻，问题回答流利 课程设计报告成绩： ，占总成绩比例： 50% 课程设计其它环节成绩：环节名称： 出勤 ，成绩： ，占总成绩比例： 20% 环节名称： 答辩 ，成绩： ，占总成绩比例： 30% 总 成 绩： 指导教师签字：年 月 日