数据结构 表达式值(中缀)实验报告.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返回其值。