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