四则运算表达式求值(栈+二叉树,c++版)

数据结构——实验报告1/11HUNANUNIVERSITY课程实习报告题目：四则运算表达式求值学生姓名：周华毅学生学号：201308010411专业班级：计科1304指导老师：吴帆完成日期：2015/5/1数据结构——实验报告2/11一、需求分析a)四则运算表达式求值，将四则运算表达式用中缀表达式表示，然后转换为后缀表达式，并计算结果。b)本程序要求利用二叉树后序遍历来实现表达式的转换，同时可以使用实验2的结果来求解后缀表达式的值。c)在字符界面上输入一个中缀表达式，回车表示结束。如果该中缀表达式正确，那么在字符界面上输出其后缀表达式，其中后缀表达式中两相邻操作数之间利用空格隔开；如果不正确，在字符界面上输出表达式错误提示。d)测试数据输入：21+23*（12-6）输出：2123126-*+二、概要设计抽象数据类型为实现上述程序的功能，应以字符串存储用户的输入，以及计算出的结果。算法的基本思想根据题目要求，利用二叉树后序遍历来实现表达式的转换。该算法的基本模块包括二叉树的建立以及如何把输入的中缀表达式利用二叉树后序遍历转化为后缀表达式。1、首先要将输入的中缀表达式（数字字符）存入到二叉树中，由于存在两位或者两位以上的数，甚至还有小数，所以考虑用字符型指针存储数字字符和操作符。2、为了便于将中缀表达式存入二叉树中，在录入中缀表达式后，要进行相应的处理，比如去掉空格符，添加结束标志，如‘=’、‘#’等。3、中缀表达式存入到二叉树的过程中，要注意处理的顺序，如‘+’、‘-’号的优先级比‘*’、‘/’号的低，当遇到‘*’、‘/’号时，要判断树以上的节点中是否有‘+’、‘-’号，有的话要与其交换位置。遇到‘（’时要反复创建二叉树的结点，构建子二叉树，考虑到括号内要处理的步骤可能会较多，可以考虑用递归。遇到‘）’时则直接结束此子二叉树的建立。此外二叉树中叶子结点存储操作数，非叶子结点存储操作码。4、对创建好的二叉树进行后序遍历，即可得到相应的后缀表达式，实现方法可以用递归的方式，由于后面还要计算表达式的值，故便利的过程中要将结点中得到的数据存入新的字符数组中。程序的流程程序由三个模块组成：（1）输入模块：完成一个中缀表达式的输入，存入字符串数组array[Max]中。（2）计算模块：设计一个建立二叉树的函数，Node*crtTree(Node*root)，传入根结点指针，返回根结点指针，该函数的实现还要反复使用另一个函数chargetOp(Node*temp)，其将数字字符存入一个结点，并返回数字字符的后一个符号。voiddeal()函数功能是对字符数组进行处理。voidoutput(Node*root);函数功能是获得处理后的字符串，也就是中缀表达式转化为的后缀表达式。（3）输出模块：如果该中缀表达式正确，那么在字符界面上输出其后缀表达式和表达式的值；如果不正确，在字符界面上输出表达式错误提示。三、详细设计物理数据类型数据结构——实验报告3/11题目要求输入的四则运算表达式运算符只有加减乘除，操作数有整数和小数，为了能够存储，采用C语言中的字符串数组。charch[Max];算法的时空分析算法的运行时间主要耗费在二叉树的建立过程中。可以发现，每当遇到一个运算符或操作数时，都要调用一次函数chargetOp(Node*temp)，来将其存入二叉树的结点中，其中也会遇到递归的情况，但耗时可以忽略。所以假设输入的字符串中字符个数为N，则算法的时间复杂度为O(N)。输入和输出的格式输入本程序可以将输入的四则运算表达式（中缀表达式）转换为后缀表达式//提示请输入四则运算表达式：//提示等待输入输出//提示后缀表达式为：//输出结果的位置表达式的值为：//输出结果的位置四、调试分析本次实验的难点主要是在建立二叉树的问题上。关于如何把中缀表达式存入二叉树中，我参考了网上的一些方法，成功实现了目标，但是却遇到了一个问题，那就是不能处理小数，甚至两位或两位以上的整数。因为如果采用字符数组来存储操作数，运算符合一位整数还可以处理，但对于两位数就就会出问题，最后我改进采用字符串数组来存储操作数，成功解决了问题。另外在处理输入的非法表达式问题中，我也费了很大功夫，但总体问题不大。五、测试结果六、用户使用说明（可选）1、本程序的运行环境为DOS操作系统2、运行程序时提示输入四则运算表达式本程序可以将中缀表达式转化为后缀表达式，并计算结果请输入四则运算表达式：输出后缀表达式为：表达式的值为：七、附录（可选）数据结构——实验报告4/11程序源代码（c++）1、利用二叉树后序遍历来实现表达式的转换：#includeiostream#includestring#includestack#includeiomanipconstintMax=100;usingnamespacestd;classNode{public:charch[Max];//考虑到数值有时会是两位数，所以使用字符串数组Node*lChild;Node*rChild;Node(){strcpy(ch,);lChild=rChild=NULL;}~Node(){if(lChild!=NULL)deletelChild;if(rChild!=NULL)deleterChild;}};staticintcount=0;staticchararray[Max];//保存原始的中缀表达式staticcharstr[2*Max];//保存后序遍历出来的字符串，为表达式求值提供方便staticintk=0;chargetOp(Node*temp);//temp指针保存每个结点，返回的是运算符Node*crtTree(Node*root);//传入根结点指针，返回根结点指针voidoutput(Node*root);//获得处理后的字符串boolisError(char);//判断字符是否有问题voiddeal();//对字符数组进行处理doublevalue(string);//计算后缀表达式，得到其结果。intmain(){Node*root=NULL;cout输入中缀表达式：;cin.getline(array,40);deal();root=crtTree(root);cout输出后缀表达式：;output(root);coutstrendl;数据结构——实验报告5/11cout输出后缀表达式的值：;if(value(str)!=0)coutfixedsetprecision(2)value(str)endl;elsecoutAWrongInput!endl;return0;}//将数字字符存入一个结点，并返回数字字符的后一个符号chargetOp(Node*temp){inti=0;if(isError(array[count]))exit(0);while(array[count]='9'&&array[count]='0'||array[count]=='.'){temp-ch[i]=array[count];i++;count++;}temp-ch[i]='\0';count++;returnarray[count-1];}//传入根结点指针，返回根结点指针Node*crtTree(Node*root){Node*p,*q;charop;if(root==NULL){root=newNode;p=newNode;}op=getOp(root);while(op!='='){q=newNode;q-ch[0]=op;q-ch[1]='\0';switch(op){case'+':case'-':q-lChild=root;root=q;p=newNode;op=getOp(p);root-rChild=p;break;数据结构——实验报告6/11case'*':case'/':if(root-ch[0]=='+'||root-ch[0]=='-'){p=newNode;strcpy(p-ch,root-ch);p-lChild=root;p-rChild=q;op=getOp(root);root=p;}else{q-lChild=root;root=q;p=newNode;op=getOp(p);root-rChild=p;}break;case'(':p=root;while(p-rChild)p=p-rChild;if(p-lChild==NULL){p-lChild=crtTree(p-lChild);//递归创建括号里的指针op=array[count];count++;break;}else{p-rChild=crtTree(p-rChild);//递归创建括号里的指针op=array[count];count++;break;}case')':returnroot;}}returnroot;}//传入根结点，后序遍历,赋值给另一个字符数组（主要是为了给后序的计算表达式值提供方便）voidoutput(Node*root){intn;if(root){output(root-lChild);output(root-rChild);数据结构——实验报告7/11n=0;while(root-ch[n]!='\0')str[k++]=root-ch[n++];str[k++]='';}}boolisError(charch){//判断每个字符是否有错if(ch!='+'&&ch!='-'&&ch!='*'&&ch!='/'&&!(ch='9'&&ch='0')&&ch!='.'&&ch!='('&&ch!=')'){cout字符错误！;returntrue;}returnfalse;}voiddeal(){//对字符数组进行处理inti=0,n=0;while(array[i]){if(array[i]==''||array[i]=='=')i++;array[n++]=array[i++];}array[n++]='=';array[n]='\0';}doublevalue(strings2){//计算后缀表达式，得到其结果。stackdoubles;doublex,y;inti=0;while(is2.length()){if(s2[i]=='')i++;switch(s2[i]){case'+':if(s.size()=2){x=s.top();s.pop();x+=s.top();s.pop();i++;break;}elsereturn0;case'-':if(s.size()=2){x=s.top();s.pop();x=s.top()-x;s.pop();i++;break;}elsereturn0;数据结构——实验报告8/11case'*':if(s.size()=2){x=s.top();s.pop();x*=s.top();s.pop();i++;break;}elsereturn0;case'/':if(s.size()=2){if(s.top()==0)return0;else{x=s.top();s.pop();x=s.top()/x;s.pop();i++;break;}}elsereturn0;default:x=0;while('0'=s2[i]&&s2[i]='9'){x=x*10+s2[i]-'0';i++;}if(s2[i]=='.'){doublek=10.0;y=0;i++;while('0'=s2[i]&&s2[i]='9'){y+=((s2[i]-'0')/k);i++;k*=10;}x+=y;}break;}if(x!=0)s.push(x);}if(s.size()==1)returns.top();elsereturn0;}2、利用堆栈来实现中缀表达式转换为后缀表达式。数据结构——实验报告9