数据结构课程实验报告_实验7优先队列教程.doc

数据结构课程实验指导书 －  PAGE 16 － HUNAN UNIVERSITY 课程实习报告 题 目： 逆波兰表达式问题 优先队列与堆 学生姓名 学生学号 指导老师 完 成 日 期 2015-5-9 逆波兰表达式问题 实验背景 在工资管理软件中，不可避免的要用到公式的定义及求值等问题。对于数学表达式的计算，虽然可以直接对表达式进行扫描并按照优先级逐步计算，但也可以将中缀表达式转换为逆波兰表达式，这样更容易处理。 基本要求 使用二叉树来实现。 实现提示 利用二叉树后序遍历来实现表达式的转换，同时可以使用实验3的结果来求解后缀表达式的值。 输入输出格式： 输入：在字符界面上输入一个中缀表达式，回车表示结束。 输出：如果该中缀表达式正确，那么在字符界面上输出其后缀表达式，其中后缀表达式中两相邻操作数之间利用空格隔开；如果不正确，在字符界面上输出表达式错误提示。 测试用例 输入：21+23*（12-6） 输出：21 23 12 6 -*+ 源代码: #includeiostream #includestring #includeiomanip using namespace std; char str[100][15];//由于一个数字可能有多个数字组成 int search_1(int start,int end)//寻找优先级最小的+或‘-’ { int i,count=0,pos=-1;//count用来记录括号的数量，pos用来记录优先级最小的+或-的位置 for(i=start;iend;i++) { if(str[i][0]==() count++; else if(str[i][0]==)) count--; else if((str[i][0]==+ || str[i][0]==-) count==0)//无括号时 pos=i; //i记录的是优先级最小的+或-的位置 ，也就是没有括号，并且在后面的加减运算 } return pos; } int search_2(int start ,int end)//寻找优先级最小的‘*’或‘/’的位置 { int i,count=0,pos=-1;//count用来记录括号的数量，pos用来记录优先级最小的+或-的位置 for(i=start;iend;i++) { if(str[i][0]==)) count--; else if(str[i][0]==() count++; else if((str[i][0]==* || str[i][0]==/) count==0) pos=i; } return pos; } double turn(char c[]) //将字符串中的数字转换为浮点型 { double temp=0; int i; for(i=0;;i++) { if(c[i]!=\0) temp=temp*10+c[i]-0; else break; } return temp; } class Node { public: char data[15]; Node* lchild; Node* rchild; Node() { lchild=NULL; rchild=NULL; } }; class Bintree { public: Node* subroot; Node* creattree(int start ,int end);//建立二叉树 void postorder(Node* subroot); //后续遍历二叉树 double calcute(Node* subroot); //计算表达式的结果 void destory(Node* subroot); //销毁二叉树，释放空间 }; Node* Bintree::creattree(int start,int end)//用递归的方法来建立二叉树 { int pos=-1; Node* root =new