数据结构表达式求值(中缀)实验报告.doc
文本预览下载声明
江西理工大学软件学院
《数据结构》课程设计报告
2012—2013学年第一学期
课程名称 数 据 结 构
设计题目 表达式求值
专业班级
姓 名
学 号
指导教师
2012年 11 月 30日
目 录
一．设计题目…………………………………………………….…..……………..3
二．需求分析………………………………………………..………………..…….3
2.1问题描述……………………………………………………………..……..3
2.2表达式程序分析…………………………………………………..………..3
三．概要设计…………………………………………………..……..…………….3
3.1基本思想……………………………………………………..……………..3
3.2栈的抽象数据类型定义…………………………………..………………..4
四．基本算法…………………………………………………………….....………4
4.1基本操作思想………………………………………………………………4
4.2基本操作……………………………………………………………………5
五．测试结果………………………………………………………………………7
六．源代码…………………………………………………………………………8
七．心得体会………………………………………………………………………12
一 设计题目
三 概要设计
3.1 基本思想（中缀表达式求值）
要把一个表达式翻译成正确求值的一个机器指令序列，或者直接对表达式求值，首先要能够正确解释表达式，要了解算术四则运算的规则即：
a先乘除后加减；
b从左到右计算；
c 先括号内，后括号外。
下表定义的运算符之间的关系:
b
a + - * / （ ） # + _ * / ( = ) # = 为了实现运算符有限算法，在程序中使用了两个工作栈。分别是：运算符栈OPTR,操作数栈OPND.
基本思想：
首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素；
依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈得栈顶运算符比较优先级后作相应操作。若大于栈顶元素优先级则如栈，若小于栈顶元素优先级则退出和OPND得操作数进行计算，并把计算结果如OPND栈。直至整个表达式求值完毕（即OPND栈的栈顶元素和当前读入的字符均为“#”）。
3.2 栈的抽象数据类型的定义：
ADT Stack{
数据对象：D={ai| ai∈IntegerSet，i=1，2，…，n，n≥0}
数据关系：R1={〈ai-1，ai〉|ai-1， ai∈D， i=1，2，…，n}
约定an端为栈顶，ai端为栈底
四．操作算法
4.1基本操作思想：
InitStack(S)
操作结果：构造一个空栈S。
DestroyStack(S)
初始条件：栈S已存在。
操作结果：栈S被销毁。
ClearStack(S)
初始条件：栈S已存在。
操作结果：将S清为空栈。
StackEmpty（S）
初始条件：栈S已存在。
操作结果：若栈S为空栈，则返回True，否则返回False。
StackLength（S）
初始条件：栈S已存在。
操作结果：返回S的元素个数，即栈的长度。
GetTop（S，e）
初始条件：栈S已存在且非空。
操作结果：用e返回S的栈顶元素。
Push（S，e）
初始条件：栈S已存在。
操作结果：插入元素e为新的栈顶元素。
Pop（S，e）
初始条件：栈S已存在且非空。
操作结果：删除S的栈顶元素，并用e返回其值。
StackTraverse（S，visit（））
初始条件：栈S已存在且非空。
操作结果
显示全部