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

實驗課程名稱 專 業(yè) 班 級 學(xué) 生 姓 名 學(xué) 號 指 導(dǎo) 教 師 20 至 20 學(xué)年第 學(xué)期第 至 周算術(shù)表達式求值演示1、 概述 數(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)分析1 以字符列的形式從終端輸入語法正確的、不含變量的整數(shù)表達式。利用已知的算符優(yōu)先關(guān)系，實現(xiàn)對算術(shù)四則混合運算表達式的求值，并仿照教科書的例子在求值中運算符棧、運算數(shù)棧、輸入字符和主要操作的變化過程。2 一般來說，計算機解決一個具體問題時，需要經(jīng)過幾個步驟：首先要從具體問題抽象出一個適當(dāng)?shù)臄?shù)學(xué)模型，然后設(shè)計一個解決此數(shù)學(xué)模型的算法，最后編出程序，進行測試，調(diào)試直至得到想要的答案。對于算術(shù)表達式這個程序，主要利用棧，把運算的先后步驟進行分析并實現(xiàn)簡單的運算！為實現(xiàn)算符優(yōu)先算法，可以使用兩個棧，一個用以寄存運算符，另一個用以寄存操作數(shù)和運算結(jié)果。3 演示程序是以用戶于計算機的對話方式執(zhí)行，這需要一個模塊來完成使用者與計算機語言的轉(zhuǎn)化。4 程序執(zhí)行時的命令： 本程序為了使用具體，采用菜單式的方式來完成程序的演示，幾乎不用輸入什么特殊的命令，只需按提示輸入表達式即可。（要注意輸入時格式，否者可能會引起一些錯誤）5. 測試數(shù)據(jù)。三、 概要設(shè)計一個算術(shù)表達式中除了括號、界限符外，還包括運算數(shù)據(jù)和運算符。由于運算符有優(yōu)先級別之差，所以一個表達式的運算不可能總是從左至右的循序執(zhí)行。每次操作的數(shù)據(jù)或運算符都是最近輸入的，這與棧的特性相吻合，故本課程設(shè)計借助棧來實現(xiàn)按運算符的優(yōu)先級完成表達式的求值計算。算法設(shè)計程序包含三個模塊(1) 主程序模塊，其中主函數(shù)為void main輸入表達式；根據(jù)要求進行轉(zhuǎn)換并求值；輸出結(jié)果；(2) 表達式求值模塊實現(xiàn)具體求值。(3) 表達式轉(zhuǎn)換模塊實現(xiàn)轉(zhuǎn)換。各個函數(shù)之間的調(diào)用關(guān)系主函數(shù)表達式轉(zhuǎn)換表達式求值數(shù)據(jù)輸入輸出輸出 棧的抽象數(shù)據(jù)類型定義ADT SqStack數(shù)據(jù)對象：D=ai| ai ElemSet,i=1,2,3，n,n0數(shù)據(jù)關(guān)系：R1=<ai-1,ai>| ai-1,ai D,i=1,2,3,，n 約定其中ai端為棧底，an端為棧頂。 操作集合：(1)void InitStack1(SqStack1 &S1);/聲明棧建立函數(shù)(2)void InitStack2(SqStack2 &S2);/聲明棧建立函數(shù)(3)void evaluate(SqStack1 &S1,SqStack2 &S2);/確定如何入棧函數(shù)(4)void Push1(SqStack1 &S1,char e);/聲明入棧函數(shù)(5)void Push2(SqStack2 &S2,float e);/聲明入壓棧函數(shù)(6)char GetTop1(SqStack1 &S1);/聲明取棧頂元素函數(shù)(7)float GetTop2(SqStack2 &S2);/聲明取棧頂元素函數(shù)(8)char Pop1(SqStack1 &S1);/聲明出棧函數(shù)(9)float Pop2(SqStack2 &S2);/聲明出棧函數(shù)(10)char Compare(char m,char n);/聲明比較函數(shù)(11)float Operate(float a,char rheta,float b);/聲明運算函數(shù)(12)void DispStack1(SqStack1 &S1);/從棧底到棧頂依次輸出各元素(13)void DispStack2(SqStack2 &S2);/從棧底到棧頂依次輸出各元素 ADT SqStack結(jié)構(gòu)分析:棧中的數(shù)據(jù)節(jié)點是通過數(shù)組來存儲的。因為在C語言中數(shù)組是用下標從零開始的，因此我們在調(diào)用他們的數(shù)據(jù)是要特別注意。指針變量的值要么為空(NULL)，不指向任何結(jié)點；要么其值為非空，即它的值是一個結(jié)點的存儲地址。注意，當(dāng)P為空值時，則它不指向任何結(jié)點，此時不能通過P來訪問結(jié)點，否則會引起程序錯誤。如果輸入的數(shù)字不符合題目要求，則會產(chǎn)生錯誤結(jié)果。算法的時空分析：時間和空間性能分析：時間上，對于含n個字符的表達式，無論是對其進行合法性檢測還是對其進行入棧出棧操作n次，因此其時間復(fù)雜度為O(n)?？臻g上，由于是用數(shù)組來存儲輸入的表達式，用棧來存儲運算中的數(shù)據(jù)和運算符，而棧的本質(zhì)也用到的數(shù)組，數(shù)組在定義時必須確定其大小。在不知表達式長度的情況下確定數(shù)組的長度確非易事，此時極易造成空間的浪費，因此空間性能不是很好。四、 詳細設(shè)計源程序#include<iostream>using namespace std;#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct /運算符棧char *base;char *top;int stacksize;SqStack1;typedef struct /運算數(shù)棧float *base;float *top;int stacksize;SqStack2;void InitStack1(SqStack1 &S1);/聲明棧建立函數(shù)void InitStack2(SqStack2 &S2);/聲明棧建立函數(shù)void evaluate(SqStack1 &S1,SqStack2 &S2);/確定如何入棧函數(shù)void Push1(SqStack1 &S1,char e);/聲明入棧函數(shù)void Push2(SqStack2 &S2,float e);/聲明入壓棧函數(shù)char GetTop1(SqStack1 &S1);/聲明取棧頂元素函數(shù)float GetTop2(SqStack2 &S2);/聲明取棧頂元素函數(shù)char Pop1(SqStack1 &S1);/聲明出棧函數(shù)float Pop2(SqStack2 &S2);/聲明出棧函數(shù)char Compare(char m,char n);/聲明比較函數(shù)float Operate(float a,char rheta,float b);/聲明運算函數(shù)void DispStack1(SqStack1 &S1);/從棧底到棧頂依次輸出各元素void DispStack2(SqStack2 &S2);/從棧底到棧頂依次輸出各元素/*主函數(shù)*/void main()SqStack1 S1;/定義運算符棧SqStack2 S2;/定義運算數(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ù)*/void InitStack1(SqStack1 &S1)/構(gòu)造一個空棧S1S1.base=(char *)malloc(STACK_INIT_SIZE *sizeof(char);if(!S1.base)cout<<"存儲分配失??！"/存儲分配失敗S1.top=S1.base;S1.stacksize=STACK_INIT_SIZE;void Push1(SqStack1 &S1,char e)/入棧if(S1.top-S1.base>=S1.stacksize)/如果棧滿，追加存儲空間S1.base=(char *)realloc(S1.base,(S1.stacksize+STACKINCREMENT)*sizeof(char);if(!S1.base)cout<<"存儲分配失??！"elseS1.top=S1.base+S1.stacksize;S1.stacksize=S1.stacksize+STACKINCREMENT;*S1.top=e;S1.top=S1.top+1;/將元素壓入棧中，指針上移char GetTop1(SqStack1 &S1)/取棧頂元素char e;if(S1.top=S1.base)cout<<"nttt運算符棧已空!n"else e=*(S1.top-1);return e;void DispStack1(SqStack1 &S1)/從棧底到棧頂依次輸出各元素char e,*p;if(S1.top=S1.base)cout<<" "elsep=S1.base;while(p<S1.top)e=*p;p+;cout<<e;char Pop1(SqStack1 &S1)/出棧char e;if(S1.top=S1.base)cout<<"nttt運算符棧已空!n"e=*(-S1.top);return e;/*運算數(shù)棧函數(shù)*/void InitStack2(SqStack2 &S2)/構(gòu)造一個空棧S2S2.base=(float *)malloc(STACK_INIT_SIZE *sizeof(float);if(!S2.base)cout<<"存儲分配失?。?quot;/存儲分配失敗S2.top=S2.base;S2.stacksize=STACK_INIT_SIZE;void Push2(SqStack2 &S2,float e)/入棧if(S2.top-S2.base>=S2.stacksize)/棧滿，追加存儲空間S2.base=(float *)realloc(S2.base,(S2.stacksize+STACKINCREMENT)*sizeof(float);if(!S2.base)cout<<"存儲分配失??！"elseS2.top=S2.base+S2.stacksize;S2.stacksize=S2.stacksize+STACKINCREMENT;*S2.top=e;S2.top=S2.top+1;/將元素e入棧，指針上移void DispStack2(SqStack2 &S2)/從棧底到棧頂依次輸出各元素float e,*p;if(S2.top=S2.base)cout<<" "elsep=S2.base;while(p<S2.top)e=*p;p+;cout<<e;float GetTop2(SqStack2 &S2)/取棧頂元素float e;if(S2.top=S2.base) cout<<"ntt運算數(shù)棧已空!"else e=*(S2.top-1);return e;float Pop2(SqStack2 &S2)/出棧float e;if(S2.top=S2.base)cout<<"ntt運算數(shù)棧已空!"e=*(-S2.top);return e;/*確定如何入棧函數(shù)*/void evaluate(SqStack1 &S1,SqStack2 &S2)char c;float t,e;int n=0,i=1,j=0,k=0,l=0;char chSTACK_INIT_SIZE;int s=1;int flag=0,flag2=0;float p1,p2;char ch1;Push1(S1,#);/將#入棧，作為低級運算符cout<<"請輸入不含變量的表達式（以#結(jié)束!）：n "cin>>ch;c=ch0;cout<<"n對表達式求值的操作過程如下："<<"n_n"<<"步驟t運算符棧S1t運算數(shù)棧S2t輸入字符tt主要操作"while(c!=#|GetTop1(S1)!=#) cout<<"n_n" cout<<i+<<"t"DispStack1(S1);cout<<"tt"DispStack2(S2);cout<<"tt"if(flag=1)k-;flag=0;if(flag2)k+=flag2;flag2=0;for(l=0;l<k;l+)cout<< ;for(j=k;chj!=0;j+)cout<<chj;if(chk!=#&&flag!=1) k+;flag=0;as:if(!(c=+|c=-|c=*|c=/|c=(|c=)|c=#)/輸入的字符如果不是運算符號，則繼續(xù)輸入直到輸入的是運算符為止，將非運算符轉(zhuǎn)換成浮點數(shù)if(!(c=.)&&n>=0)e=float(c-48);n+;if(n=1)t=e;else if(n>1)t=t*10+e;c=chs+;if(n=-1)e=float(c-48);t=t+e/10;c=chs+;if(c=.)n=-1;c=chs+; if(c>=0&&c<=9)|c=.)flag2+;goto as;if(c<0|c>9)Push2(S2,t); cout<<"ttPush2(S2,"<<t<<")"else/輸入的是運算符n=0;/非運算型數(shù)據(jù)計數(shù)器清零switch(Compare(GetTop1(S1),c)/比較運算符的優(yōu)先級case <:/棧頂元素優(yōu)先級低，則入棧且繼續(xù)輸入Push1(S1,c);cout<<"ttPush1(S1,"<<c<<")"c=chs+;break;case =:/棧頂元素優(yōu)先級相等，脫括號并接收下一字符Pop1(S1);cout<<"ttPop1(S1)"c=chs+;break;case >:/棧頂元素優(yōu)先級高，則退棧并將運算結(jié)果入棧p1=Pop2(S2);p2=Pop2(S2);ch1=Pop1(S1);Push2(S2,Operate(p2,ch1,p1);cout<<"ttOperate("<<p2<<,<<ch1<<,<<p1<<);flag=1;break;cout<<"n_n"cout<<i<<t<<#<<"tt"<<GetTop2(S2)<<"tt"for(j=0;j<k;j+) cout<< ;cout<<"#"<<"tt"<<"RETURN(GETTOP(S2)"cout<<"n_n"if(S2.top-1=S2.base)/顯示表達式最終結(jié)果cout<<"n表達式的結(jié)果為："<<GetTop2(S2)<<endl;else cout<<"n表達式出錯!n"char Compare(char m,char n)/運算符的優(yōu)先級比較if(n=+|n=-)/輸入符號為"+"、"-" if(m=(|m=#)return </棧頂元素為"("、"#",此時棧頂符號優(yōu)先級低，返回"<"else return >/否則，棧頂符號優(yōu)先級高,返回">"else if(n=*|n=/)/輸入的符號為"*"、"/"if(m=)|m=*|m=/)return >/棧頂元素為")"、"*"、"/",此時棧頂符號優(yōu)先級高，返回">"else return </否則，棧頂符號優(yōu)先級低,返回"<"else if(n=()return</輸入的符號為"(",則直接返回"<"else if(n=)/輸入的符號為")"if(m=()return=;/棧頂元素為"(",此時優(yōu)先級同，返回"="else return >/否則，棧頂符號優(yōu)先級高,返回">"else /輸入符號為其他if(m=#)return=;/棧頂元素為"#",此時優(yōu)先級同，返回"="else return >/否則，棧頂符號優(yōu)先級高,返回">"float Operate(float a,char theta,float b)/運算函數(shù)float tmp=0;if (theta=+)tmp=a+b;/從運算符棧取出的符號為"+"，則運算數(shù)棧的兩元素相加，并返回else if(theta=-)tmp=a-b;/從運算符棧取出的符號為"-"，則運算數(shù)棧的兩元素相減，并返回else if(theta=*)tmp=a*b;/從運算符棧取出的符號為"*"，則運算數(shù)棧的兩元素相乘，并返回else if(theta=/) /從運算符棧取出的符號為"/"，則運算數(shù)棧的兩元素相除，并返回if(b=0) cout<<"n表達式出錯!除數(shù)不能為0!n"else tmp=a/b;return tmp;五、運行與測試第六章 總結(jié)與心得數(shù)據(jù)結(jié)構(gòu)的研究不僅涉及到計算機硬件的研究，而且和計算機軟件的研究有著更密切的關(guān)系，無論是編譯程序還是操作系統(tǒng)，都涉及到數(shù)據(jù)元素在存儲器中的分配問題。在研究信息檢索時也必須考慮如何組織數(shù)據(jù)，以便使查找和存取數(shù)據(jù)元素更為方便。在課程設(shè)計中，應(yīng)該力求算法簡明易懂，而易于轉(zhuǎn)換為上機程序；如果程序反復(fù)多次使用，則應(yīng)該盡可能選用快速的算法；如果待解決的問題數(shù)據(jù)量極大，機器的存儲空間較小，則在編寫算法時應(yīng)該考慮如何節(jié)省空間。以后在編寫程序時就應(yīng)該注意到所編寫程序的時間復(fù)雜度，以及是否運用了良好的算法，而不能只是像以前編寫程序時單純使用C語言的知識，要充分考慮程序的性能，爭取編寫出更優(yōu)良的程序來。讓我對數(shù)據(jù)結(jié)構(gòu)有了更進一步的認識和了解，也讓我知道，要想學(xué)好它要重在實踐，理論與實際應(yīng)用相結(jié)合，提高了自己組織數(shù)據(jù)及編寫大型程序的能力，培養(yǎng)了基本的、良好的程序設(shè)計技能力。通過實際操作，我也發(fā)現(xiàn)我的好多不足之處：(1)用棧的結(jié)構(gòu)來解決表達式的求值，首先要解決的問題是如何將人們習(xí)慣書寫的表達式轉(zhuǎn)換成計算機容易處理的表達式。開始有些茫然，后來通過結(jié)合課本和同學(xué)的幫助完成了該課題。(2)對一些看似簡單的東西掌握不夠熟練，比如由于函數(shù)的調(diào)用參數(shù)問題不熟而造成了調(diào)試的困難。對于語法的掌握也欠缺成熟，需要進一步掌握。(3)棧的結(jié)構(gòu)理解不夠清晰，造成了設(shè)計程序時理不清頭緒，需要對數(shù)據(jù)結(jié)構(gòu)有更深層次的理解。13