《數(shù)據(jù)結(jié)構(gòu)與算法》課程設(shè)計-表達式的相關(guān)函數(shù)庫實現(xiàn)

數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計成果報告表達式的相關(guān)函數(shù)庫實現(xiàn)學(xué)生學(xué)號： 學(xué)生姓名： 學(xué) 院： 計算機學(xué)院 專業(yè)班級： 1341 專業(yè)課程： 數(shù)據(jù)結(jié)構(gòu)與算法 指導(dǎo)教師： 2014 年 12 月 29 日題 目表達式的相關(guān)函數(shù)庫實現(xiàn)考核項目考核內(nèi)容得分平時考核（30分）出勤情況、態(tài)度、效率；知識掌握情況、基本操作技能、知識應(yīng)用能力、獲取知識能力系統(tǒng)設(shè)計（20分）分析系統(tǒng)的功能模塊編程調(diào)試（20分）實現(xiàn)系統(tǒng)的各個功能模塊，并完成調(diào)試回答問題（15分）回答老師針對課程設(shè)計提出的問題課程設(shè)計報告撰寫（10分）嚴(yán)格按照規(guī)范要求完成課程設(shè)計報告源代碼（5分）按照規(guī)范要求完成課程設(shè)計源代碼的排版總 評 成 績指導(dǎo)教師評語： 日期： 年 月 日目 錄1 課程設(shè)計目標(biāo)與任務(wù)11.1課程設(shè)計目標(biāo)11.2課程設(shè)計任務(wù)12 分析與設(shè)計22.1 題目需求分析22.2 存儲結(jié)構(gòu)設(shè)計22.3 算法描述22.4 程序流程圖22.5 測試程序說明23 程序清單34 測試44.1 測試數(shù)據(jù)44.2 測試結(jié)果分析45 總結(jié)5參考文獻7附 錄81 課程設(shè)計目標(biāo)與任務(wù)1.1 課程設(shè)計目標(biāo)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計是在學(xué)完數(shù)據(jù)結(jié)構(gòu)課程之后的實踐教學(xué)環(huán)節(jié)。該實踐教學(xué)是軟件設(shè)計的綜合訓(xùn)練,包括問題分析，總體結(jié)構(gòu)設(shè)計用戶界面設(shè)計，程序設(shè)計基本技能和技巧。要求學(xué)生在設(shè)計中逐步提高程序設(shè)計能力培養(yǎng)科學(xué)的軟件工作方法學(xué)生通過數(shù)據(jù)結(jié)構(gòu)課程設(shè)計各方面得到鍛煉：（1）能根據(jù)實際問題的具體情況結(jié)合數(shù)據(jù)結(jié)構(gòu)課程中的基本理論和基本算法，正確分析出數(shù)據(jù)的邏輯結(jié)構(gòu)，合理地選擇相應(yīng)的存儲結(jié)構(gòu)，并能設(shè)計出解決問題的有效算法；（2）通過上機實習(xí),驗證自己設(shè)計的算法的正確性，學(xué)會有效利用基本調(diào)試方法，迅速找出程序代碼中的錯誤并且修改；（3）培養(yǎng)算法分析能力，分析所設(shè)計算法的時間復(fù)雜度和空間復(fù)雜度，進一步提高程序設(shè)計水平；（4）盡可能借助語言環(huán)境實現(xiàn)圖形顯示功能，以便將抽象的數(shù)據(jù)結(jié)構(gòu)以圖形方式顯示出來，將復(fù)雜的運行過程以動態(tài)方式顯示出來，獲得算法的直觀感受。1.2 課程設(shè)計任務(wù)設(shè)計一個表達式求值的程序。該程序必須可以接受包含（，），+， -，*，/，%，和（求冪運算符ab=a）的中綴表達式并求出結(jié)果。如果表達式正確則輸出表達式的結(jié)果如果表達式非法則輸出錯誤信息。2 分析與設(shè)計2.1 題目需求分析利用棧設(shè)計一個程序，該程序能夠用于表達式求值，程序能夠處理以字符序列的形式輸入的不含變量的實數(shù)表達式，能正確處理負(fù)數(shù)與小數(shù)，判斷表達式是否語法正確，包含分母不能為零的情況。正確實現(xiàn)對算術(shù)四則混合運算表達式的求值，將計算中遇到的問題和結(jié)果予以輸出。2.2 存儲結(jié)構(gòu)設(shè)計在計算機中，算術(shù)表達式的計算往往是通過使用棧來實現(xiàn)的。所以，求值程序的最主要的數(shù)據(jù)結(jié)構(gòu)就是棧。本程序就是使用棧來存儲輸入表達式的操作符和操作數(shù)。輸入的表達式是由操作數(shù)和運算符以及改變運算次序的圓括號連接而成的式子。任何一個表達式都是由操作數(shù)(OPTR)、運算符(OPND)和界限(delimiter)組成的。實現(xiàn)運算符優(yōu)先算法時需要使用兩個工作棧，一個為OPTR，用以存放運算符，另一個為OPND，用以存放操作數(shù)或運算的中間結(jié)果。首先初始化操作數(shù)棧OPTR和運算符棧OPND，并將表達式起始符“”壓入運算符棧，依次讀入表達式中的每個字符,若是操作數(shù)則直接進入操作數(shù)棧OPTR，若是運算符，則與運算符棧OPND的棧頂運算符進行優(yōu)先權(quán)比較，并做如下處理： (1) 若棧頂運算符的優(yōu)先級低于剛讀入的運算符，則讓剛讀入的運算符進OPTR棧。 (2) 若棧頂運算符的優(yōu)先級高于剛讀入的運算符，則將棧頂運算符退棧,同時接收下一個運算符，最后將運算結(jié)果推入OPND棧。 (3) 若棧頂運算符的優(yōu)先級與剛讀入的運算符的優(yōu)先級相同，說明左右括號相遇，只需將棧頂運算符“左括號”退棧即可。當(dāng)輸入完一個完整的表達式之后（沒有遇到最后一個是運算符輸入時）程序結(jié)束。2.3 算法描述 （1）首先是創(chuàng)建了一個運算符優(yōu)先級表，用于比較運算符，然后創(chuàng)建兩個棧，再設(shè)計3個指針，用于指向結(jié)點。然后是計算函數(shù)Operate的設(shè)計，它也是利用棧來實現(xiàn)運算。利用創(chuàng)建的兩個棧直接對表達式進行計算。分別構(gòu)建一個char類型和一個double類型的棧函數(shù)。（2）在main函數(shù)中讓用戶進行輸入，將用戶輸入的字符串進行循環(huán)、判斷，并將判斷后的字符串傳遞到新的數(shù)組中，循環(huán)結(jié)束后，再將數(shù)組傳遞給中綴表達式轉(zhuǎn)后綴表達式函數(shù)。（3）在Operate()函數(shù)中先創(chuàng)建一個數(shù)字棧和一個符號棧，對表達式進行循環(huán)，直到元素為0。在循環(huán)中如果元素為數(shù)字，將元素賦給新的數(shù)組s，再判斷下一個元素，若是則利用函數(shù)將數(shù)組中的字符串轉(zhuǎn)換成double類型的數(shù)字，然后數(shù)字進棧，清空數(shù)組s；否則，繼續(xù)判斷。若元素不為數(shù)字，則先看棧頂，如果棧為空或棧頂元素為（或者棧頂元素為+或并且現(xiàn)有元素為*、/或%又或是現(xiàn)有元素為，則現(xiàn)有元素進棧；否則，再對現(xiàn)有元素進行判斷：如果現(xiàn)有元素為），運算符出棧直到（出棧；否則，運算符出棧直到?？栈蛘邨ｍ斣氐膬?yōu)先級低于現(xiàn)有運算符，現(xiàn)有運算符才進棧。每當(dāng)有一個運算符出棧，就從數(shù)棧中取兩個數(shù)與運算符一起傳遞給Operate()函數(shù),并將函數(shù)的返回值壓入棧中。循環(huán)結(jié)束后，將棧中的運算符全部依次輸出，每當(dāng)有一個運算符出棧，就從數(shù)棧中取兩個數(shù)與運算符一起傳遞給Operate()函數(shù),并將函數(shù)的返回值壓入棧中，最后輸出數(shù)字棧中的數(shù)字成為表達式的最終結(jié)果，再銷毀棧。（4）Operate()函數(shù)是利用switch語句對傳入進來的運算符進行判斷，并將傳入的兩個數(shù)進行相應(yīng)的運算，并返回運算結(jié)果。（5）各模塊的主要功能*Push(SC *s,char c)：把字符壓棧*Push(SF *s,float f)：把數(shù)值壓棧*Pop(SC *s)：把字符退棧*Pop(SF *s)：把數(shù)值退棧Operate(a,theta,b)：根據(jù)theta對a和b進行+ 、- 、* 、/ 、操作In(Test,*TestOp)：若Test為運算符則返回true，否則返回falseReturnOpOrd(op,*TestOp)：若Test為運算符，則返回此運算符在數(shù)組中的下標(biāo)precede(Aop,Bop)：根據(jù)運算符優(yōu)先級表返回Aop與Bop之間的優(yōu)先級EvaluateExpression(*MyExpression)：用算符優(yōu)先法對算術(shù)表達式求值2.4 程序流程圖程序流程圖1-12.5 測試程序說明1.一般來說，計算機解決一個具體問題時，需要經(jīng)過幾個步驟：首先要從具體問題抽象出一個適當(dāng)?shù)臄?shù)學(xué)模型，然后設(shè)計一個解決此數(shù)學(xué)模型的算法，最后編出程序，進行測試，調(diào)試直至得到想要的答案。對于算術(shù)表達式這個程序，主要利用棧，把運算的先后步驟進行分析并實現(xiàn)簡單的運算！為實現(xiàn)算符優(yōu)先算法，可以使用兩個棧，一個用以寄存運算符，另一個用以寄存操作數(shù)和運算結(jié)果。2.演示程序是以用戶于計算機的對話方式執(zhí)行，這需要一個模塊來完成使用者與計算機語言的轉(zhuǎn)化。 3.程序塊的功能介紹：（1）棧的抽象數(shù)據(jù)類型定義：ADT Stack數(shù)據(jù)對象：D=ai|aiElemSet,i=1,2,n,n0數(shù)據(jù)關(guān)系：R1=|ai-1,aiD,i=2,n約定an端為棧頂，ai端為棧底（）基本操作：Push(&S,e)初始條件：棧S已存在操作結(jié)果：插入元素e為新的棧頂元素Pop(&S,&e)初始條件：棧S已存在且非空操作結(jié)果：刪除S的棧頂元素，并用e返回其值A(chǔ)DT Stack3 程序清單#includestdio.h#includestdlib.h #includestring.h #includemath.h#define true 1 #define false 0 #define OPSETSIZE 8 typedef int Status; unsigned char Prior88 = / 運算符優(yōu)先級表 / + - * / ( ) # /*+*/, /*(*/,=, , , /*#*/, ,=, ; typedef struct StackChar char c; struct StackChar *next; SC; /StackChar類型的結(jié)點SCtypedef struct StackFloat float f; struct StackFloat *next; SF; /StackFloat類型的結(jié)點SFSC *Push(SC *s,char c) /SC類型的指針Push，返回p SC *p=(SC*)malloc(sizeof(SC); p-c=c; p-next=s; return p; SF *Push(SF *s,float f) /SF類型的指針Push，返回p SF *p=(SF*)malloc(sizeof(SF); p-f=f; p-next=s; return p; SC *Pop(SC *s) /SC類型的指針Pop SC *q=s; s=s-next; free(q); return s; SF *Pop(SF *s) /SF類型的指針Pop SF *q=s; s=s-next; free(q); return s; float Operate(float a,unsigned char theta, float b) /計算函數(shù)Operate switch(theta) case +: return a+b; case -: return a-b; case *: return a*b; case /: return a/b; case : return pow(a,b); default : return 0; char OPSETOPSETSIZE=+,-,*,/,(,),#,; Status In(char Test,char *TestOp) int Find=false; for (int i=0; i OPSETSIZE; i+) if(Test = TestOpi) Find= true; return Find; Status ReturnOpOrd(char op,char *TestOp) for(int i=0; ic!=#) if (!In(*c, OPSET) Dr0=*c; strcat(TempData,Dr); /字符串連接函數(shù) c+; if (In(*c, OPSET) Data=atof(TempData); /字符串轉(zhuǎn)換函數(shù)(double) OPND=Push(OPND, Data); strcpy(TempData,0); else / 不是運算符則進棧 switch (precede(OPTR-c, *c) case : / 退棧并將運算結(jié)果入棧 theta=OPTR-c;OPTR=Pop(OPTR); b=OPND-f;OPND=Pop(OPND); a=OPND-f;OPND=Pop(OPND); OPND=Push(OPND, Operate(a, theta, b); break; /switch /while return OPND-f; /EvaluateExpression int main(void) char s128; puts(請輸入表達式:); gets(s); puts(該表達式的值為:); printf(%sb=%gn,s,EvaluateExpression(s); system(pause); return 0;4 測試4.1 測試數(shù)據(jù)下面執(zhí)行加法運算：1+1測試結(jié)果圖-1下面執(zhí)行減法運算：10-9測試結(jié)果圖1-2下面執(zhí)行乘法運算：5*2測試結(jié)果圖1-3下面執(zhí)行除法運算：8/4測試結(jié)果圖1-4下面執(zhí)行混合運算：(2+2)*3_2)/5測試結(jié)果圖1-54.2 測試結(jié)果分析程序經(jīng)過測試之后，主要的功能可以實現(xiàn)，可以完成實驗的要求，并仿照教科書的例子在求值中運算符棧、運算數(shù)棧、輸入字符和主要操作的變化過程進行四則混合運算。但是也存在一些小問題，就是在計算完一個表達式之后，不可以直接進行下一運算，必須再一次啟動程序進行計算。但它的優(yōu)點是，用戶輸入方便，沒有過多的輸入要求，直接輸入想計算的表達式即可，沒有過多的格式要求。以字符列的形式從終端輸入語法正確的、不含變量的整數(shù)表達式。利用已知的運算符優(yōu)先關(guān)系，實現(xiàn)對算術(shù)四則混合運算表達式的求值。5 總結(jié) 一周的課程設(shè)計即將結(jié)束了，在這次的課程設(shè)計中不僅檢驗了我所學(xué)習(xí)的知識，也培養(yǎng)了我如何去把握一件事情，如何去做一件事情，又如何完成一件事情。在設(shè)計過程中，與同學(xué)分工設(shè)計，和同學(xué)們相互探討，相互學(xué)習(xí)，相互監(jiān)督。學(xué)會了合作，學(xué)會了運籌帷幄，學(xué)會了寬容，學(xué)會了理解，也學(xué)會了做人與處世。由于本人的設(shè)計能力有限，在設(shè)計過程中難免出現(xiàn)錯誤，懇請老師多多指教,我十分樂意接受您的批評與指正，我將十分感謝。參考文獻1朱福喜.Java語言程序設(shè)計（第二版）.科學(xué)出版社2陳國君等.Java程序設(shè)計基礎(chǔ)（第二版）.清華大學(xué)出版社3Deitel.Java大學(xué)基礎(chǔ)教程（第六版）.電子工業(yè)出版社4MaryCampione.Java語言導(dǎo)學(xué)（第四版）.機械工業(yè)出版社5Y.DanielLiang.Java語言程序設(shè)計基礎(chǔ)篇（第六版）.機械工業(yè)出版社6KathySierra.HeadFirstJava（第二版）.東南大學(xué)出版社#includestdio.h #includestdlib.h #includestring.h #includemath.h #define true 1 #define false 0 #define OPSETSIZE 8 typedef int Status; unsigned char Prior88 = / 運算符優(yōu)先級表 / + - * / ( ) # /*+*/, /*(*/,=, , , /*#*/, ,=, ; typedef struct StackChar char c; struct StackChar *next; SC; /StackChar類型的結(jié)點SC typedef struct StackFloat float f; struct StackFloat *next; SF; /StackFloat類型的結(jié)點SF SC *Push(SC *s,char c) /SC類型的指針Push，返回p SC *p=(SC*)malloc(sizeof(SC); p-c=c; p-next=s; return p; SF *Push(SF *s,float f) /SF類型的指針Push，返回p SF *p=(SF*)malloc(sizeof(SF); p-f=f; p-next=s; return p; SC *Pop(SC *s) /SC類型的指針Pop SC *q=s; s=s-next; free(q); return s; SF *Pop(SF *s) /SF類型的指針Pop SF *q=s; s=s-next; free(q); return s; float Operate(float a,unsigned char theta, float b) /計算函數(shù)Operate switch(theta) case +: return a+b; case -: return a-b; case *: return a*b; case /: return a/b; case : return pow(a,b); default : return 0; char OPSETOPSETSIZE=+,-,*,/,(,),#,;