文档介绍：实验三实验报告实验三实验报告1120131317周任然1、简易计算器(1)问题描述由键盘输入一算术表达式,以中缀形式输入,试编写程序将中缀表达式转换成一棵二叉表达式树,通过对该的后序遍历求出计算表达式的值。(2)。不合法要有错误提示信息。。(3)数据结构与算法分析一棵表达式树,它的树叶是操作数,如常量或变量名字,而其他的结点为操作符。。二叉树的存储可以用顺序存储也可用链式存储。当要创建二叉树时,先从表达式尾部向前搜索,找到第一个优先级最低的运算符,建立以这个运算符为数据元素的根结点。注意到表达式中此运算符的左边部分对应的二叉绔为根结点的左子树,右边部分对应的是二叉绔为根结点的右子树,根据地这一点,可用递归调用自己来完成对左右子树的构造。。求值时同样可以采用递归的思想,对表达式进行后序遍历。先递归调用自己计算左子树所代表的表达式的值,再递归调用自己计算右子树代表的表达式的值,最后读取根结点中的运算符,以刚才得到的左右子树的结果作为操作数加以计算,得到最终结果。(4)需求分析程序运行后显示提示信息,输入任意四则运算表达式,倘若所输入的表达式不合法程序将报错。输入四则运算表达式完毕,程序将输出运算结果。测试用的表达式须是由+、-、*、/运算符,括号“(”、“)”与相应的运算数组成。运算数可以是无符号浮点型或整型,范围在0~65535。(5)概要设计二叉树的抽象数据类型定义ADTBinaryTree{数据对象:表达式运算数{num|0<num<65535}表达式运算符{opr|+,-,*,/}数据关系:由一个根结点和两棵互不相交的左右子树构成,且树中结点具有层次关系。根结点必须为运算符,叶子结点必须为运算数。基本操作:InitBiTree(&T,&S)初始条件:存在一四则运算前缀表达式S。操作结果:根据前缀表达式S构造相应的二叉树T。DestroyBiTree(&T)初始条件:二叉树T已经存在。操作结果:销毁T。Value(&T)初始条件:二叉树T已经存在。操作结果:计算出T所表示的四则运算表达式的值并返回。}ADTBineryTree顺序栈的抽象数据类型定义ADTStack{数据对象:具有相同类型及后进先出特性的数据元素集合。数据关系:相邻数据元素具有前去和后继关系。基本操作: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返回其值。}ADTStack字符串的抽象数据类型定义ADTString{数据对象:具有字符类型的数据元素集合。数据关系:相邻数据元素具有前驱和后继关系。基本操作:StrLength(S)初始条件:串S已经存在。操作结果:返回S的元素个数。StrNeg(S,F)初始条件:串S已经存在且非空。操作结果:求S的逆序并将结果保存在串F中。}ADTString本程序包含四个模块:主程序模块;二叉树单元模块(实现二叉树的抽象数据类型,包括结点和指针的定义);顺序栈单元模块(实现顺序栈的抽象数据类型,包含结点和指针的定义);字符串单元模块(实现字符串的抽象数据类型)。四个模块之间调用关系为主程序模块二叉树模块,二叉树模块调用顺序栈模块。详细设计顺序栈类型。#defineStack_Size100typedefstruct{charelem[Stack_Size];inttop;}SqStack基本操作实现的伪代码算法如下:voidInitStack(SqStack&S){//=newElemType[Stack_Size];if(!)Error("Overflow!");=-1;}viodPush(SqStack&S,charc){//顺序栈压栈if(==(Stack_Size-1))Error("StackOverflow!");[++]=c;}ElemTypePop(SqStack&S){//顺序栈出栈if(==-1)Error("StackEmpty!");[--];}intStackLength(SqStack&S){//求顺序栈长度return(S