文档介绍：.
1 / 10
HUNANUNIVERSITY
课程实****报告
题目：四则运算表达式求值
学生康小雪
学生学号
专业班级计科三班
指导老师晓鸿
完成日期 2010-10-24
.
2 / 10
需求分析
1．该程序可以从通过从键盘输入一个中缀表达式，判断该表达式是否合法，若合法将
其转化为后缀表达式，并计算其结果，否则说明该表达式错误
2．.输入的表达式包含数字和运算符与括号，之间用空格隔开
3．数字可以为整数和小数
4．运算结果保留两位小数
输入输出举例
输入：21+23*（12-6）
输出：21 23 12 6 -*+
概要设计
在表达式中每个运算符应对应两个操作数，与二叉树中非叶子结点和叶子结点之间的关系刚好一样，于是，本题可采用二叉树来将中缀表达式变为后缀表达式。
最后用堆栈来实现后缀表达式的计算。
抽象数据类型
二叉树
ADT BiTree
{
数据对象 D：D是具有一样特性的数据元素集合
数据关系 R：
若D为空集，则R为空集，则称BinaryTree为空二叉树；
若D不为空集，否则R={H}，H是如下二元关系：
在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；
若D-{root}≠空集，则存在D-{root}的一个划分{D1,Dr} 且D1∩Dr=空集；
若D1≠空集，则D1中存在唯一元素x1，<root，x1>∈H,且存在D1shang de guanxi H1=H;ruo Dr≠空集，则Dr中存在唯一的元素，xr，<root，xr>∈H，且存在Dr上的关系Hr∈H;H={<root,x1>,<root,xr>,H1,Hr};
(D1,{H1})是一棵符合本定义的二叉树，称为根的左子树，(Dr，{Hr})是一棵符合本定义的二叉树，称为根的右子树
基本操作P:
InitBiTree（&T）
操作结果：构造空二叉树T
DestroyBiTree（&T）
初始条件：二叉树T存在
操作结果：销毁二叉树T
CreateBiTree（&T，definition）
初始条件：definition给出二叉树T的定义
操作结果：按definition构造二叉树T
ClearBiTree（&T）
初始条件：二叉树T存在
操作结果：将二叉树T清空为空树
TreeBiEmpty(T)
初始条件：二叉树T存在
操作结果：若二叉树T为空树，则返回TRUE，否则返回FALSE
TreeBiDepth（T）
.
3 / 10
初始条件：二叉树T存在
操作结果：返回二叉树T的深度
Root（T）
初始条件：二叉树T存在
操作结果：返回T的根
Value（T,cur_e）
初始条件：二叉树T存在，cur_e是T中的某个结点
操作结果：返回cur_e的值
Assign（T, cur_e，value）
初始条件：二叉树T存在，cur_e