算术表达式求值-数据结构实验报告.doc

清华大学数据结构课程实验报告 （20 -20 学年 第 学期） 报告题目： 算术表达式求值 任课老师： 专　　业： 学　　号： 姓　　名： 二0一 年 月 日 摘要：现代科学技术高速发展，各种高科技产品频频问世，而各种技术的基础都离不开基本的表达式求值，它虽然简单，但却是任何复杂系统的基本执行操作。栈是一种重要的线性结构，从数据结构的角度看，它是一种特殊的线性表，具有先入先出的特点。而算符优先法的设计恰巧符合先入先出的思想。故我们基于栈这种数据结构，利用算符优先法，来实现简单算术表达式的求值。 关键字：算符优先法；算术表达式；数据结构；栈 一、课题概述 1、问题描述 一个算术表达式是由运算数、运算符、界限符组成。假设操作数是正整数，运算符只含有加“+”、减“-”、乘“*”、除“/”四种二元运算符，界限符有左括号“（”、右括号“）”和表达式起始、结束符“#”。利用算符优先法对算术表达式求值。 2、设计目的 （1）通过该算法的设计思想，熟悉栈的特点和应用方法； （2）通过对算符优先法对算术表达式求值的算法执行过程的演示，理解在执行相应栈的操作时的变化过程。 （3）通过程序设计，进一步熟悉栈的基本运算函数； （4）通过自己动手实现算法，加强从伪码算法到C语言程序的实现能力。 3、基本要求： （1）使用栈的顺序存储表示方式； （2）使用算符优先法； （3）用C语言实现； （4）从键盘输入一个符合要求的算术表达式，输出正确的结果。 4、编程实现平台 Microsoft Visual C++ 6.0 二、设计思路及采取方案 1、设计思路： 为了实现算符优先法，可以使用两个工作栈。一个称做OPTR，用以寄存运算符；另一个称做OPND，用以寄存操作数或运算结果。 算法的基本思想是： （1）首先置操作数栈为空栈，表达式起始符“#”作为运算符栈的栈底元素； （2）依次读入表达式中每个字符，若是操作数则进入OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为“#”）。 算法中还调用了两个函数。其中函数Precede是判定运算符栈顶运算符与读入的运算符之间优先关系的函数；函数Operate为进行二元运算的函数，如果是编译表达式，则产生这个运算的一组相应指令并返回存放结果的中间变量名；如果是解释执行表达式，则直接进行该运算，并返回运算结果。 2、方案设计 （1）抽象数据类型定义 ADT Stack{ 数据对象：D={ | ∈ElemSet,i=1,2,…,n,, n≧0} 数据对象：R1={, | , ∈D，i=2,…,n} 约定端为栈顶，端为栈底。 基本操作： InitStack(S) 操作结果：构造一个空栈S。 GetTop(S) 初始条件：栈S已存在。 操作结果：用P返回S的栈顶元素。 Push(S, e) 初始条件：栈S已存在。 操作结果：插入元素e为新的栈顶元素。 Pop(S, e) 初始条件：栈S已存在。 操作结果：删除S的栈顶元素，并用e返回其值。 Precede(,) 初始条件：,为运算符。 操作结果：判断运算符优先权，返回表示优先权高低关系的“”、“=”或“”的字符。 Operate(a, OP, b) 初始条件：a, b为整数，OP为运算符。 操作结果：a与b进行运算，OP为二元运算符，返回其值。 }ADT Stack （2）符号之间的优先权关系比较 ：的优先权低于: =：的优先权等于 ：的优先权高于 + - * / ( ) # + - * / ( = ) # = （3）顺序栈的定义 typedef struct { SElemType *base; SElemType *top; int stacksize; }SqStack; （4）调用函数： void InitStack(SqStack *S) //构造空栈 SElemType GetTop(SqStack *S) //用e返回栈顶元素 SElemType Push(SqStack *S, SElemType e) //插入e为新的栈顶元素 SElemType Pop(SqStack *S) //删除栈顶元素 int jiancha1(char e) //判断e是运