《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計》表達式求值實驗報告

實驗課程名稱 專業(yè)班級學(xué)生姓名學(xué)號指導(dǎo)教師20至20學(xué)年第學(xué)期第至周算術(shù)表達式求值演示概述數(shù)據(jù)結(jié)構(gòu)課程設(shè)計?要求學(xué)生在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇和應(yīng)用、算法的設(shè)計及其實現(xiàn)等方面?加深對課程基本內(nèi)容的理解。同時?在程序設(shè)計方法以及上機操作等基本技能和科學(xué)作風(fēng)方面受到比較系統(tǒng)和嚴格的訓(xùn)練。在這次的課程設(shè)計中我選擇的題目是算術(shù)表達式求值演示。表達式計算是實現(xiàn)程序設(shè)計語言的基本問題之一?也是棧的應(yīng)用的一個典型例子。設(shè)計一個程序?演示用算符優(yōu)先法對算術(shù)表達式求值的過程。深入了解棧和隊列的特性.以便在解決實際問題中靈活運用它們.同時加深對這種結(jié)構(gòu)的理解和認識。二、系統(tǒng)分析以字符列的形式從終端輸入語法正確的、不含變量的整數(shù)表達式。利用已知的算符優(yōu)先關(guān)系?實現(xiàn)對算術(shù)四則混合運算表達式的求值?并仿照教科書的例子在求值中運算符棧、運算數(shù)棧、輸入字符和主要操作的變化過程。一般來說?計算機解決一個具體問題時.需要經(jīng)過幾個步驟：首先要從具體問題抽象出一個適當?shù)臄?shù)學(xué)模型?然后設(shè)計一個解決此數(shù)學(xué)模型的算法?最后編出程序?進行測試.調(diào)試直至得到想要的答案。對于算術(shù)表達式這個程序?主要利用棧?把運算的先后步驟進行分析并實現(xiàn)簡單的運算！為實現(xiàn)算符優(yōu)先算法.可以使用兩個棧?一個用以寄存運算符?另一個用以寄存操作數(shù)和運算結(jié)果。演示程序是以用戶于計算機的對話方式執(zhí)行?這需要一個模塊來完成使用者與計算機語言的轉(zhuǎn)化。程序執(zhí)行時的命令：本程序為了使用具體?采用菜單式的方式來完成程序的演示?幾乎不用輸入什么特殊的命令?只需按提示輸入表達式即可。（要注意輸入時格式?否者可能會引起一些錯誤）測試數(shù)據(jù)。三、概要設(shè)計一個算術(shù)表達式中除了括號、界限符外?還包括運算數(shù)據(jù)和運算符。由于運算符有優(yōu)先級別之差.所以一個表達式的運算不可能總是從左至右的循序執(zhí)行。每次操作的數(shù)據(jù)或運算符都是最近輸入的.這與棧的特性相吻合?故本課程設(shè)計借助棧來實現(xiàn)按運算符的優(yōu)先級完成表達式的求值計算。算法設(shè)計程序包含三個模塊主程序模塊?其中主函數(shù)為voidmain{輸入表達式；根據(jù)要求進行轉(zhuǎn)換并求值；輸出結(jié)果；}表達式求值模塊——實現(xiàn)具體求值。表達式轉(zhuǎn)換模塊——實現(xiàn)轉(zhuǎn)換。各個函數(shù)之間的調(diào)用關(guān)系棧的抽象數(shù)據(jù)類型定義ADTSqStack{數(shù)據(jù)對象：D={a|aWEIemSet,i二1,2,3 .n,n$O}TOC\o"1-5"\h\zi i數(shù)據(jù)關(guān)系：R1={<a,a>|a,aWD,i=1,2,3,…….n}i-1i i-1i約定其中a端為棧底.a端為棧頂。i n操作集合：voidInitStack1(SqStackl&S1);//聲明棧建立函數(shù)voidInitStack2(SqStack2&S2);//聲明棧建立函數(shù)voidevaluate(SqStack1&S1,SqStack2&S2)；//確定如何入棧函數(shù)voidPush1(SqStack1&S1,chare);//聲明入棧函數(shù)voidPush2(SqStack2&S2,floate);//聲明入壓棧函數(shù)charGetTop1(SqStack1&S1);//聲明取棧頂元素函數(shù)floatGetTop2(SqStack2&S2);//聲明取棧頂元素函數(shù)charPop1(SqStack1&S1);//聲明出棧函數(shù)floatPop2(SqStack2&S2);//聲明出棧函數(shù)charCompare(charm,charn);//聲明比較函數(shù)floatOperate(floata,charrheta,floatb);//聲明運算函數(shù)voidDispStack1(SqStack1&S1);//從棧底到棧頂依次輸出各元素voidDispStack2(SqStack2&S2);//從棧底到棧頂依次輸出各元素}ADTSqStack結(jié)構(gòu)分析：棧中的數(shù)據(jù)節(jié)點是通過數(shù)組來存儲的。因為在C語言中數(shù)組是用下標從零開始的.因此我們在調(diào)用他們的數(shù)據(jù)是要特別注意。指針變量的值要么為空(NULL)?不指向任何結(jié)點；要么其值為非空.即它的值是一個結(jié)點的存儲地址。注意.當P為空值時?則它不指向任何結(jié)點?此時不能通過P來訪問結(jié)點?否則會引起程序錯誤。如果輸入的數(shù)字不符合題目要求則會產(chǎn)生錯誤結(jié)果。算法的時空分析：時間和空間性能分析：時間上?對于含n個字符的表達式?無論是對其進行合法性檢測還是對其進行入棧出棧操作n次.因此其時間復(fù)雜度為O(n)?？臻g上.由于是用數(shù)組來存儲輸入的表達式.用棧來存儲運算中的數(shù)據(jù)和運算符.而棧的本質(zhì)也用到的數(shù)組?數(shù)組在定義時必須確定其大小。在不知表達式長度的情況下確定數(shù)組的長度確非易事?此時極易造成空間的浪費.因此空間性能不是很好。四、詳細設(shè)計源程序#include<iostream>usingnamespacestd;#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefstruct//運算符棧{char*base;char*top;intstacksize;}SqStack1;typedefstruct//運算數(shù)棧{float*base;float*top;intstacksize;}SqStack2；voidInitStack1(SqStack1&S1);//聲明棧建立函數(shù)voidInitStack2(SqStack2&S2);//聲明棧建立函數(shù)voidevaluate(SqStack1&S1,SqStack2&S2)；//確定如何入棧函數(shù)voidPush1(SqStack1&S1,chare);//聲明入棧函數(shù)voidPush2(SqStack2&S2,floate);//聲明入壓棧函數(shù)charGetTop1(SqStack1&S1);//聲明取棧頂元素函數(shù)floatGetTop2(SqStack2&S2);//聲明取棧頂元素函數(shù)charPop1(SqStack1&S1);//聲明出棧函數(shù)floatPop2(SqStack2&S2);//聲明出棧函數(shù)charCompare(charm,charn);//聲明比較函數(shù)floatOperate(floata,charrheta,floatb);//聲明運算函數(shù)voidDispStack1(SqStack1&S1);//從棧底到棧頂依次輸出各元素voidDispStack2(SqStack2&S2);//從棧底到棧頂依次輸出各元素/*主函數(shù)*/voidmain(){SqStack1S1;//定義運算符棧SqStack2S2;//定義運算數(shù)棧//freopen("data1.in","r",stdin);//freopen("data1.out","w",stdout);InitStack1(S1);//調(diào)用棧建立函數(shù)InitStack2(S2)；//調(diào)用棧建立函數(shù)evaluate(S1,S2)；//調(diào)用確定如何入棧函數(shù)cout<<"按任意鍵結(jié)束！"<<endl;}/*運算符棧函數(shù)*/voidInitStack1(SqStack1&S1)//構(gòu)造一個空棧S1{S1.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char));if(!S1.base)cout<<"存儲分配失??！"；//存儲分配失敗S1.top二S1.base;S1.stacksize二STACK_INIT_SIZE;}voidPush1(SqStackl&S1,chare)//入棧{if(S1.top-S1.base>二S1.stacksize)//如果棧滿.追加存儲空間{S1.base=(char*)realloc(S1.base,(S1.stacksize+STACKINCREMENT)*sizeof(char));if(!S1.base) cout<<"存儲分配失??！"；else{S1.top二S1.base+S1.stacksize;S1.stacksize二S1.stacksize+STACKINCREMENT;}}*S1.top二e;S1.top=S1.top+1;//將元素壓入棧中.指針上移}charGetTop1(SqStackl&S1)//取棧頂元素{chare;if(S1.top二二S1.base)cout<<"\n\t\t\t運算符棧已空！\n";elsee=*(S1.topT);returne;}voidDispStack1(SqStackl&S1)//從棧底到棧頂依次輸出各元素{chare,*p;if(S1.top二二S1.base)cout<<"”；else{p二Sl.base;while(p<S1.top){e=*p;P++；cout<<e;}}}charPop1(SqStackl&S1)//出棧{chare;if(S1.top二二S1.base)cout<<"\n\t\t\t運算符棧已空！\n";e=*(一S1.top);returne;}/*運算數(shù)棧函數(shù)*/voidInitStack2(SqStack2&S2)//構(gòu)造一個空棧S2{S2.base=(float*)malloc(STACK_INIT_SIZE*sizeof(float));if(!S2.base)cout<<"存儲分配失?。?；//存儲分配失敗S2.top二S2.base;S2.stacksize二STACK_INIT_SIZE;}voidPush2(SqStack2&S2,floate)//入棧{if(S2.top-S2.base>二S2.stacksize)//棧滿.追加存儲空間{S2.base=(float*)realloc(S2.base,(S2.stacksize+STACKINCREMENT)*sizeof(float));if(!S2.base)cout<<"存儲分配失??！"；else{S2.top=S2.base+S2.stacksize;S2.stacksize二S2.stacksize+STACKINCREMENT;}}*S2.top二e;S2.top=S2.top+1;//將元素e入棧.指針上移}voidDispStack2(SqStack2&S2)//從棧底到棧頂依次輸出各元素{floate,*p;if(S2.top二二S2.base)cout<<"”；elsep二S2.base;while(p<S2.top){e=*p;P++；cout<<e;}}}floatGetTop2(SqStack2&S2)//取棧頂元素{floate;if(S2.top==S2.base)cout<<"\n\t\t運算數(shù)棧已空！"；elsee=*(S2.top-1);returne;}floatPop2(SqStack2&S2)//出棧{floate;if(S2.top==S2.base)cout<<"\n\t\t運算數(shù)棧已空！"；e=*(一S2.top);returne;}/*確定如何入棧函數(shù)*/voidevaluate(SqStack1&S1,SqStack2&S2){charc;floatt,e;intn=O,i=1,j=O,k=O,l=O；charch[STACK_INIT_SIZE];ints—1;intflag=0,flag2=0；floatp1,p2；charch1;Push1(S1,'#');//將'#'入棧?作為低級運算符cout<<"?請輸入不含變量的表達式(以#結(jié)束！)：\n";cin>>ch;c=ch[0];cout<<"\n?對表達式求值的操作過程如下："<<"\n __\n"<<"步驟\t運算符棧S1\t運算數(shù)棧S2\t輸入字符\t\t主要操作"；while(c!='#'||GetTop1(S1)!='#')cout<<"\n \n";cout<<i++<<"\t";DispStack1(S1);cout<<"\t\t";DispStack2(S2)；cout<<"\t\t";if(flag==1){k——;flag=0;}if(flag2){k+=flag2;flag2=0；}for(l=0;l<k;l++)cout<<'';for(j=k;ch[j]!='\0';j++)cout<<ch[j];if(ch[k]!二’#'&&flag!=1){k++；flag=0；}as:if(!(c二二'+'||c二二'—’||c二二'*'||c二二'/'||c二二’(’||c二二’)’||c二二'#')){//輸入的字符如果不是運算符號?則繼續(xù)輸入直到輸入的是運算符為止?將非運算符轉(zhuǎn)換成浮點數(shù)if(!(c二二'.')&&?>二0){e二float(c—48);n++;if(n=1)t；e;elseif(n>1)t二t*10+e;c=ch[s++];}if(n=-1){e=float(c—48);t二t+e/10;c=ch[s++];}if(c='.'){?二—1；c=ch[s++];}if((c>二'O'&&c<='9')||c二二'.'){flag2++；gotoas;}if(c<'0'||c>9){Push2(S2,t);}cout<<"\t\tPush2(S2,"<<t<<")";}else//輸入的是運算符{n=0;//非運算型數(shù)據(jù)計數(shù)器清零switch(Compare(GetTop1(S1),c))//比較運算符的優(yōu)先級{case'<'://棧頂元素優(yōu)先級低.則入棧且繼續(xù)輸入Push1(S1,c);cout<<"\t\tPush1(S1,"<<c<<")";c=ch[s++];break;case'='://棧頂元素優(yōu)先級相等?脫括號并接收下一字符Pop1(S1);cout<<"\t\tPop1(S1)";c=ch[s++];break;case'>'://棧頂元素優(yōu)先級高?則退棧并將運算結(jié)果入棧p仁Pop2(S2);p2=Pop2(S2);ch仁Pop1(S1);Push2(S2,Operate(p2,ch1,p1));cout<<"\t\tOperate("<<p2<<','<<ch1<<','<<p1<<')';flag=1;break;}}}cout<<"\n \n";cout<<i<<'\t'<<'#'<<"\t\t"<<GetTop2(S2)<<"\t\t";for(j=0;j<k;j++)cout<<'';cout<<"#"<<"\t\t"<<"RETURN(GETT0P(S2))"；cout<<"\n \n";if(S2.top-1二二S2.base)//顯示表達式最終結(jié)果cout<<"\n?表達式的結(jié)果為："<<GetTop2(S2)<<endl;elsecout<<"\n表達式出錯!\n";}charCompare（charm,charn）//運算符的優(yōu)先級比較{if（n二二'+'||n二二'一'）//輸入符號為"+"、"-"{if（m二二’（’||m二二'#'）return'<';//棧頂元素為"（"、"#",此時棧頂符號優(yōu)先級低?返回"<"elsereturn'>';//否則.棧頂符號優(yōu)先級高，返回">"}elseif（n二二'*'||n二二'/'）//輸入的符號為"*"、"/"{if（m二二'）’||m二二'*'||m二二'/'）return'>';//棧頂元素為"）"、"*"、"/",此時棧頂符號優(yōu)先級高?返回">"elsereturn'<';//否則.棧頂符號優(yōu)先級低，返回"<"}elseif（n二二’（'）return'<';//輸入的符號為"（"，則直接返回"<"elseif（n二二'）’）//輸入的符號為"）"{if（m二二’（'）return'二’；//棧頂元素為"（"，此時優(yōu)先級同?返回"二"elsereturn'>';//否則.棧頂符號優(yōu)先級高，返回">"}else //輸入符號為其他{if（m二二'#'）return'二’；//棧頂元素為"#",此時優(yōu)先級同?返回"二"elsereturn'>';//否則.棧頂符號優(yōu)先級高，返回">"}}floatOperate（floata,chartheta,floatb）//運算函數(shù){floattmp=0;if （theta二二'+'）tmp二a+b;//從運算符棧取出的符號為"+".則運算數(shù)棧的兩元素相加.并返回elseif（theta二二'-'）tmp二a-b;//從運算符棧取出的符號為"-".