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