數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--表達式求值問題

1、<p><b>　　課程設(shè)計(論文)</b></p><p>　　題 目 名 稱 表達式求值問題 </p><p>　　課 程 名 稱 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 </p><p>　　學(xué) 生 姓 名 XXX <

2、/p><p>　　學(xué) 號 xxxxxxxxx </p><p>　　系 、專 業(yè) 信息工程系、信息工程類 </p><p>　　指 導(dǎo) 教 師 xxxxxx </p><p>　　2010年 1 月 3 日<

3、;/p><p><b>　　目 錄</b></p><p><b>　　1 問題描述2</b></p><p><b>　　2 需求分析2</b></p><p><b>　　3 概要設(shè)計2</b></p><p>　　3．1抽

4、象數(shù)據(jù)類型定義2</p><p><b>　　3．2模塊劃分3</b></p><p><b>　　4 詳細設(shè)計4</b></p><p>　　4．1數(shù)據(jù)類型的定義4</p><p>　　4．2主要模塊的算法描述4</p><p><b>　　5 測試分析

5、7</b></p><p>　　5．1程序運行結(jié)果7</p><p>　　5．2程序調(diào)試與體會.........................................................................8</p><p>　　6 課程設(shè)計總結(jié)8</p><p><b>　　參考

6、文獻8</b></p><p>　　附錄（源程序清單）9</p><p><b>　　1 問題描述</b></p><p>　　編寫一個表達式求值程序，使輸入一個四則運算表達式后，能夠返回正確的結(jié)果。該表達式由數(shù)字0～9、+、-、*、/、括號組成，且表達式必須正確無誤。程序的編寫可用到棧或隊列的基本算法，求出該表達式的值，并分析

7、算法的時間復(fù)雜度和運算的結(jié)果。</p><p><b>　　2 需求分析</b></p><p>　?。?）為實現(xiàn)算符優(yōu)先算法,可以使用兩個工作棧。一個稱做OPTR，用以寄存運算符;另一個稱做OPND;用以寄存操作數(shù)或運算結(jié)果。算法的基本思想是：</p><p>　?、偈紫戎貌僮鲾?shù)棧為空棧，表達式起始符“#”為運算符棧的棧底元素; </p

8、><p>　　②依次讀入表達式中每個字符,若是操作數(shù)則OPND棧,若是運算符,則和OPTR棧的棧頂運算符比較優(yōu)先權(quán)后做相應(yīng)操作,直至整個表達式求值完畢(即OPTR棧的棧頂元素和當(dāng)前讀入的字符均為"#")。</p><p>　　（2）該程序?qū)崿F(xiàn)表達式的求值問題：</p><p>　　從鍵盤讀入一個合法的算術(shù)表達式，利用算符優(yōu)先關(guān)系，實現(xiàn)對算術(shù)四則混合運

9、算的求值，輸出正確的結(jié)果。</p><p><b>　　3 概要設(shè)計</b></p><p>　　3．1抽象數(shù)據(jù)類型定義</p><p>　　設(shè)定棧抽象數(shù)據(jù)類型的定義采用兩個棧的入棧與出棧的操作來進行“運算符和操作數(shù)的配對”。程序中主要用到以下抽象數(shù)據(jù)類型：</p><p>　　1）ADT Stack {</p&g

10、t;<p>　　數(shù)據(jù)對象：D＝{ ai | ai ∈ElemSet, i=2,...,n, </p><p><b>　　n≥0 }</b></p><p>　　數(shù)據(jù)關(guān)系：R1＝{ <ai-1, ai >| ai-1, ai∈D, i=2,...,n }</p><p>　　約定an 端為棧頂，a1 端為棧底。<

11、;/p><p><b>　　基本操作：</b></p><p>　?。?）InitStack(&S) </p><p>　　操作結(jié)果：構(gòu)造一個空棧S。</p><p>　?。?）GetTop(S, &e) </p><p>　　初始條件：棧S已存在且非空。<

12、/p><p>　　操作結(jié)果：用e返回S的棧頂元素。</p><p>　?。?）Push(&S, e) </p><p>　　初始條件：棧S已存在。</p><p>　　操作結(jié)果：插入元素e為新的棧頂元素。</p><p>　?。?）StackEmpty(&s) </p>&

13、lt;p>　　初始條件: 棧S已存在。</p><p>　　操作結(jié)果:若S為空棧，則返回TRUE, 否則返回FALSE</p><p>　?。?）Pop(&S, &e) </p><p>　　初始條件：棧S已存在且非空。</p><p>　　操作結(jié)果：刪除S的棧頂元素，并用e返回其值。</p>

14、<p>　　} ADT Stack</p><p><b>　　3．2模塊劃分</b></p><p>　　本程序包括三個模塊：</p><p><b>　?。?）主函數(shù)模塊</b></p><p>　　void main()</p><p><b>　

15、　{ 輸入表達式；</b></p><p>　　根據(jù)要求進行轉(zhuǎn)換并求值；</p><p><b>　　輸出結(jié)果；}</b></p><p>　?。?）表達式求值模塊-----實現(xiàn)具體求值</p><p>　　（3）表達式轉(zhuǎn)換模塊-----實現(xiàn)轉(zhuǎn)換。</p><p>　　三模塊之間簡單

16、調(diào)用關(guān)系：</p><p>　　圖3.2 模塊調(diào)用圖</p><p><b>　　4 詳細設(shè)計</b></p><p>　　4．1數(shù)據(jù)類型的定義</p><p><b>　?。?）棧類型</b></p><p>　　#define MAXSIZE 100</p>

17、<p>　　typedef int elmtype;</p><p>　　struct sqstack</p><p><b>　　{</b></p><p>　　elmtype stack[MAXSIZE];</p><p><b>　　int top;</b></p>

18、<p><b>　　};</b></p><p><b>　?。?）運算符號類型</b></p><p>　　char ch[7]={'+','-','*','/','(',')','#'};</p><

19、p>　?。?）運算符號優(yōu)先級類型</p><p>　　int f1[7]={3,3,5,5,1,6,0};/*棧內(nèi)元素優(yōu)先級*/</p><p>　　int f2[7]={2,2,4,4,6,1,0};/*棧外元素優(yōu)先級*/</p><p>　　4．2主要模塊的算法描述</p><p>　　該程序主要由主函數(shù)模塊、表達式求值模塊、表達式

20、轉(zhuǎn)換模塊三個個部分組成。</p><p>　?。?）主函數(shù)及表達式求值模塊</p><p>　　void main()</p><p><b>　　{</b></p><p>　　int result;</p><p>　　result=EvaluateExpression(); /*對Eva

21、luateExpression()進行調(diào)用*/ }</p><p>　?。?）表達式求值模塊</p><p>　　主函數(shù)只調(diào)用了EvaluateExpression()函數(shù);而其他的函數(shù)則由EvaluateExpression()調(diào)用了，因此使得主函數(shù)十分簡潔明了。其中求值函數(shù)流程圖如下：</p><p>　　圖4.2 表達式求值模塊流程圖</p>

22、<p>　?。?）表達式轉(zhuǎn)換模塊</p><p>　　void trans(char *exp,char *postexp)</p><p><b>　　{</b></p><p>　　在本函數(shù)中先初始化一個OP棧，依次讀入表達式中的每個字符，若是運算符就進OP棧，若運算符則與OP棧進行比較，直至整個表達式轉(zhuǎn)換完畢。</p&g

23、t;<p><b>　　}</b></p><p>　　float compvalue(char *postexp){ </p><p><b>　　struct </b></p><p><b>　　{ </b></p><p>　　float data[Max

24、Size]; </p><p><b>　　int top; </b></p><p><b>　　} st;</b></p><p><b>　　5 測試分析</b></p><p>　　5．1程序運行結(jié)果： </p><p>　　5．2程序調(diào)試與體會

25、</p><p>　　運用棧的基本操作順利的解決表達式求值及轉(zhuǎn)換問題，主要利用棧的先進后出結(jié)構(gòu)，執(zhí)行出棧進棧操作并在出棧時進行配對并輸出配對情況，而整個過程不需要不需要移動元素使程序在空間復(fù)雜度上降到最小，采用指針的移動大大加快了程序的執(zhí)行效率。并且對輸入進行了改進，以防止用戶隨意輸入時出現(xiàn)的各種意想不到的錯誤。系統(tǒng)整體上比較完美，無論是輸入、輸出，還是整個系統(tǒng)的界面，都非常美觀、簡潔、大方</p>

26、<p><b>　　6 課程設(shè)計總結(jié)</b></p><p>　　通過這段時間的課程設(shè)計，本人對計算機的應(yīng)用、數(shù)據(jù)結(jié)構(gòu)的作用以及C語言的使用都有了更深的了解。在理論學(xué)習(xí)和上機實踐的各個環(huán)節(jié)中，通過自主學(xué)習(xí)和請教陳智、成婭輝老師，我收獲了不少。當(dāng)然也遇到不少問題，也正是因為這些問題引發(fā)的思考給我?guī)砹耸斋@。從當(dāng)初不喜歡上機寫程序到現(xiàn)在能主動寫程序，從當(dāng)初拿著程序不知從何下手道現(xiàn)在知

27、道如何分析問題，如何用專業(yè)知識解決實際問題的轉(zhuǎn)變。我發(fā)現(xiàn)無論是專業(yè)知識還是動手能力，自己都有很大程度的提高。</p><p>　　在實際上機操作過程中，不僅是讓我們了解數(shù)據(jù)結(jié)構(gòu)的理論知識，更重要的是培養(yǎng)解決實際問題的能力。所以相信通過此次課程設(shè)計實習(xí)可以提高我們分析設(shè)計能力和編程能力，為后續(xù)課程的學(xué)習(xí)及實踐打下良好的基礎(chǔ)。</p><p>　　在這次短短的課程實踐里，我得到了陳智老師的關(guān)心

28、和幫助。他給了我們很多的信息，與我們一起探討問題，詢問我們遇到了哪些問題并耐心給予指導(dǎo)。當(dāng)我們遇到技術(shù)上難以解決的問題時，他就會指導(dǎo)我們解決問題，他把自己多年來積累的經(jīng)驗傳授給我們，是我們順利的完成了課程設(shè)計的任務(wù)。再一次感謝給予我指導(dǎo)及幫助的老師和同學(xué)們！ </p><p><b>　　參考文獻</b></p><p>　　[1] 黃同成，黃俊民，董建寅．?dāng)?shù)據(jù)結(jié)構(gòu)[

29、M]．北京：中國電力出版社，2008</p><p>　　[2] 董建寅，黃俊民，黃同成．?dāng)?shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)與題解[M]．北京：中國電力出版社，2008</p><p>　　[3] 嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)（C語言版）[M]. 北京：清華大學(xué)出版社，2002</p><p>　　[4] 劉振鵬，張曉莉，郝杰．?dāng)?shù)據(jù)結(jié)構(gòu)[M]．北京：中國鐵道出版社，2003</p

30、><p><b>　　附錄（源程序清單）</b></p><p>　　#include <conio.h></p><p>　　#include <stdio.h></p><p>　　#include <ctype.h></p><p>　　#define MAX

31、SIZE 100</p><p>　　typedef int elmtype;</p><p>　　typedef struct sqstack sqstack;</p><p>　　char ch[7]={'+','-','*','/','(',')','#&#

32、39;};</p><p>　　int f1[7]={3,3,5,5,1,6,0};/*棧內(nèi)元素優(yōu)先級*/</p><p>　　int f2[7]={2,2,4,4,6,1,0};/*棧外元素優(yōu)先級*/</p><p><b>　　int n=0;</b></p><p>　　struct sqstack</p&g

33、t;<p>　　{elmtype stack[MAXSIZE];</p><p><b>　　int top;</b></p><p><b>　　};</b></p><p>　　void Initstack(sqstack *s)</p><p>　　{ s->top=0;&

34、lt;/p><p><b>　　}</b></p><p>　　int StackEmpty(sqstack S )</p><p>　　{ if( S.top==0 ) return 1;</p><p>　　else return 0;}</p><p>　　void Push(sqstac

35、k *s,elmtype x)</p><p>　　{if(s->top==MAXSIZE-1)</p><p>　　printf("ERROR,Overflow!\n");</p><p><b>　　else</b></p><p>　　{ s->top++;</p>&

36、lt;p>　　s->stack[s->top]=x;}</p><p><b>　　}</b></p><p>　　void Pop(sqstack *s,elmtype *x)</p><p>　　{if(s->top==0)</p><p>　　printf("ERROR,Under

37、flow!\n");</p><p><b>　　else</b></p><p>　　{*x=s->stack[s->top];</p><p>　　s->top--;}</p><p><b>　　}</b></p><p>　　elmtype

38、 Gettop(sqstack s)</p><p><b>　　{</b></p><p>　　if(s.top==0)</p><p>　　{ printf("ERROR,underflow\n");</p><p>　　return 0; }</p><p><b&

39、gt;　　else</b></p><p>　　return s.stack[s.top];</p><p><b>　　}</b></p><p>　　elmtype f(char c)</p><p>　　{ switch(c)</p><p>　　{case '+'

40、;: return 0;</p><p>　　case '-': return 1;</p><p>　　case '*': return 2;</p><p>　　case '/': return 3;</p><p>　　case '(':

41、return 4;</p><p>　　case ')': return 5;</p><p>　　default: return 6; } </p><p><b>　　}</b></p><p>　　char Compare(char c1,char c2)</p>

42、<p>　　{int i1=f(c1);</p><p>　　int i2=f(c2);</p><p>　　if(f1[i1]>f2[i2])</p><p>　　return '>';</p><p>　　else if(f1[i1]<f2[i2])</p><p>　

43、　return '<';</p><p><b>　　else</b></p><p>　　return '=';</p><p><b>　　}</b></p><p>　　int Operate(elmtype a,elmtype t,elmtype b)&

44、lt;/p><p><b>　　{int sum;</b></p><p><b>　　switch(t)</b></p><p>　　{case 0: sum=a+b; break;</p><p>　　case 1: sum=a-b; break;</p><p>　

45、　case 2: sum=a*b; break;</p><p>　　default: sum=a/b;}</p><p>　　return sum;</p><p><b>　　}</b></p><p>　　float compvalue(char *postexp) </p><p>

46、<b>　　{ </b></p><p><b>　　struct </b></p><p><b>　　{ </b></p><p>　　float data[MaxSize]; </p><p><b>　　int top; </b></p>

47、;<p><b>　　} st; </b></p><p>　　EvaluateExpression()</p><p><b>　　{</b></p><p><b>　　char c;</b></p><p>　　int i=0,sum=0;</p>

48、;<p>　　int k=1,j=1;</p><p>　　elmtype x,t,a,b;</p><p>　　sqstack OPTR,OPND;</p><p>　　Initstack(&OPTR);</p><p>　　Push(&OPTR,f('#'));</p><

49、p>　　Initstack(&OPND);</p><p>　　c=getchar();</p><p>　　while(c!='#'||ch[Gettop(OPTR)]!='#')</p><p><b>　　{</b></p><p>　　if(isdigit(c))&l

50、t;/p><p><b>　　{</b></p><p><b>　　sum=0;</b></p><p>　　while(isdigit(c))</p><p><b>　　{</b></p><p><b>　　if(!j)</b>

51、</p><p>　　{ sum=sum*10-(c-'0'); }</p><p><b>　　else</b></p><p>　　sum=sum*10+(c-'0');</p><p>　　c=getchar();}</p><p>　　Push(&O

52、PND,sum);</p><p><b>　　j=1;}</b></p><p><b>　　else</b></p><p><b>　　if(k)</b></p><p><b>　　{</b></p><p>　　switc

53、h(Compare(ch[Gettop(OPTR)],c))</p><p>　　{ case'<': Push(&OPTR,f(c));</p><p>　　c=getchar()；break;</p><p>　　case'=': Pop(&OPTR,&x);</p><p>

54、;　　c=getchar(); break;</p><p>　　case'>': Pop(&OPTR,&t);</p><p>　　Pop(&OPND,&b);</p><p>　　Pop(&OPND,&a);</p><p>　　Push(&OPND,Opera

55、te(a,t,b));</p><p>　　printf("\n");</p><p><b>　　break;} </b></p><p>　　return(Gettop(OPND));</p><p><b>　　}</b></p><p><b

56、>　　main()</b></p><p>　　{ int result;</p><p>　　textcolor(GREEN);</p><p>　　cprintf("***************WELCOME **************n\r");</p><p>　　cprintf(&quo

57、t;*Input arithmetic expression (end with '#')*\n\r");</p><p>　　cprintf("*****************************************\n\r");</p><p>　　cprintf("*

58、 *\n\r");</p><p>　　result=EvaluateExpression();</p><p>　　textcolor(RED);</p><p>　　cprintf("*THE RESULT IS: %d \n\r",result);</p><

59、;p>　　textcolor(GREEN);</p><p>　　cprintf("* *\n\r");</p><p>　　cprintf("*************Thanks for using************* \n\r");</p>&l

60、t;p>　　cprintf("* *\n\r");</p><p>　　cprintf("* Instructor : Chen Zhi *\n\r");</p><p>　　cprintf("* Designers :

61、Chen Chunlin *\n\r");</p><p>　　cprintf("* Number : 0841330197 *\n\r");</p><p>　　cprintf("* School : ShaoYang University *\n\r")