数据结构课程实验报告-实验5

数据结构课程实验报告-实验5

数据结构课程实验指导书

HUNAN UNIVERSITY

课程实习报告

题 目： 四则运算表达式求值

学生姓名 康小雪

学生学号 20090810310

专业班级 计科三班 指导老师 李晓鸿

完 成 日 期 2010-10-24

－ 2 －

数据结构课程实验指导书

－ 3 －

数据结构课程实验指导书

一、 需求分析

1．该程序可以从通过从键盘输入一个中缀表达式，判断该表达式是否合法，若合法将 其转化为后缀表达式，并计算其结果，否则说明该表达式错误

2．.输入的表达式包含数字和运算符及括号，之间用空格隔开

3．数字可以为整数和小数 4．运算结果保留两位小数 输入输出举例 输入：21+23*（12-6） 输出：21 23 12 6 -*+ 二、 概要设计

在表达式中每个运算符应对应两个操作数，与二叉树中非叶子结点和叶子结点之间的关系刚好相同，于是，本题可采用二叉树来将中缀表达式变为后缀表达式。

最后用堆栈来实现后缀表达式的计算。 抽象数据类型

二叉树 ADT BiTree {

－ 4 －

数据结构课程实验指导书

数据对象 D：D是具有相同特性的数据元素集合

数据关系 R：

若D为空集，则R为空集，则称BinaryTree为空二叉树；

若D不为空集，否则R={H}，H是如下二元关系：

（1） 在D中存在唯一的称为根的数据元素

root，它在关系H下无前驱；

（2） 若D-{root}≠空集，则存在D-{root}

的一个划分{D1,Dr} 且D1∩Dr=空集； （3） 若D1≠空集，则D1中存在唯一元素

x1，∈H,且存在D1shang de guanxi H1=H;ruo Dr≠空集，则Dr中存在唯一的元素，xr，∈H，且存在

Dr

上的关系

Hr∈

H;H={,,H1,Hr}; （4） (D1,{H1})是一棵符合本定义的二叉

树，称为根的左子树，(Dr，{Hr})是一棵符合本定义的二叉树，称为根的右子树 基本操作P: InitBiTree（&T）

－ 5 －