數(shù)據(jù)結構實驗報告-四則運算表達式求值

實驗五四則運算表達式求值一． 問題描述：四則運算表達式求值，將四則運算表達式用中綴表達式，然后轉換為后綴表達式，并計算結果。二． 基本要求：使用二叉樹來實現(xiàn)。三． 實現(xiàn)提示：利用二叉樹后序遍歷來實現(xiàn)表達式的轉換，同時可以使用實驗二的結果來求解后綴表達式的值。輸入輸出格式：輸入：在字符界面上輸入一個中綴表達式，回車表示結束。輸出：如果該中綴表達式正確，那么在字符界面上輸出其后綴表達式，其中后綴表達式中兩相鄰操作數(shù)之間利用空格隔開；如果不正確，在字符界面上輸出表達式錯誤提示。測試實例：輸入：21+23*（12-6）輸出：2123126-*+四．設計概要用二叉樹表示表達式：若表達式為數(shù)或簡單變量，則相應二叉樹中僅有一個根結點，其數(shù)據(jù)域存放該表達式信息若表達式=（第一操作數(shù)）（運算符）（第二操作數(shù)），則相應的二叉樹中以左子樹表示第一操作數(shù)，右子樹表示第二操作數(shù)，根結點的數(shù)據(jù)域存放運算符（若為一元算符，則左子樹空）。操作數(shù)本身又為表達式.后綴遍歷二叉樹碼實現(xiàn)和靜態(tài)檢查上機調(diào)試及測試數(shù)據(jù)的調(diào)試五．源程序：#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字符串中字符的個數(shù)structBiTNode*lchild,*rchild;}BiTNode,*BiTree;typedefstruct{SElemtype*base;SElemtype*top;intstacksize;}SqStack;StatusIsDigital(charch){if(ch>='0'&&ch<='9'){return1;//是數(shù)字字母}return0;//不是數(shù)字字母}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]={{'>','>','<','<','>'},//符號優(yōu)先級{'>','>','<','<','>'},{'>','>','>','>','>'},{'>','>','>','>','>'},{'<','<','<','<','='}};intsym2num(chars)//返回符號對應優(yōu)先級矩陣位置{switch(s){case'+':return0;break;case'-':return1;break;case'*':return2;break;case'/':return3;break;case'#':return4;break;}}charPrecede(chara,charb)//返回符號優(yōu)先級{return(symbol[sym2num(a)][sym2num(b)]);}voidCrtExptree(BiTree&T,charexp[]){//根據(jù)字符串exp的內(nèi)容構建表達式樹Tstack<BiTree>PTR;//存放表達式樹中的節(jié)點指針stack<char>OPTR;//存放操作符charop;inti=0;OPTR.push('#');op=OPTR.top();while(!((exp[i]=='#')&&(OPTR.top()=='#')))//與{if(IsDigital(exp[i])){//建立葉子節(jié)點并入棧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，獲取樹中每個結點的數(shù)據(jù)值生成逆波蘭表達式exp//T是表達式樹的根節(jié)點；字符串exp保存逆波蘭表達式；count保存exp中字符的個數(shù)//后序遍歷中，處理根結點時，依據(jù)T->len的值，把T->data中的字符依次添加到當前exp字符串的尾端//添加完T->data后，再添加一個空格字符，同時更新count計數(shù)器的值。//填空//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("程序運行到獲得堆棧元素的個數(shù)\n");//獲得堆棧元素的個數(shù)}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;}//--------