數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-四則運(yùn)算表達(dá)式求值

實(shí)驗(yàn)五四則運(yùn)算表達(dá)式求值一． 問題描述：四則運(yùn)算表達(dá)式求值，將四則運(yùn)算表達(dá)式用中綴表達(dá)式，然后轉(zhuǎn)換為后綴表達(dá)式，并計(jì)算結(jié)果。二． 基本要求：使用二叉樹來實(shí)現(xiàn)。三． 實(shí)現(xiàn)提示：利用二叉樹后序遍歷來實(shí)現(xiàn)表達(dá)式的轉(zhuǎn)換，同時(shí)可以使用實(shí)驗(yàn)二的結(jié)果來求解后綴表達(dá)式的值。輸入輸出格式：輸入：在字符界面上輸入一個(gè)中綴表達(dá)式，回車表示結(jié)束。輸出：如果該中綴表達(dá)式正確，那么在字符界面上輸出其后綴表達(dá)式，其中后綴表達(dá)式中兩相鄰操作數(shù)之間利用空格隔開；如果不正確，在字符界面上輸出表達(dá)式錯誤提示。測試實(shí)例：輸入：21+23*（12-6）輸出：2123126-*+四．設(shè)計(jì)概要用二叉樹表示表達(dá)式：若表達(dá)式為數(shù)或簡單變量，則相應(yīng)二叉樹中僅有一個(gè)根結(jié)點(diǎn)，其數(shù)據(jù)域存放該表達(dá)式信息若表達(dá)式=（第一操作數(shù)）（運(yùn)算符）（第二操作數(shù)），則相應(yīng)的二叉樹中以左子樹表示第一操作數(shù)，右子樹表示第二操作數(shù)，根結(jié)點(diǎn)的數(shù)據(jù)域存放運(yùn)算符（若為一元算符，則左子樹空）。操作數(shù)本身又為表達(dá)式.后綴遍歷二叉樹碼實(shí)現(xiàn)和靜態(tài)檢查上機(jī)調(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字符串中字符的個(gè)數(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();//先右子樹，否則運(yùn)算次序反了PTR.pop();T->lchild=PTR.top();PTR.pop();PTR.push(T);}charsymbol[5][5]={{'>','>','<','<','>'},//符號優(yōu)先級{'>','>','<','<','>'},{'>','>','>','>','>'},{'>','>','>','>','>'},{'<','<','<','<','='}};intsym2num(chars)//返回符號對應(yīng)優(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)容構(gòu)建表達(dá)式樹Tstack<BiTree>PTR;//存放表達(dá)式樹中的節(jié)點(diǎn)指針stack<char>OPTR;//存放操作符charop;inti=0;OPTR.push('#');op=OPTR.top();while(!((exp[i]=='#')&&(OPTR.top()=='#')))//與{if(IsDigital(exp[i])){//建立葉子節(jié)點(diǎn)并入棧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){//后序遍歷表達(dá)式樹T，獲取樹中每個(gè)結(jié)點(diǎn)的數(shù)據(jù)值生成逆波蘭表達(dá)式exp//T是表達(dá)式樹的根節(jié)點(diǎn)；字符串exp保存逆波蘭表達(dá)式；count保存exp中字符的個(gè)數(shù)//后序遍歷中，處理根結(jié)點(diǎn)時(shí)，依據(jù)T->len的值，把T->data中的字符依次添加到當(dāng)前exp字符串的尾端//添加完T->data后，再添加一個(gè)空格字符，同時(shí)更新count計(jì)數(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++;}}//---------------------------------//逆波蘭表達(dá)式計(jì)算//填空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("程序運(yùn)行到構(gòu)建棧\n");returnOK;}intStackLength(SqStackS){returnS.top-S.base;//printf("程序運(yùn)行到獲得堆棧元素的個(gè)數(shù)\n");//獲得堆棧元素的個(gè)數(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("程序運(yùn)行到入棧\n");returnOK;//入棧}StatusPop(SqStack&S,SElemtype&e){if(S.top==S.base)returnERROR;e=*--S.top;//printf("程序運(yùn)行到出棧\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("程序運(yùn)行標(biāo)志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("程序運(yùn)行標(biāo)志2\n");}//如果ch中保存的是操作符，則從堆棧中彈出兩個(gè)元素，并把操作符應(yīng)用在這兩個(gè)元素之上，//然后把操作結(jié)果壓入到棧中。如果試圖從棧中彈出兩個(gè)元素是，該棧中并沒有，那么該//后綴表達(dá)式是不正確的。}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++;}}//如果到達(dá)表達(dá)式末尾時(shí)，棧中剩余元素不止一個(gè)，那么該//后綴表達(dá)式是不正確的。if(StackLength(S)==1)Pop(S,result);else{//printf("表達(dá)式錯誤");returnERROR;}//printf("程序運(yùn)行標(biāo)志3\n");returnOK;}//--------