數(shù)據(jù)結構實驗報告

..課程設計實驗報告實驗名稱：表達式類型的實現(xiàn)編譯環(huán)境：硬件:PC軟件：VS2010問題描述一個表達式和一棵二叉樹之間,存在著自然的對應關系。寫一個程序,實現(xiàn)基于二叉樹表示的算術表達式Expression的操作。基本要求假設算術表達式Expression可以含有變量〔a～z、常量〔0~9和二元運算符〔+,-,*,/,^〔乘冪。實現(xiàn)以下操作。ReadExpr<E>——以字符序列的形式輸入語法正確的前綴表示式并構造表達式E。WriteExpr<E>——用帶括弧的前綴表示式輸出表達式E。Assign<V,c>——實現(xiàn)對變量V的賦值<V=c>,變量的初值為0。Value<E>——對算術表達式E求值。CompoundExpr<P,E1,E2>——構造一個新的復合表達式<E1>P<E2>。選作內容：增加常數(shù)合并操作MergeConst<E>-------合并表達式中E的所有常數(shù)運算。例如：表達式E=2+2*1-A進行合并常數(shù)的操作后,求得E=4-A〔2以表達式的原書寫形式輸入需求分析1．以字符序列的形式輸入語法正確的中綴表示式并構造表達式E。即要根據(jù)正確的前綴式建立一棵二叉樹T。2．用帶括弧的前綴表達式輸出表達式E。即要求在前綴遍歷二叉樹的時候考慮運算符的優(yōu)先級,在適當?shù)奈恢幂敵隼ɑ　?．實現(xiàn)對變量V的賦值〔V＝c,變量的初值為0。那就在中綴遍歷二叉樹的過程中比較結點的值是否為V,找到V以后將c賦給V。4．對算術表達式E求值。如果表達式中有變量的話,首先提示用戶表達式中變量,建議先執(zhí)行操作3〔實現(xiàn)對變量V賦值,執(zhí)行完后再回來執(zhí)行表達式求值這一步驟。表達式求值利用遞歸,如果某個結點的值為運算符并且它的左右孩子結點的值為數(shù)據(jù),那么就把〔左孩子〔運算符〔右孩子的結果賦給該結點。一層一層往上,最后只剩下一個根結點。此時根結點的值就是表達式E的值。5．構造一個新的復合表達式〔E1P〔E2。只要先構造表達式E1的二叉樹和E2的二叉樹,然后利用P把這兩棵二叉樹連接起來構成一棵新的二叉樹。6．合并表達式E中所有常數(shù)運算。此原理類似于對表達式E求值,不同之處只在于該功能只對常數(shù)合并。概要設計1.樹的抽象數(shù)據(jù)類型定義:ADTTree{數(shù)據(jù)對象D:D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關系R:若D為空集,則稱為空樹；若D僅含一個數(shù)據(jù)元素,則R為空集,否則R={H},H是如下二元關系：在D中存在唯一的稱為根的數(shù)據(jù)元素root,它在關系H下無前驅；若D-{root}≠ф,則存在D-{root}的一個劃分D1,D2,…Dm<m>0>,對任意j≠k<1<=j,k<=m>有Dj∩Dk=ф,且對任意的i<1≤i≤m>,唯一存在數(shù)據(jù)元素Xi∈Di,有<root,Xi>∈H；對應于D-{root}≠ф的劃分,H-{<root,Xi>…<root,Xm>}有唯一的一個劃分H1,H2…Hm<m>0>,對任意j≠k<1<=j,k<=m>有Dj∩Dk=ф,且對任意的i<1≤i≤m>,Hi是Di上的二元關系,<Di,{Hi}>是一棵符合本定義的樹,稱為根的root的子樹?；静僮?DoubleExpression<char*exp>;功能：算術表達式求值doublecalculate<doubleopnd1,charop,doubleopnd2>;功能：操作數(shù)四則運算voidpush<char,char,double,ExpressionCalculateStack*>;功能：入棧doublepop<char,ExpressionCalculateStack*>;功能：出棧voidGetNextNotation<char*notation,char*exp>;功能：讀下一個運算符或操作數(shù)charGetTypeOfNotation<char*notation>;功能：判定是運算符或是操作數(shù)intCompareOpPrior<charop2,charop1>;功能：運算符優(yōu)先級別比較BTNode*ReadExpr<chars[],inti,intj>功能：讀入表達式voidWriteExpr<BTNode*b>功能：/把輸入的表達式轉換為相應的二叉樹,并以前綴表達式的形式輸出charSeek<chars[],intk>功能：判斷是否有字母輸入voidCompoundExpr<charE1[],charE2[],charp>功能：復合表達式voidAssign<chars[],chari,charj>功能：對變量進行復制}流程圖：MMian函數(shù)對算術表達式求值查找式中的變量Seek以中綴方式輸入表達式ReadExpr以前綴方式輸出表達式WriteExpr對式中的變量進行復制Assign3菜單65412復合表達式對變量賦值,即執(zhí)行步驟3NY是否有變量對算術表達式求值查找式中的變量Seek以中綴方式輸入表達式ReadExpr以前綴方式輸出表達式WriteExpr對式中的變量進行復制Assign3菜單65412復合表達式對變量賦值,即執(zhí)行步驟3NY是否有變量常數(shù)合并常數(shù)合并程序清單：頭文件〔MyExpression.h#include<stdio.h>#include<malloc.h>#include<string.h>#include<math.h>#include<conio.h>#defineMaxSize100typedefcharElemType;typedefstructnode{ElemTypedata;structnode*lchild;structnode*rchild;}BTNode;#defineMAX_EXP_LEN128/*表達式最大長度*/#defineMAX_NOTATION_NUM32/*一個表達式中的最大算符個數(shù)*/#defineMAX_NOTATION_LEN20/*表達式中一個算符的最大字串長度*/#defineNULL0typedefstructstack{/*表達式計算堆棧*/doubleOpdStack[MAX_NOTATION_NUM];/*操作數(shù)堆棧*/charOpStack[MAX_NOTATION_NUM];/*運算符堆棧*/intOpdStackTop,/*操作數(shù)堆棧頂指針*/OpStackTop;/*運算符堆棧頂指針*/}ExpressionCalculateStack;#defineOPND'D'/*操作數(shù)類型標志*/#defineOPTR'R'/*運算符類型標志*/#defineCONTINUE_READ_NEXT_NOTATION'C'/*表達式掃描標志,繼續(xù)掃描*/#defineSTOP_READ_NEXT_NOTATION'S'/*表達式掃描標志,暫停掃描*//*部分子函數(shù)聲明如下〔主要是表達式求值函數(shù)*/doubleExpression<char*exp>;/*算術表達式求值*/doublecalculate<doubleopnd1,charop,doubleopnd2>;/*操作數(shù)四則運算*/voidpush<char,char,double,ExpressionCalculateStack*>;/*入棧*/doublepop<char,ExpressionCalculateStack*>;/*出棧*/voidGetNextNotation<char*notation,char*exp>;/*讀下一個運算符或操作數(shù)*/charGetTypeOfNotation<char*notation>;/*判定是運算符或是操作數(shù)*/intCompareOpPrior<charop2,charop1>;/*運算符優(yōu)先級別比較*/源代碼文件〔MyExpression.c#include"MyExpression.h"#include"stdlib.h"externdoubleExpression<char*oldexp>;externintCompareOpPrior<charop2,charop1>;externcharGetTypeOfNotation<char*notation>;externvoidGetNextNotation<char*notation,char*exp>;externdoublecalculate<doubleopnd1,charop,doubleopnd2>;externdoublepop<chartype,ExpressionCalculateStack*s>;externvoidpush<chartype,charop,doubleopnd,ExpressionCalculateStack*s>;BTNode*ReadExpr<chars[],inti,intj>{BTNode*p;intk,plus=0,posi;if<i==j>{p=<BTNode*>malloc<sizeof<BTNode>>;p->data=s[i];p->lchild=NULL;p->rchild=NULL;returnp;}//以下是i!=j的情況if<i!=j>{for<k=i;k<=j;k++> {if<s[k]=='+'||s[k]=='-'> { plus++; posi=k; }}if<plus==0>{ for<k=i;k<=j;k++> if<s[k]=='*'||s[k]=='/'> { plus++; posi=k; }} p=<BTNode*>malloc<sizeof<BTNode>>; p->data=s[posi]; p->lchild=ReadExpr<s,i,posi-1>; p->rchild=ReadExpr<s,posi+1,j>; returnp; // }}}voidWriteExpr<BTNode*b>//把輸入的表達式轉換為相應的二叉樹,并以前綴表達式的形式輸出{ if<b!=NULL> { printf<"%c",b->data>; if<b->lchild!=NULL||b->rchild!=NULL> { printf<"<">; WriteExpr<b->lchild>; if<b->rchild!=NULL> printf<",">; WriteExpr<b->rchild>; printf<">">; } }}charSeek<chars[],intk>//判斷是否有字母輸入{chara[1]={0};inti;for<i=0;i<=k;i++> if<s[i]>='A'&&s[i]<='Z'||s[i]>='a'&&s[i]<='z'> returna[0]='1';}voidAssign<chars[],chari,charj>{for<intp=0;p<=strlen<s>-1;p++> if<s[p]==i> s[p]=j;}voidCompoundExpr<charE1[],charE2[],charp>//復合表達式{charNewE[MaxSize],q[1];intk=0,i;BTNode*bt1,*bt2,*T;if<p=='+'||p=='-'>//復合函數(shù)為+或-是應怎樣復合{for<i=0;i<strlen<E1>;i++> NewE[i]=E1[i]; NewE[strlen<E1>]=p; for<k=0;k<strlen<E2>;i++,k++> NewE[i+1]=E2[k]; NewE[i+1]='\0'; printf<"復合后的表達式為：%s\n\n",NewE>;printf<"其對應的二叉樹為：">; T=ReadExpr<NewE ,0,strlen<NewE>-1>; WriteExpr<T>; printf<"\n">;}else{printf<"復合的表達式為：">;//復合符號為*或/是應該怎樣復合這兩個表達式bt1=ReadExpr<E1,0,strlen<E1>-1>;printf<"<">;WriteExpr<bt1>;printf<">">;printf<"%c",p>;bt2=ReadExpr<E2,0,strlen<E2>-1>;printf<"<">;WriteExpr<bt2>;printf<">">;printf<"\n">;}}voidConbination<chars[],intk>//對常數(shù)項進行合并{//intFX=0;if<s[k]=='*'>{if<<s[k-1]>='0'&&s[k-1]<='9'>&&<s[k+1]>='0'&&s[k+1]<='9'>>//判斷是否為數(shù)字{/*FX=s[k-1]*s[k+1];s[k-1]=FX;*/ s[k-1]=<s[k-1]-48>*<s[k+1]-48>+48;for<inti=k;i<strlen<s>;i++> s[i]=s[i+2];}}if<s[k]=='/'>{if<<s[k-1]>='0'&&s[k-1]<='9'>&&<s[k+1]>='0'&&s[k+1]<='9'>>{s[k-1]=<s[k-1]-48>/<s[k+1]-48>+48;for<inti=k;i<strlen<s>;i++> s[i]=s[i+2];}}if<s[k]=='+'>{if<<s[k-1]>='0'&&s[k-1]<='9'>&&<s[k+1]>='0'&&s[k+1]<='9'>>{s[k-1]=<s[k-1]-48>+<s[k+1]-48>+48;for<inti=k;i<strlen<s>;i++> s[i]=s[i+2];}}if<s[k]=='-'>{if<<s[k-1]>='0'&&s[k-1]<='9'>&&<s[k+1]>='0'&&s[k+1]<='9'>>{s[k-1]=<s[k-1]-48>-<s[k+1]-48>+48;for<inti=k;i<strlen<s>;i++> s[i]=s[i+2];}}printf<"常數(shù)合并后為：%s",s>; }voidMergeConst<chars[]>//常數(shù)合并{inti,j,n;for<i=0;i<strlen<s>;i++>{if<s[i]=='*'||s[i]=='/'> Conbination<s,i>;}for<j=0;j<strlen<s>;j++>{if<s[j]=='+'||s[j]=='-'> Conbination<s,j>;}}voidmain<>{doublefx=0;BTNode*b;inti=0,j=0;chars[MaxSize],yesORno,value,getvalue,GetDigitl=NULL,p,E1[7],E2[3],e1,e2;printf<"\n\n表達式類型實現(xiàn)的使用說明：\n\n">;printf<"表達式暫時還不能進行括號操作,請不要輸入括號,\n\n">;printf<"數(shù)字的輸入只能是一位數(shù)〔0-9,字母的輸入a-z或A-Z\n\n">;printf<"表達式輸入時請按以下形式輸入：A-S+D\n\n">;printf<"************************************\n\n">;printf<"1.輸入表達式2.輸出表達式\n\n">;printf<"3.對變量賦值4.對表達式求值\n\n">;printf<"5.復合表達式6.常數(shù)合并\n\n">;printf<"7.返回\n\n">;printf<"************************************\n\n">;printf<"請輸入選擇〔1-7">;while<<GetDigitl=getchar<>>!='7'>{switch<GetDigitl> {case'1':{printf<"\n\n請以中綴表達式形式輸入表達式,例如a+b*c/d\n\n">;printf<"你的輸入">;getchar<>;gets<s>;//以中綴表達式形式輸入表達式printf<"\n">;printf<"你輸入的表達式為:%s\n",s>;b=ReadExpr<s,0,strlen<s>-1>; printf<"\n請輸入選擇〔1-7\n">; break; } case'2': { printf<"\n對應的二叉樹：">; WriteExpr<b>; printf<"\n\n">; printf<"\n請輸入選擇〔1-7\n">; break; } case'3': {while<<yesORno=Seek<s,strlen<s>-1>>=='1'> { printf<"表示式中有變量！\n">; getchar<>;printf<"需要賦值的變量：">; value=getchar<>; getchar<>; printf<"變量值：">; getvalue=getchar<>; Assign<s,value,getvalue>; } b=ReadExpr<s,0,strlen<s>-1>; printf<"\n對應的二叉樹：">;WriteExpr<b>;printf<"\n請輸入選擇〔1-7\n">; break; } case'4': {yesORno=Seek<s,strlen<s>-1>; if<yesORno=='1'> printf<"表達式中有未知變量,請選擇3進行變量賦值\n">; else { fx=Expression<s>;/*表達式求值*/printf<"\n表達式的運算結果為:%f\n",fx>; } printf<"\n請輸入選擇〔1-7\n">; break; } case'5': { printf<"請從〔+、-、*、/中選擇一個作為復合符號\n">; printf<"你的選擇是：">; getchar<>; p=getchar<>; printf<"\n">; printf<"請輸入要復合的第一個表達式：">; getchar<>; gets<E1>; printf<"\n">; printf<"請輸入要復合的第二個表達式:">; gets<E2>; printf<"\n">; CompoundExpr<E1,E2,p>;printf<"\n請輸入選擇〔1-7\n">; break; } case'6': {MergeConst<s>; printf<"\n請輸入選擇〔1-7\n">; break; }} }}//一下是表達式求值函數(shù)#include"MyExpression.h"doubleExpression<char*oldexp>//表達式計算函數(shù),輸入的是表達式字符串{charnotation[MAX_NOTATION_LEN],//存放當前符號掃描讀入的符號op1,op2,exp[MAX_EXP_LEN];//存放當前操作表達式charflag=CONTINUE_READ_NEXT_NOTATION;//判別是否繼續(xù)掃描下去intprior;//存放算符優(yōu)先級別比較結果:op2<op1:-1op2>op1:1//op2=op1:0doubleopnd1,opnd2;//存放當前用于計算的2個操作數(shù)ExpressionCalculateStacks;//定義堆棧ss.OpdStackTop=s.OpStackTop=0;strcpy<exp,oldexp>;//把原表達式復制給當前操作表達式strcat<exp,"#">;//把‘#’接到exp后面,原exp最后面的‘\0’被取消push<OPTR,'#',0.0,&s>;//初始化表達式計算堆棧while<1>{if<flag==CONTINUE_READ_NEXT_NOTATION>GetNextNotation<notation,exp>;else/*有運算結果進操作數(shù)棧后*/flag=CONTINUE_READ_NEXT_NOTATION;if<GetTypeOfNotation<notation>==OPND>{opnd2=atof<notation>;push<OPND,NULL,opnd2,&s>;//操作數(shù)處理}else//運算符處理{op2=notation[0];op1=<char>pop<OPTR,&s>;//運算符出棧prior=CompareOpPrior<op2,op1>;if<prior<0>//op2<op1{push<OPTR,op1,0.0,&s>;//剛出棧的運算符再次進棧push<OPTR,op2,0.0,&s>;//當前運算符優(yōu)先級別高,進棧}if<prior>0>//op2>op2{opnd2=pop<OPND,&s>;opnd1=pop<OPND,&s>;opnd2=calculate<opnd1,op1,opnd2>;push<OPND,NULL,opnd2,&s>;flag=STOP_READ_NEXT_NOTATION;///暫停讀入下一個表達式符號//使當前運算符與棧頂運算符再作一次比較}if<prior==0>//op2=op1的情況處理{if<op2=='#'>returnpop<OPND,&s>;//結束運算,將運算結果從堆棧中彈出}}}}voidpush<chartype,charop,doubleopnd,ExpressionCalculateStack*s>{if<type==OPND>s->OpdStack[s->OpdStackTop++]=opnd;elses->OpStack[s->OpStackTop++]=op;}doublepop<chartype,ExpressionCalculateStack*s>{if<type==OPND>//是操作數(shù)棧returns->OpdStack[--s->OpdStackTop];else//是運算符棧return<double><s->OpStack[--s->OpStackTop]>;}doublecalculate<doubleopnd1,charop,doubleopnd2>{switch<op>{case'+':returnopnd1+opnd2;case'-':returnopnd1-opnd2;case'*':returnopnd1*opnd2;case'/':if<opnd2!=0.0>returnopnd1/opnd2;elsereturn0.0;}return0.0;}voidGetNextNotation<char*notation,char*exp>//讀入下一個完整的符號:操作數(shù)或運算符{//把一個完整的操作數(shù)或運算符保存到notation[]staticinti=0;//變量i為表達式掃描的當前位置,注意其類型intj;chartype,lasttype=GetTypeOfNotation<exp+i>;for<j=0;exp[i]!='\0';j++,i++>{if<exp[i]==''>continue;notation[j]=exp[i];type=GetTypeOfNotation<notation+j>;if<type==OPTR&&lasttype==OPTR>{i++,j++;break;}//第一次讀到的就是//運算符if<type==OPTR&&lasttype==OPND>break;//由讀到的不是運算符轉為讀到的是運算符lasttype=type;}notation[j]=NULL;if<notation[0]=='#'>i=0;//表達式掃描完畢}charGetTypeOfNotation<char*notation>//判斷一個字符是不是運算符{charopstr[]="+-*/<>#";//運算符集inti;if<notation[0]=='\0'>returnNULL;for<i=0;opstr[i]!='\0';i++>if<notation[0]==opstr[i]>returnOPTR;//'R'即是運算符returnOPND;//'D'即是操作數(shù)或小數(shù)點或其它如空格等}intCompareOpPrior<charop2,charop1>//2個先后出現(xiàn)的運算符優(yōu)先級別比較：按P53表3.1//定{charopstr[]="+-*/<>#";inti,j;intpriortable[7][7]=//+-*/<>#{1,1,-1,-1,-1,1,1,1,1,-1,-1,-1,1,1,1,1,1,1,-1,1,1,1,1,1,1,-1,1,1,-1,-1,-1,-1,-1,0,'I',1,1,1,1,'I',1,1,-1,-1,-1,-1,-1,'I',0,};for<i=0;opstr[i]!='\0';i++>i