数据结构课程设计告-表达式求值问题.doc

《数据结构》 课 程 设 计 报 告 题 目： 表达式求值问题 学院（系）： 数学与计算科学学院 班 级： 11级信息与计算科学4班 学生学号： 1107020432 姓 名： 杨宇红 指导教师： 彭叶辉 2013年 6月28 日 目 录 摘要………………………………………………………………………2 一、需求分析……………………………………………………………2 二、概要设计……………………………………………………………2 三、详细设计……………………………………………………………5 1、预定义和定义结构体 ……………………………………………………5 2、基本操作的算法描述 ……………………………………………………5 3、判断输入的运算符是否在运算符允许范围内 …………………………………6 4、比较运算符间的优先关系 …………………………………………………7 5、确定两运算数之间的运算符后进行运算，并返回两操作数运算后的结果 ………7 6、提示用户按照要求输入正确的表达式 ………………………………………8 7、遵循算术运算规则求解表达式 ……………………………………………9 8、输出运算结果 …………………………………………………………9 四、设计和调试分析……………………………………………………9 五、用户手册……………………………………………………………10 六、测试结果……………………………………………………………10 七、设计心得……………………………………………………………12八、参考文献……………………………………………………………12九、附录…………………………………………………………………12 摘 要 通过数据结构这门课程，我们较深入的了解到了栈，栈是一种重要的线性结构，它广泛应用于各种软件系统中，因此在面向对象的程序设计中，它们是多型数据类型。 栈是限定仅在表尾进行插入或删除操作的线性表。因此，栈又称为后进先出的线性表。它的这个特点可以应用于多种实际问题，比如数制转换、括号匹配的检验、行编辑程序、迷宫求解以及表达式求值等问题。 本次试验我们将探索表达式求值问题，表达式求值是程序设计语言编译中的一个最基本的问题，它的实现是栈应用的又一个典型的例子。通过实验我们能用程序计算带括号的表达式，在过程中更深入的了解到栈的基本操作。 关键词：栈、先进后出、带括号的表达式、表达式求值、一、需求分析 本程序用于解决一个可以带括号的表达式求值的问题，要运用到栈，而且会用到一种简单直观，广为使用的算法，通常称为“算符优先法”。进行表达式求值首先要了解算术四则运算的规则。即：(1）先乘除，后加减；（2）从左算到右；（3）先括号内后括号外；算符优先法根据这个算符优先关系的规定来实现对表达式的编译或解释执行的。任何一个表达式都是由操作数、运算符和界限符组成。 为实现算符优先算法，可以使用两个工作栈。一个称作OPTR，用以寄存运算符；另一个称作OPND，用以寄存操作数或运算结果。算法的基本思想是：（1）首先置操作数栈为空栈，表达式起始符“#”为运算符的栈底元素；（2）一次读入表达式中每个字符，若是操作数则进OPND栈若是运算符则和OPTR栈的栈顶元素比较优先权后做相应操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为“#”）。 界面要求使用VC++6.0的运行环境。 二、概要设计 1、栈抽象数据类型的定义如下： ADT Stack{数据对象：D={ai|ai∈ElemSet, i=1,2, …,n, n≥0}数据关系：R1={ai-1,ai|ai-1,ai∈D, i=1,2, …,n } 约定an端为栈顶，a1端为栈底。基本操作： InitStack( S ) 操作结果：构造一个空栈S。 DestroyStack ( S ) 初始条件：栈S已存在。 操作结果：销毁栈S。 ClearStack( S ) 初始条件：栈S已存在。 操作结果：将S清为空栈。 StackEmpty( S ) 初始条件：栈S已存在。 操作结果：若S为空栈，则返回TRUE，否则返回FALSE。 StackLength( S ) 初始条件：栈S已存在。 操作结果：