数据结构课程实验报告-实验7优先队列

《数据结构课程实验报告-实验7优先队列》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、HUNANUNIVERSITY课程实习报告题目：逆波兰表达式问题优先队列与堆学生姓名学生学号指导老师完成日期2015-5-9逆波兰表达式问题实验背景在工资管理软件中－16－，不可避免的要用到公式的定义及求值等问题。对于数学表达式的计算，虽然可以直接对表达式进行扫描并按照优先级逐步计算，但也可以将中缀表达式转换为逆波兰表达式，这样更容易处理。基本要求使用二叉树来实现。实现提示利用二叉树后序遍历来实现表达式的转换，同时可以使用实验3的结果来求解后缀表达式的值。输入输出格式：输入：在字符界面上输入一个中缀表达式，回车表示结束。输

2、出：如果该中缀表达式正确，那么在字符界面上输出其后缀表达式，其中后缀表达式中两相邻操作数之间利用空格隔开；如果不正确，在字符界面上输出表达式错误提示。测试用例输入：21+23*（12-6）输出：2123126-*+源代码:#include#include#includeusingnamespacestd;charstr[100][15];//由于一个数字可能有多个数字组成intsearch_1(intstart,intend)//寻找优先级最小的'+'或‘-’{inti

3、,count=0,pos=-1;//count用来记录括号的数量，pos用来记录优先级最小的'+'或'-'的位置for(i=start;i

4、

5、str[i][0]=='-')&&count==0)//无括号时pos=i;//i记录的是优先级最小的'+'或'-'的位置，也就是没有括号，并且在后面的加减运算}returnpos;}intsearch_2(i

6、ntstart,intend)//寻找优先级最小的‘*’或‘/’的位置{inti,count=0,pos=-1;－16－//count用来记录括号的数量，pos用来记录优先级最小的'+'或'-'的位置for(i=start;i

7、

8、str[i][0]=='/')&&count==0)pos=i;}returnpos;}doubleturn(charc[

9、])//将字符串中的数字转换为浮点型{doubletemp=0;inti;for(i=0;;i++){if(c[i]!='')temp=temp*10+c[i]-'0';elsebreak;}returntemp;}classNode{public:chardata[15];Node*lchild;Node*rchild;Node(){lchild=NULL;rchild=NULL;}};classBintree{public:Node*subroot;－16－Node*creattree(intstart,inten

10、d);//建立二叉树voidpostorder(Node*subroot);//后续遍历二叉树doublecalcute(Node*subroot);//计算表达式的结果voiddestory(Node*subroot);//销毁二叉树，释放空间};Node*Bintree::creattree(intstart,intend)//用递归的方法来建立二叉树{intpos=-1;Node*root=newNode;if(end-start==1)strcpy(root->data,str[start]);else{pos=s

11、earch_1(start,end);//找优先级最低的加减法if(pos==-1)pos=search_2(start,end);//如果没有的话那就找优先级最低的乘除法if(pos==-1)root=creattree(start+1,end-1);else{strcpy(root->data,str[pos]);root->lchild=creattree(start,pos);root->rchild=creattree(pos+1,end);}}returnroot;}voidBintree::postorder

12、(Node*subroot)//递归的方法后续遍历{if(subroot!=NULL){postorder(subroot->lchild);postorder(subroot->rchild);cout<data<<"";}}voidBintree::destory(Node*su