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

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

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

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

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

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

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

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

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

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

10、t;<p>　　數(shù)據(jù)對(duì)象：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>　　（1）InitStack(&S) </p><p>　　操作結(jié)果：構(gòu)造一個(gè)空棧S。</p><p>　?。?）GetTop(S, &e) </p><p>　　初始條件：棧S已存在且非空。<

12、/p><p>　　操作結(jié)果：用e返回S的棧頂元素。</p><p>　　（3）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>　　本程序包括三個(gè)模塊：</p><p><b>　　（1）主函數(shù)模塊</b></p><p>　　void main()</p><p><b>　

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

16、調(diào)用關(guān)系：</p><p>　　圖3.2 模塊調(diào)用圖</p><p><b>　　4 詳細(xì)設(shè)計(jì)</b></p><p>　　4．1數(shù)據(jù)類(lèi)型的定義</p><p><b>　?。?）棧類(lèi)型</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>　?。?）運(yùn)算符號(hào)類(lèi)型</b></p><p>　　char ch[7]={'+','-','*','/','(',')','#'};</p><

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

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

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

22、<p>　　（3）表達(dá)式轉(zhuǎn)換模塊</p><p>　　void trans(char *exp,char *postexp)</p><p><b>　　{</b></p><p>　　在本函數(shù)中先初始化一個(gè)OP棧，依次讀入表達(dá)式中的每個(gè)字符，若是運(yùn)算符就進(jìn)OP棧，若運(yùn)算符則與OP棧進(jìn)行比較，直至整個(gè)表達(dá)式轉(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 測(cè)試分析</b></p><p>　　5．1程序運(yùn)行結(jié)果： </p><p>　　5．2程序調(diào)試與體會(huì)

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

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

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

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

29、M]．北京：中國(guó)電力出版社，2008</p><p>　　[2] 董建寅，黃俊民，黃同成．?dāng)?shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)與題解[M]．北京：中國(guó)電力出版社，2008</p><p>　　[3] 嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）[M]. 北京：清華大學(xué)出版社，2002</p><p>　　[4] 劉振鵬，張曉莉，郝杰．?dāng)?shù)據(jù)結(jié)構(gòu)[M]．北京：中國(guó)鐵道出版社，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)先級(jí)*/</p><p>　　int f2[7]={2,2,4,4,6,1,0};/*棧外元素優(yōu)先級(jí)*/</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")