《实验三实验报告》由会员分享，可在线阅读，更多相关《实验三实验报告（14页珍藏版）》请在金锄头文库上搜索。
1、实验三实验报告1120131317 周任然1、简易计算器（1）问题描述由键盘输入一算术表达式， 以中缀形式输入， 试编写程序将中缀表达式转换成一棵二叉 表达式树，通过对该的后序遍历求出计算表达式的值。（2）基本要求 a要求对输入的表达式能判断出是否合法。不合法要有错误提示信息。 b将中缀表达式转换成二叉表达式树。c后序遍历求出表达式的值（3）数据结构与算法分析 一棵表达式树，它的树叶是操作数，如常量或变量名字，而其他的结点为操作符。 a建立表达式树。 二叉树的存储可以用顺序存储也可用链式存储。当要创建二叉树时， 先从表达式尾部向前搜索， 找到第一个优先级最低的运算符， 建立以这个运算符为数据元
2、素 的根结点。 注意到表达式中此运算符的左边部分对应的二叉绔为根结点的左子树， 右边部分 对应的是二叉绔为根结点的右子树， 根据地这一点， 可用递归调用自己来完成对左右子树的 构造。b求表达式的值。求值时同样可以采用递归的思想，对表达式进行后序遍历。先递归 调用自己计算左子树所代表的表达式的值，再递归调用自己计算右子树代表的表达式的值， 最后读取根结点中的运算符， 以刚才得到的左右子树的结果作为操作数加以计算， 得到最终 结果。（ 4）需求分析程序运行后显示提示信息， 输入任意四则运算表达式， 倘若所输入的表达式不合法程序 将报错。输入四则运算表达式完毕，程序将输出运算结果。测试用的表达式须是
3、由 +、-、*、/ 运算符，括号“ （”、“）”与相应的运算数组成。运算 数可以是无符号浮点型或整型，范围在0 65535。（5）概要设计 二叉树的抽象数据类型定义 ADT BinaryTree数据对象：表达式运算数 num | 0 num 65535 表达式运算符 opr | + , - , * , / 数据关系：由一个根结点和两棵互不相交的左右子树构成，且树中结点具有层次 关系。根结点必须为运算符，叶子结点必须为运算数。基本操作：InitBiTree（&T , &S） 初始条件：存在一四则运算前缀表达式S。操作结果：根据前缀表达式 S 构造相应的二叉树 T。DestroyBiTree（&T
4、） 初始条件：二叉树 T 已经存在。 操作结果：销毁 T。Value(&T) 初始条件：二叉树 T 已经存在。 操作结果：计算出 T 所表示的四则运算表达式的值并返回。ADT BineryTree 顺序栈的抽象数据类型定义ADT Stack 数据对象：具有相同类型及后进先出特性的数据元素集合。 数据关系：相邻数据元素具有前去和后继关系。基本操作：InitStack(&S) 初始条件：无 操作结果：构造一个空栈 S。DestroyStack(&S) 初始条件：栈 S 已经存在。 操作结果：销毁 S。StackLength(&S) 初始条件：栈 S 已经存在。 操作结果：返回 S 中元素个数。Ge
5、tTop(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 , F) 初始条件：串
6、 S 已经存在且非空。 操作结果：求 S的逆序并将结果保存在串 F 中。ADT String 本程序包含四个模块：主程序模块； 二叉树单元模块(实现二叉树的抽象数据类型，包 括结点和指针的定义) ；顺序栈单元模块(实现顺序栈的抽象数据类型，包含结点和指针的 定义)；字符串单元模块 (实现字符串的抽象数据类型 )。四个模块之间调用关系为主程序模 块二叉树模块，二叉树模块调用顺序栈模块。详细设计 顺序栈类型。#define Stack_Size 100typedef struct char elemStack_Size;int top;SqStack 基本操作实现的伪代码算法如下： void In
7、itStack (SqStack &S) / 初始化顺序栈S.elem=new ElemTypeStack_Size; if(!S.elem) Error(Overflow!); S.top=-1; viod Push (SqStack &S,char c) / 顺序栈压栈 if(S.top=(Stack_Size-1) Error(Stack Overflow!); S.elem+S.top=c; ElemType Pop (SqStack &S) / 顺序栈出栈if(S.top=-1) Error(Stack Empty!);return S.elemS.top-; int StackLe
8、ngth(SqStack &S) return (S.top+1); GetTop(SqStack &S ,char e) e=S.elemtop; 字符串类型typedef structchar *ch;int length;String 基本操作实现的伪代码算法如下： int StrLength(&S) return S.length; void StrNeg(&S , &F) if(!S.length) error(“ String Empty!” ); for(i=0 ; i=0 ; i-) / 判断运算符级别函数/ 判断输入串中的字符是不是合法操作符/ 将一个中缀串转换为后缀串，/
9、输出串/ 对输入串逆序扫描/ 假如是操作数，把它添加到输出串中。/ 假如是右括号，将它压栈。/ 如果是运算符| GetTop(S)=) |if(Str.chi=48&Str.chi=Precedence( GetTop(S) ) ) Push( S , Str.chi ); break; else Pop(S , e);Output.chi=e;Output.length+; if( Str.chi=( ) / 假如是左括号右括号。右括号出栈并丢弃。while( GetTop(S)!=) ) Output.chi=Pop(S); Output.length+;/ 二叉树指针其中 * / 的级别
10、为 2，+ - 的级别为 1；栈中运算符逐个出栈并输出， 直到遇到while(S.top!=-1) / 假如输入完毕，栈中剩余的所有操作符出栈并加到输出串中。Output.ch=Output.ch-;Output.ch=Pop(S); return output;void CreatBiTree(&T , &S) / 由中缀表达式生成表达式二叉树String F;SqStack Sq;/ 用以存放生成的二叉树结点InitStack(Sq);F=Convert(S);/ 求得 S 的前缀表达式for(i=F.length-1 ; i=0 ; i-) If( !IsOperator(F.chi)
11、) T=new TNode;T-data=F.chi;T-lchild=NULL;T-rchild=NULL;Push(Sq , T) else T=new TNode;T-data=F.chi;T-lchild=Pop( Sq );T-rchild=Pop( Sq );Push(Sq , T); int Calc(int a, char opr, int b) / 计算switch (opr) case +: return a + b;case -: return a - b;case *: return a * b;case /: return a / b;int Value(TNode
12、*T) if (T-lchild = NULL &T-rchild = NULL)return T-data;elsereturn Calc( Value(T-lchild) , T-data , Value(T-rchild) );主函数伪码算法。void main() Face(); / 输出界面及相关信息do cout ” Please input an expression”: Str;JudgeExp(S); / 判断输入的表达式是否合法。T=CreatBiTree(S);N=Value(T);cout ” The value of this expression is”Nendl; coute;if(e= y ) flag=1;else flag=0; while(flag)/main测试结果
