数据结构
课程设计报告
设计题目：表达式求值
年 级 05
级
班 级
姓 名
学 号
指导教师
起止时间 2007.11.26 11.30
2007 年第一学期
一．实习目的
通过实习，了解并初步掌握设计、实现较大系统的完整过程，包括系统分析、
编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及
操作方法，为进一步的应用开发打好基础。
二．问题描述
一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假
设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、
结束符“#，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利
用“算符优先法”求算术表达式的值。
三．需求分析
为实现算符优先算法,可以使用两个工作栈。一个称做 OPTR，用以寄存运算
符;另一个称做 OPND;用以寄存操作数或运算结果。算法的基本思想是：
1) 首先置操作数栈为空栈，表达式起始符“#为运算符栈的栈底元素;
2) 依次读入表达式中每个字符,若是操作数则 OPND 栈,若是运算符,则和 OPTR
栈的栈顶运算 符比较优先权后做相应操作,直至整个表达式求值完毕(即
OPTR 栈的栈顶元素和当前读入的字符均为"#")。
该程序实现表达式的求值问题：
（1） 从键盘读入一个合法的算术表达式，利用算符优先关系，实现对算术四则
混合运算的求值，输出正确的结果。
（2） 显示输入序列和栈的变化过程。
四．概要设计
程序流程图
系统用到的抽象数据类型定义：
1．ADT Stack {
数据对象：D＝{ ai | ai ∈ElemSet, i=1,2,...,n,
n≥0 }
数据关系：R1＝{ <ai-1, ai >| ai-1, ai∈D, i=2,...,n }
约定an 端为栈顶，a1 端为栈底。
基本操作：
InitStack(&S) 操作结果：构造一个空栈S。
GetTop(S, &e) 初始条件：栈S已存在且非空。
操作结果：用e返回S的栈顶元素。
Push(&S, e) 初始条件：栈S已存在。
操作结果：插入元素e为新的栈顶元素。
StackEmpty(&s) 初始条件: 栈S已存在。
操作结果:若S为空栈，则返回TRUE, 否则返回FALSE
Pop(&S, &e) 初始条件：栈S已存在且非空。
开始
优先级比较算法
Operate 算法
建 立
栈
存放操作字符 存放数据
EvaluateExpression
算法
计算
结束
操作结果：删除S的栈顶元素，并用e返回其值。
} ADT Stack
系统中子程序及功能要求：
、函数实现的功能是把操作符转换成相应的数字，并返回其值。
、函数实现的功能是对操作符栈进行遍历，并在屏
幕上输出遍历到的各操作符。
、函数实现的功能是对操作符栈进行遍历，并在
屏幕上输出遍历到的各操作数。
、函数实现打印程序执行的步骤在屏幕上输出。
、通过原来的设定比较两个字符的优先级。
、 !函数进行四则运算，并
返回结果。
"、#$#%：函数对以上函数进行调用，实现表达式的求
值并打印出计算过程，完成程序的总体功能，
返回表达式的计算结果。
各程序模块之间的调用关系
主函数可调用子程序 "
子程序 调用子程序
子程序 " 可调用子程序 ，，，，，
五．详细设计(C 语言) 源程序
&&&&&&&&&&&&&&&&&&&&&&&''''''''''''表达式求值'''''''''''''&&&&&&&&&&&&&&&&&&&&
($)*+
($)*+
($) *+&&判断是否为字符的函数的头文件
(,-./012#33
4 5
4$5&&由于 不是一个类型 而 $ 才是
6"789:;::<::'::&::::::(:=5&&把符号转换成一个字符数组
46"7893=5&&栈内元素优先级
46"7893=5&&栈外的元素优先级
835
$
9
6-./012#75
5
=5
1'
9
<+835
=
!0# 0
9&&若 0 为空栈，则返回 >?@#否则返回 .A0#
40*883
$$5
$45
=
B$' %
9
- 1
- 2
前往页