东南大学数据结构实验报告电气工程学院王磊实验二

四则混合运算表达式处理侯创 16010131 2012/11/2一 需求分析1. 程序功能实现逆波兰式输入后的二叉树转化，并分别输出前序中序和后序输出。计算表达式的值，并打印树木。同时，如果树木的逆波兰式有错，报错，并删除树木2. 输入输出要求输入数据见下侧试验数据，输出要求为输出个表达式，以及计算结果和二叉树形状。3. 测试数据ab*,abcd-*+ef/-,abc*,abc+-/二 概要设计1. 数据结构采用链表形式构成二叉树，每个节点包含五个数据，分别是节点数据，左节点位置，右节点位置。节点横纵坐标2. 各个模块模块一为树的生成阶段，如表达式正确，将继续横纵坐标。如果表达式错误，删除已经生成的树，模块二各项遍历输出模块三打印树模块四计算算式结果3. 模块关系各模块平行运行三 详细设计1. 树的生成对于输入逆波兰式从输入的最后一个数据进行读取，按照先生出右枝叶的原则生成，遇到同层左枝和与下测均空的情况下，率先将树的层次加深，即按照中右左形式生成如果当前数据为一个字母，则生成后，停止该枝叶的生成跳出这个子树。2. 树的检测如果树生成完，仍然有剩余数据，标明输入有错误对于生成的树检测如发现枝叶元素有运算符运算生成错误对于根节点，如果没有两个子树，输入错误3. 遍历算法比较简单，不再详述4. 打印函数从根节点进行遍历，首先赋予根节点一个坐标再进行任意一种遍历，但是子节点坐标由根节点数据计算而来，按照树的形状计算。5. 计算函数从根节点遍历，使用递归算法，检测到运算符，则进行进一步递归调用检测到字母，按照字母的ASCII码调用数组中的预设值数据，该数组数据，可以随意改变。四 调试分析1. 遇到问题主要为一些语法错误，按照编译器提示修改即可2. 算法复杂度树的生成时间复杂度O（n）空间复杂度O（n）树的检测时间复杂度O（n）空间复杂度O（n）打印函数时间复杂度为O（n2）空间复杂度为O（n）计算函数与遍历函数，树的生成函数相同五 使用说明及测试结果本程序为避免操作错误，已经将所有检测项目内嵌于主程序内，观察即可得结果六 源程序/类的头文件#include#includeusing namespace std;/定义二叉链表节点类型struct Btnodechar ch;/节点元素Btnode* lchild;/左子树数据Btnode* rchild;/右子树节点int xpoint;/X坐标int ypoint;/Y坐标;/二叉链表类class Binary_Treeprivate:Btnode* BT;/二叉链表根节点指针int length;/长度public:Binary_Tree();/构造函数 int creat_Binary_Tree (string);/生成二叉链表void pretrav_Binary_Tree();/前序遍历二叉链表void intrav_Binary_Tree ();/中序遍历二叉链表void postrav_Binary_Tree();/后序遍历二叉链表void print_Binary_Tree ();/打印二叉树void delete_Binary_Tree ();/删除二叉树int calute_Binary_Tree ();/类程序定义文件#includebolan.h#include#include#include using namespace std;int i;int creat(Btnode*p,int mark, string val,int depth);int pretrav(Btnode*p);int intrav(Btnode*p);int postrav(Btnode*p);int text(Btnode*p);int pretravtext(Btnode*p);void delete_Tree(Btnode*p);int calute_Tree(Btnode*p);Binary_Tree:Binary_Tree()/Construct functionBT=NULL;length=0;int Binary_Tree:creat_Binary_Tree(string val)Btnode*p;int len=0;while(1)if (vallen=0)i=len-1;length=len;break;len+;p=new Btnode;p-ch=vali;p-lchild=NULL;p-rchild=NULL;p-xpoint=1;p-ypoint=30;BT=p;i-; creat(p,2,val,5);creat(p,1,val,5);if (text(p)=0)/检测树是否有问题coutch=vali; q-lchild=NULL; q-rchild=NULL;if(mark=2)p-rchild=q;q-xpoint=p-xpoint+1;q-ypoint=p-ypoint+depth; if(mark=1) p-lchild=q;q-xpoint=p-xpoint+1;q-ypoint=p-ypoint-depth;i-;creat(q,2,val,depth-1);creat(q,1,val,depth-1);elseq=new Btnode;q-ch=vali;i-;q-lchild=NULL; q-rchild=NULL;if(mark=2)p-rchild=q;q-xpoint=p-xpoint+1;/根据深度，调整坐标q-ypoint=p-ypoint+depth;if(mark=1) p-lchild=q;q-xpoint=p-xpoint+1;q-ypoint=p-ypoint-depth;return 0;return 0;void Binary_Tree:pretrav_Binary_Tree()Btnode* p=BT;pretrav(p);coutendl;int pretrav(Btnode*p)if(p!=NULL)coutchlchild);pretrav(p-rchild);return 0;int text(Btnode*p)if(p!=NULL) pretravtext(p-lchild);if (p-ch)=+|(p-ch)=-|(p-ch)=*|(p-ch)=/)if (p-lchild=NULL|p-rchild=NULL)return 0;pretravtext(p-rchild);if(i!=-1)return 0;return 1;int pretravtext(Btnode*p)if(p!=NULL) pretravtext(p-lchild);pretravtext(p-rchild);return 0;void Binary_Tree:intrav_Binary_Tree()Btnode* p=BT;intrav(p);coutlchild);coutchrchild);return 0;void Binary_Tree:postrav_Binary_Tree()Btnode* p=BT;postrav(p);coutlchild);postrav(p-rchild);coutch ;return 0;void Binary_Tree:print_Binary_Tree()/打印树，根据已有坐标设计char bottle860;for(int ix=0;ix8;ix+)for(int iy=0;iy60;iy+)bottleixiy= ;Btnode*p=BT;queueque;que.push(p);while(que.size()!=0)p=que.front();bottlep-xpointp-ypoint=p-ch;que.pop();if (p-lchild!=NULL)que.push(p-lchild);if (p-rchild!=NULL)que.push(p-rchild);for(int ixx=0;ixx8;ixx+)for(int iyy=0;iyy60;iyy+)coutbottleixxiyy;coutlchild);delete_Tree(p-rchild); delete p;int number26;int Binary_Tree:calute_Binary_Tree()/计算数据for(int k=0;k0 -1 *-2 /-3numberk=1+k*2; / a=97-0z-122-25/为减少操作 /数，变量数据在此设置，如需要实验变量设置，可在此更改 switch(BT-ch)case +:return calute_Tree(BT-lchild)+calute_Tree(BT-rchild);case -:return calute_Tree(BT-lchild)-calute_Tree(BT-rchild);case *:return calute_Tree(BT-lchild)*calute_Tree(BT-rchild);case /:return calute_Tree(BT-lchild)/calute_Tree(BT-rchild);default: return 0;int calute_Tree(Btnode*p)switch(p-ch)case +:return calute_Tree(p-lchild)+calute_Tree(p-rchild);case -:return calute_Tree(p-lchild)-calute_Tree(p-rchild);case *:return calute_Tree(p-lchild)*calute_Tree(p-rchild);case /:return calute_Tree(p-lchild)/calute_Tree(p-rchild);default: coutch=ch-97ch-97;/测试程序#include#include#include bolan.husing namespace std;int main()Binary_Tree obj4;string valu4=ab*,abcd-*+ef/-,abc*,abc+-/;/以实验数据生成树，生成不成功，删除之for(int i=0;i4;i+)coutThe input is valuiendl;/输出输入的计算式if (obji.