数据结构实验报告-四则运算表达式求值

实验五四则运算表达式求值一． 问题描述：四则运算表达式求值，将四则运算表达式用中缀表达式，然后转换为后缀表达式，并计算结果。二． 基本要求：使用二叉树来实现。三． 实现提示：利用二叉树后序遍历来实现表达式的转换，同时可以使用实验二的结果来求解后缀表达式的值。输入输出格式：输入：在字符界面上输入一个中缀表达式，回车表示结束。输出：如果该中缀表达式正确，那么在字符界面上输出其后缀表达式，其中后缀表达式中两相邻操作数之间利用空格隔开；如果不正确，在字符界面上输出表达式错误提示。测试实例：输入：21+23*（12-6）输出：2123126-*+四．设计概要用二叉树表示表达式：若表达式为数或简单变量，则相应二叉树中仅有一个根结点，其数据域存放该表达式信息若表达式=（第一操作数）（运算符）（第二操作数），则相应的二叉树中以左子树表示第一操作数，右子树表示第二操作数，根结点的数据域存放运算符（若为一元算符，则左子树空）。操作数本身又为表达式.后缀遍历二叉树码实现和静态检查上机调试及测试数据的调试五．源程序：#include<iostream.h>#include<string.h>#include<malloc.h>#include<stdlib.h>#include<stack>#include<string.h>#defineSTACK_INIT_SIZE100#defineDATA_SIZE10#defineSTACKINCREMENT10#defineOK1#defineTRUE1#defineFALSE0#defineERROR0#defineOVERFLOW-2usingnamespacestd;typedeffloatSElemtype;typedefintStatus;typedefchar*TElemType;typedefstructBiTNode{TElemTypedata;intlen; //data字符串中字符的个数structBiTNode*lchild,*rchild;}BiTNode,*BiTree;typedefstruct{SElemtype*base;SElemtype*top;intstacksize;}SqStack;StatusIsDigital(charch){if(ch>='0'&&ch<='9'){return1;//是数字字母}return0;//不是数字字母}intCrtNode(stack<BiTree>&PTR,char*c){BiTNode*T;inti=0;T=(BiTNode*)malloc(sizeof(BiTNode));T->data=(char*)malloc(DATA_SIZE*sizeof(char));while(IsDigital(c[i])){T->data[i]=c[i];i++;}T->len=i;T->lchild=T->rchild=NULL;PTR.push(T);returni;}voidCrtSubTree(stack<BiTree>&PTR,charc){BiTNode*T;T=(BiTNode*)malloc(sizeof(BiTNode));T->data=(char*)malloc(DATA_SIZE*sizeof(char));T->data[0]=c;T->len=1;T->rchild=PTR.top();//先右子树，否则运算次序反了PTR.pop();T->lchild=PTR.top();PTR.pop();PTR.push(T);}charsymbol[5][5]={{'>','>','<','<','>'},//符号优先级{'>','>','<','<','>'},{'>','>','>','>','>'},{'>','>','>','>','>'},{'<','<','<','<','='}};intsym2num(chars)//返回符号对应优先级矩阵位置{switch(s){case'+':return0;break;case'-':return1;break;case'*':return2;break;case'/':return3;break;case'#':return4;break;}}charPrecede(chara,charb)//返回符号优先级{return(symbol[sym2num(a)][sym2num(b)]);}voidCrtExptree(BiTree&T,charexp[]){//根据字符串exp的内容构建表达式树Tstack<BiTree>PTR;//存放表达式树中的节点指针stack<char>OPTR;//存放操作符charop;inti=0;OPTR.push('#');op=OPTR.top();while(!((exp[i]=='#')&&(OPTR.top()=='#')))//与{if(IsDigital(exp[i])){//建立叶子节点并入栈PTRi+=CrtNode(PTR,&exp[i]);}elseif(exp[i]=='')i++;else{switch(exp[i]){case'(':{OPTR.push(exp[i]);i++;break;}case')':{op=OPTR.top();OPTR.pop();while(op!='('){CrtSubTree(PTR,op);op=OPTR.top();OPTR.pop();}//endwhilei++;break;}default://exp[i]是+-*/while(!OPTR.empty()){op=OPTR.top();if(Precede(op,exp[i])=='>'){CrtSubTree(PTR,op);OPTR.pop();}if(exp[i]!='#'){OPTR.push(exp[i]);i++;}break;}}//endswitch}//endelse}//endwhileT=PTR.top();PTR.pop();}voidPostOrderTraverse(BiTree&T,char*exp,int&count){//后序遍历表达式树T，获取树中每个结点的数据值生成逆波兰表达式exp//T是表达式树的根节点；字符串exp保存逆波兰表达式；count保存exp中字符的个数//后序遍历中，处理根结点时，依据T->len的值，把T->data中的字符依次添加到当前exp字符串的尾端//添加完T->data后，再添加一个空格字符，同时更新count计数器的值。//填空//inti;if(T){PostOrderTraverse(T->lchild,exp,count);PostOrderTraverse(T->rchild,exp,count);strncpy(exp+count,T->data,T->len);exp[count+=(T->len)]='';count++;}}//---------------------------------//逆波兰表达式计算//填空StatusInitStack(SqStack&S){S.base=(SElemtype*)malloc(STACK_INIT_SIZE*sizeof(SElemtype));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;//printf("程序运行到构建栈\n");returnOK;}intStackLength(SqStackS){returnS.top-S.base;//printf("程序运行到获得堆栈元素的个数\n");//获得堆栈元素的个数}StatusPush(SqStack&S,SElemtypee){if(S.top-S.base>=S.stacksize){S.base=(SElemtype*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemtype));if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;//printf("程序运行到入栈\n");returnOK;//入栈}StatusPop(SqStack&S,SElemtype&e){if(S.top==S.base)returnERROR;e=*--S.top;//printf("程序运行到出栈\n");returnOK;//出栈}intEvalValue(char*ch,SqStack&S){inti=0;SElemtyperesult=0;chara;a=ch[i];while(IsDigital(a)){result=10*result+(int)(a-48);a=ch[++i];}Push(S,result);//printf("程序运行标志1\n");returni;}voidEvalExpr(charch,SqStack&S){floatp,q,r;if((ch=='+')||(ch=='-')||(ch=='*')||(ch=='/')){Pop(S,p);Pop(S,q);switch(ch){case'+':r=p+q;break;case'-':r=q-p;break;case'*':r=q*p;break;case'/':r=q/p;break;default:;}Push(S,r);//printf("程序运行标志2\n");}//如果ch中保存的是操作符，则从堆栈中弹出两个元素，并把操作符应用在这两个元素之上，//然后把操作结果压入到栈中。如果试图从栈中弹出两个元素是，该栈中并没有，那么该//后缀表达式是不正确的。}Statusevaluate(charch[],float&result){SqStackS;StatusSt;inti;i=0;St=InitStack(S);while(ch[i]!='#'&&i<100){if(IsDigital(ch[i])){i+=EvalValue(&ch[i],S);}elseif(ch[i]=='')i++;else{EvalExpr(ch[i],S);i++;}}//如果到达表达式末尾时，栈中剩余元素不止一个，那么该//后缀表达式是不正确的。if(StackLength(S)==1)Pop(S,result);else{//printf("表达式错误");returnERROR;}//printf("程序运行标志3\n");returnOK;}//--------