北工大数据结构上机实验报告3

1、上机题三报告 姓名： 学号： 完成日期：2015年5月5日题目：表达式可以用表达式二叉树来表示。对于简单的四则运算表达式，请实现以下功能；（1）对于任意给出的前缀表达式（不带括号）、中缀表达式（可以带括号）或后缀表达式（不带括号），能够在计算机内部构造出一棵表达式二叉树，并且以图示显示出来（字符图或图形的形式）。（2） 对于构造好的内部表达式二叉树，按照用户要求，输出相应的前缀表达式（不带括号）、中缀表达式（可以带括号）或后缀表达式（不带括号）.1、 需求分析1. 输入形式、输入值的范围；输入前缀表达式（不带括号）、中缀表达式（可以带括号）或后缀表达式（不带括号）2. 输出形式；表达式二叉树，

2、前缀表达式、中缀表达式和后缀表达式。3. 程序功能；用表达式二叉树表示表达式，并转换为前缀表达式、中缀表达式或后缀表达式。4. 测试数据 正确的输入输出： 错误的输入输出： 2、 概要设计1. ADT定义class TNode/节点类开始2. 主程序流程结束输出各类表达式是是将表达式转换为二叉树表达式是否是否为中缀表达式是否为前缀表达式输入表达式是否为后缀表达式否 3. 各程序模块间的调用关系Main（） 删除树打印树求前、中、后缀表达式模块求二叉树表达式模块3、 详细设计1. 实现ADT定义的数据类型class TNode/节点类 public:char oper;/数据域，为简便起见，操作

3、数用单个字符代替TNode *left;TNode *right;int s;int t;/计算树的层数使用TNode()/缺省构造函数 left=right=NULL; oper=0; TNode(char op)/赋值构造函数 left=right=NULL; oper=op;2. 算法描述表达式转化为二叉树void pre2tree(TNode *&p, string str)/前缀表达式生成二叉树 碰到操作数则把其值赋给相应的新申请的二叉树结点，地址压栈；碰到操作符则把其值赋给相应的新申请的二叉树，并从栈中弹出两个地址，分别作为其左指针和右指针，然后再把其地址压栈，最后一个地址

4、即为二叉树的根结点地址。void post2tree(TNode *&p,string str)/后缀表达式生成二叉树 /碰到操作数则把其值赋给相应的新申请的二叉树结点，若栈为空则地址压栈，/碰到操作符则把其值赋给相应的新申请的二叉树结点，取栈顶元素，/若当前元素的左孩子为空则设为其左孩子，/左孩子为满则设为其右孩子,开始那个元素地址为根结点地址，开始时用变量root保存。void in2tree(TNode *&p, string str)/中缀表达式转换成后缀表达式生成二叉树 从中缀表达式中自左至右依次读入各个字符。  如果读入操作数，直接输出到后缀表达式。 如果

5、读入的是运算符，并且运算符栈为空，则将该运算符直接进栈；如果栈不为空， 则比较该运算符和栈顶运算符的优先级。      若该运算符高于栈顶运算符的优先级，则将该运算符直接进栈； 若该运算符低于或等于栈顶运算符的优先级，则将栈中高于或等于该运算符优先级的元 素依次出栈输出到后缀表达式中，然后再将该运算符进栈。 在碰到开括号和栈为空前反复弹出栈中元素 若栈非空栈顶不是左括号且栈顶元素优先级不低于输入运算符时，/将栈顶元素弹出到后缀表达式二叉树表达式转化为表达式 void postOrder(TNode *p) /先序遍

6、历 if(p) postOrder(p->left); postOrder(p->right); cout<<p->oper; void preOrder(TNode *p) /后序遍历 if(p) cout<<p->oper; preOrder(p->left); preOrder(p->right); void inOrder(TNode *p)/中序遍历，同时输出不带冗余括号的中缀表达式 if(p)if(p->left) if(如果当前节点的左子树是运算符，且运算符优先级低于当前运算符，那么左边的表达式要先计算，需要加括号

7、) cout<<"(" inOrder(p->left); cout<<")" else/否则直接输出左子树 inOrder(p->left); cout<<p->oper;/输出当前节点 if(p->right) if(如果当前节点的右子树是运算符，且运算符优先级不高于当前运算符，那么右边的表达式要先计算，需要加括号) cout<<"(" inOrder(p->right); cout<<")" else inOrder(p

8、->right); 4、 程序测试5、 用户使用说明运行程序后，按照提示选择表达式类型（-1：前缀表达式；0：中缀表达式；1：后缀表达式）然后输入相应的表达式，回车后可以得到二叉树表达式及出前缀、中缀、后缀表达式6、 源程序#include <iostream>#include <stack>#include <queue>#include <string>#include<math.h>using namespace std;class TNode/节点类 public:char oper;/数据域，为简便起见，操作数用单个字

9、符代替TNode *left;TNode *right;int s;int t;/计算树的层数使用TNode()/缺省构造函数 left=right=NULL; oper=0; TNode(char op)/赋值构造函数 left=right=NULL; oper=op;bool isOper(char op)/判断是否为运算符char oper='(',')','+','-','*','/',''for(int i=0;i<sizeof(oper);i+) if(op=ope

10、ri) return true; return false;int getOperOrder(char op)/返回运算符op所对应的优先级/ 左括号优先级，加减号为，乘除号为，方幂为，右括号，栈底返回switch(op)case '(': return 1; case '+': case '-':return 2; case '*': case '/':return 3; case '':return 4; default: /定义在栈中的右括号和栈底字符的优先级最低 return 0; void

11、 freeTree(TNode *&p) /递归删除树 if(p->left!=NULL) freeTree(p->left); if(p->right!=NULL) freeTree(p->right); delete(p); void postOrder(TNode *p) /先序遍历 if(p) postOrder(p->left); postOrder(p->right); cout<<p->oper; void preOrder(TNode *p) /后序遍历 if(p) cout<<p->oper; p

12、reOrder(p->left); preOrder(p->right); void inOrder(TNode *p)/中序遍历，同时输出不带冗余括号的中缀表达式 if(p)if(p->left) /如果当前节点的左子树是运算符，且运算符优先级低于当前运算符，/那么左边的表达式要先计算，需要加括号if(isOper(p->left->oper)&& getOperOrder(p->left->oper)<getOperOrder(p->oper) cout<<"(" inOrder(p-&g

13、t;left); cout<<")" else/否则直接输出左子树 inOrder(p->left); cout<<p->oper;/输出当前节点 if(p->right) /如果当前节点的右子树是运算符，且运算符优先级不高于当前运算符，/那么右边的表达式要先计算，需要加括号 if(isOper(p->right->oper)&& getOperOrder(p->right->oper)<=getOperOrder(p->oper) cout<<"("

14、; inOrder(p->right); cout<<")" else inOrder(p->right); void post2tree(TNode *&p,string str)/后缀表达式生成二叉树 /（a）碰到操作数则把其值赋给相应的新申请的二叉树结点，若栈为空则地址压栈，/（b）碰到操作符则把其值赋给相应的新申请的二叉树结点，取栈顶元素，/若当前元素的左孩子为空则设为其左孩子，/左孩子为满则设为其右孩子,开始那个元素地址为根结点地址，开始时用变量root保存。stack <TNode*> nodeStack;/用于保存节

15、点指针的栈 char temp; int i=0; temp=stri+; while(temp!='0') if(temp!='0'&&!isOper(temp)/不是运算符，则进栈 p=new TNode(temp);/以temp为结点值构造二叉树结点 nodeStack.push(p); temp=stri+;/读入下一个 else /如果遇到符号，则弹栈，依次设为右节点和左节点p=new TNode(temp); if(nodeStack.size() p->right=nodeStack.top();/若非空则弹栈并设为结点的右孩

16、子 nodeStack.pop(); if(nodeStack.size() p->left=nodeStack.top();/若非空则弹栈并设为结点的左孩子 nodeStack.pop(); nodeStack.push(p); temp=stri+; void pre2tree(TNode *&p, string str)/前缀表达式生成二叉树/碰到操作数则把其值赋给相应的新申请的二叉树结点，地址压栈；/碰到操作符则把其值赋给相应的新申请的二叉树，并从栈中弹出两个地址，/分别作为其左指针和右指针，然后再把其地址压栈，最后一个地址即为二叉树的根结点地址。stack <TN

17、ode*> nodeStack; char temp; int i=str.size()-1; temp=stri-; while(temp!='0') if(temp!='0'&&!isOper(temp) p=new TNode(temp);/以temp为内容来建立新的结点 nodeStack.push(p); temp=stri-; else p=new TNode(temp); if(nodeStack.size()/栈非空 p->left=nodeStack.top(); /则栈顶指针所指结点设置成当前结点左孩子 nodeS

18、tack.pop(); if(nodeStack.size()/栈非空 p->right=nodeStack.top();/则栈顶指针所指结点设置成当前结点右孩子 nodeStack.pop();/栈顶元素左右孩子指针设置完毕弹出 nodeStack.push(p); temp=stri-; /当栈空且扫描到最后时，树根由P带回void in2tree(TNode *&p, string str)/中缀表达式转换成后缀表达式生成二叉树 stack<char> a; char temp; string Postfixexp="" int i=0; t

19、emp=stri+; while(temp!='0') if(!isOper(temp)/操作数则直接进数据栈 Postfixexp+=temp; temp=stri+; else if(temp='(')/进栈 a.push(temp); temp=stri+; else if(temp=')') while(a.top()!='(')/脱括号 Postfixexp+=a.top(); a.pop();/在碰到开括号和栈为空前反复弹出栈中元素 a.pop(); temp=stri+; else if(temp='+

20、9;|temp='-'|temp='*'|temp='/')/出栈while(!a.empty()&&a.top()!='('&&getOperOrder(a.top()>=getOperOrder(temp)/若栈非空栈顶不是左括号且栈顶元素优先级不低于输入运算符时，/将栈顶元素弹出到后缀表达式中，并且str下标加 Postfixexp+=a.top(); a.pop(); a.push(temp);temp=stri+; /end while(temp!='0') whil

21、e(!a.empty() Postfixexp+=a.top();a.pop(); Postfixexp+='0' /cout<<Postfixexp; post2tree(p,Postfixexp);void count(TNode *p,int &height,int n)/求值函数/求树的高度if(p->left=NULL&&p->right=NULL) if(n>height) height=n; if(p->left!=NULL)count(p->left,height,n+1); if(p->r

22、ight!=NULL) count(p->right,height,n+1);void paint(TNode *p)/打印树 int height=0; int h=0; int i; using std:queue; queue<TNode*> aQueue; count(p,height,1);TNode *pointer=p; TNode *lastpointer; if(pointer) pointer->s=1; pointer->t=1; aQueue.push(pointer); while(!aQueue.empty() lastpointer=

23、pointer; pointer=aQueue.front(); aQueue.pop(); if(pointer->s>h) cout<<endl; h=pointer->s; if(pointer->t=1) for(i=0;i<pow(2,height-pointer->s)-1;i+) cout<<" " else if(lastpointer->s!=pointer->s)for(i=0;i<(pointer->t-1)*(pow(2,height-pointer->s+1)

24、-1)+(pointer->t-1)-1+pow(2,height-pointer->s);i+) cout<<" " else for(i=0;i<(pointer->t-lastpointer->t)*(pow(2,height-pointer->s+1)-1)+(pointer->t-lastpointer->t)-1;i+) cout<<" " cout<<pointer->oper; if(pointer->left!=NULL) pointer->left->s=pointer->s+1; pointer->left->t=pointer-&g