实验三实验报告分析.doc

实验三实验报告 1120131317 周任然 1、简易计算器 （1）问题描述 由键盘输入一算术表达式，以中缀形式输入，试编写程序将中缀表达式转换成一棵二叉表达式树，通过对该的后序遍历求出计算表达式的值。 （2）基本要求 a．要求对输入的表达式能判断出是否合法。不合法要有错误提示信息。 b．将中缀表达式转换成二叉表达式树。 c．后序遍历求出表达式的值 （3）数据结构与算法分析 一棵表达式树，它的树叶是操作数，如常量或变量名字，而其他的结点为操作符。 a．建立表达式树。二叉树的存储可以用顺序存储也可用链式存储。当要创建二叉树时，先从表达式尾部向前搜索，找到第一个优先级最低的运算符，建立以这个运算符为数据元素的根结点。注意到表达式中此运算符的左边部分对应的二叉绔为根结点的左子树，右边部分对应的是二叉绔为根结点的右子树，根据地这一点，可用递归调用自己来完成对左右子树的构造。 b．求表达式的值。求值时同样可以采用递归的思想，对表达式进行后序遍历。先递归调用自己计算左子树所代表的表达式的值，再递归调用自己计算右子树代表的表达式的值，最后读取根结点中的运算符，以刚才得到的左右子树的结果作为操作数加以计算，得到最终结果。 （4）需求分析 程序运行后显示提示信息，输入任意四则运算表达式，倘若所输入的表达式不合法程序将报错。 输入四则运算表达式完毕，程序将输出运算结果。 测试用的表达式须是由+、-、*、/运算符，括号“(”、“)”与相应的运算数组成。运算数可以是无符号浮点型或整型，范围在0～65535。 （5）概要设计 二叉树的抽象数据类型定义 ADT BinaryTree{ 数据对象：表达式运算数 { num | 0 num 65535 } 表达式运算符 { opr | + , - , * , / } 数据关系：由一个根结点和两棵互不相交的左右子树构成，且树中结点具有层次关系。根结点必须为运算符，叶子结点必须为运算数。 基本操作： InitBiTree(T , S) 初始条件：存在一四则运算前缀表达式S。 操作结果：根据前缀表达式S构造相应的二叉树T。 DestroyBiTree(T) 初始条件：二叉树T已经存在。 操作结果：销毁T。 Value(T) 初始条件：二叉树T已经存在。 操作结果：计算出T所表示的四则运算表达式的值并返回。 }ADT BineryTree 顺序栈的抽象数据类型定义 ADT Stack{ 数据对象：具有相同类型及后进先出特性的数据元素集合。 数据关系：相邻数据元素具有前去和后继关系。 基本操作： InitStack(S) 初始条件：无 操作结果：构造一个空栈S。 DestroyStack(S) 初始条件：栈S已经存在。 操作结果：销毁S。 StackLength(S) 初始条件：栈S已经存在。 操作结果：返回S中元素个数。 GetTop(S , e) 初始条件：栈S已经存在且非空。 操作结果：用e返回S的栈顶元素。 Push(S , e) 初始条件：栈S已经存在。 操作结果：插入元素e为S的新栈顶元素。 Pop(S , e) 初始条件：栈S已经存在且非空。 操作结果：删除S的栈顶元素，并用e返回其值。 }ADT Stack 字符串的抽象数据类型定义 ADT String{ 数据对象：具有字符类型的数据元素集合。 数据关系：相邻数据元素具有前驱和后继关系。 基本操作： StrLength(S) 初始条件：串S已经存在。 操作结果：返回S的元素个数。 StrNeg(S