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

1、<p>　　課 程 設(shè) 計(jì) 說 明 書</p><p>　　課程名稱： 數(shù)據(jù)結(jié)構(gòu) </p><p>　　設(shè)計(jì)題目： 表達(dá)式求值 </p><p>　　院 系： </p><p>　　學(xué)生姓名： <

2、;/p><p>　　學(xué) 號(hào)： </p><p><b>　　專業(yè)班級(jí)： </b></p><p>　　指導(dǎo)教師： </p><p>　　2011年 6 月 25 日</p><p>　　課 程 設(shè) 計(jì) 任 務(wù) 書<

3、/p><p><b>　　表達(dá)式求值</b></p><p><b>　　摘 要：</b></p><p>　　表達(dá)式求值是程序設(shè)計(jì)語言編譯中的一個(gè)最基本的問題。它的實(shí)現(xiàn)是棧應(yīng)用的一個(gè)典型例子。我們使用的是一種簡單直觀，廣為使用的算法—“算符優(yōu)先法”。</p><p>　　要把一個(gè)表達(dá)式翻譯成正確求值

4、的一個(gè)機(jī)器指令序列，或者直接對表達(dá)式求值，首先要能夠正確解釋表達(dá)式。要知道算法四則運(yùn)算即（1）先乘除，后加減；（2）從左到右；（3）先括號(hào)內(nèi)，后括號(hào)外。算法優(yōu)先級(jí)法就是根據(jù)這個(gè)運(yùn)算優(yōu)先級(jí)的規(guī)定來實(shí)現(xiàn)對表達(dá)式的編譯或解釋執(zhí)行的。</p><p>　　任何一個(gè)表達(dá)式都是由操作數(shù)，運(yùn)算符和界限符組成的，我們稱之它們?yōu)閱卧~。一般地，操作數(shù)既可以是常數(shù)也可以是被說明為變量或常量的標(biāo)識(shí)符；運(yùn)算符可以分為算術(shù)運(yùn)算符，關(guān)系運(yùn)算符

5、和邏輯運(yùn)算符三類；基本界限符有左右括號(hào)和表達(dá)式結(jié)束符等。</p><p><b>　　關(guān)鍵詞：</b></p><p>　　表達(dá)式 棧（出戰(zhàn)，入棧） 括號(hào)匹配 符號(hào)優(yōu)先級(jí) 運(yùn)算</p><p><b>　　目 錄</b></p><p>　　一.設(shè)計(jì)背景………………………………………

6、………………………3</p><p>　　1.1．目的 ……………………………………………………………3</p><p>　　1.2．背景 ……………………………………………………………3</p><p>　　二.設(shè)計(jì)方案………………………………………………………………3</p><p>　　方案實(shí)施 ………………………………………………

7、……………4</p><p>　　3.1運(yùn)算……………………………………………………………… 4</p><p>　　結(jié)果與結(jié)論 …………………………………………………………6</p><p>　　4.1.運(yùn)算結(jié)果…………………………………………………………6</p><p>　　4.2.結(jié)論………………………………………………………………

8、7</p><p>　　收獲與致謝……………………………………………………………7</p><p>　　5.1.收獲………………………………………………………………7</p><p>　　5.2.致謝………………………………………………………………7</p><p>　　六．參考文獻(xiàn) ……………………………………………………………8</

9、p><p>　　八．指導(dǎo)教師評語 ………………………………………………………9</p><p><b>　　一. 設(shè)計(jì)背景</b></p><p><b>　　1.1．目的</b></p><p>　　通過課程設(shè)計(jì)，鞏固和加深對棧的理論知識(shí)的理解；掌握現(xiàn)實(shí)復(fù)雜問題的分析和解決方法；提高利用計(jì)算機(jī)分析解決

10、綜合性實(shí)際問題的基本能力。</p><p><b>　　1.2．背景</b></p><p>　　“數(shù)據(jù)結(jié)構(gòu)”是計(jì)算機(jī)程序設(shè)計(jì)的重要理論技術(shù)基礎(chǔ)，它不僅是計(jì)算機(jī)學(xué)科的核心課程，而且已成為其他理科專業(yè)的熱門選修課。棧是重要的線性結(jié)構(gòu)，從數(shù)據(jù)結(jié)構(gòu)角度看，棧也是線性表，其特點(diǎn)在于棧的基本操作是線性表操作的子集，它的操作受限的線性表，因此，可稱為限定性的數(shù)據(jù)結(jié)構(gòu)。但從數(shù)據(jù)類型

11、角度看，它是和線性表大不相同的一類重要的抽象數(shù)據(jù)類型。由于棧廣泛應(yīng)用在各種軟件系統(tǒng)中，因此在面向?qū)ο蟮某绦蛟O(shè)計(jì)中，它是多型數(shù)據(jù)類型。表達(dá)式計(jì)算是實(shí)現(xiàn)程序設(shè)計(jì)語言的基本問題之一，也是棧的應(yīng)用的一個(gè)典型例子。</p><p><b>　　設(shè)計(jì)方案</b></p><p>　　我負(fù)責(zé)的部分是求值的過程，使OPTR和OPND分別為運(yùn)算符棧和運(yùn)算數(shù)棧，算法的基本思想是：<

12、/p><p>　?。?）首先置操作數(shù)棧為棧，表達(dá)式起始符“=”為運(yùn)算符棧的棧底元素。</p><p>　?。?）依次讀入表達(dá)式中的每一個(gè)字符，若是操作數(shù)則進(jìn)OPND棧，若是運(yùn)算符則和OPTR棧的棧頂運(yùn)算符比較優(yōu)先權(quán)后做相應(yīng)操作，直至整個(gè)表達(dá)式求值完畢（即OPTR棧的棧頂元素和讀入的字符均為“=”）。</p><p><b>　　三.方案實(shí)施</b>

13、</p><p><b>　　3.1.運(yùn)算</b></p><p>　　SElemType EvaluateExpression()</p><p>　　{SqStack OPTR,OPND;</p><p>　　SElemType a,b,x, theta;</p><p>　　char c;

14、// 存放由鍵盤接收的字符串 </p><p>　　char z[6]; // 存放整數(shù)字符串 </p><p><b>　　int i;</b></p><p><b>　　float f;</b></p><p>　　InitStack(OPTR);//構(gòu)造一個(gè)運(yùn)算符棧</p>&

15、lt;p>　　Push(OPTR,'=');//將“=”號(hào)壓入棧底</p><p>　　InitStack(OPND);//構(gòu)造一個(gè)運(yùn)算數(shù)棧</p><p>　　c=getchar();</p><p>　　while(c!='='||GetTop(OPTR)!='=')//棧頂不是“=”號(hào)且輸入不是“=”號(hào)&l

16、t;/p><p><b>　　{</b></p><p>　　if(In(c))//輸入的字符為運(yùn)算符</p><p>　　switch(Precede(GetTop(OPTR),c))</p><p><b>　　{</b></p><p>　　case'<

17、9;://棧頂元素優(yōu)先權(quán)低</p><p>　　Push(OPTR, c);</p><p>　　c=getchar();</p><p><b>　　break;</b></p><p>　　case'='://脫括號(hào)并接下一個(gè)字符</p><p>　　Pop(OPTR,x);&

18、lt;/p><p>　　c=getchar();</p><p><b>　　break;</b></p><p>　　case'>':退棧并將運(yùn)算結(jié)果入棧</p><p>　　Pop(OPTR,theta);</p><p>　　Pop(OPND,b);</p>

19、<p>　　Pop(OPND,a);</p><p>　　Push(OPND,Operate(a,theta,b));</p><p><b>　　}</b></p><p>　　else if(c>='0'&&c<='9'||c=='.'){</p

20、><p>　　if(c>='0'&&c<='9')</p><p><b>　　i=0;</b></p><p><b>　　do</b></p><p><b>　　{</b></p><p>&

21、lt;b>　　z[i]=c;</b></p><p><b>　　i++;</b></p><p>　　c=getchar();</p><p>　　}while(c>='0'&&c<='9');</p><p>　　int d=z[i-1]-

22、48;</p><p><b>　　int e1=1;</b></p><p>　　for(int j=i-2;j>=0;j--)</p><p><b>　　{</b></p><p><b>　　e1=e1*10;</b></p><p>　　

23、d=d+(z[j]-48)*e1;</p><p><b>　　}</b></p><p>　　if(c=='.')</p><p>　　c=getchar();</p><p>　　float digit=0.0,e=0.1;</p><p>　　while(c>='

24、;0'&&c<='9')</p><p><b>　　{</b></p><p>　　digit=digit+(c-48)*e;</p><p><b>　　e=e*0.1;</b></p><p>　　c=getchar();</p>&

25、lt;p><b>　　}</b></p><p>　　f=(float)d+digit;</p><p>　　Push(OPND,f);</p><p><b>　　}</b></p><p>　　else //不能出現(xiàn)除了“+”，“-”，“*”，“/”以及小數(shù)點(diǎn)“.”，“=”和操作數(shù)以外的

26、非法字符</p><p><b>　　{</b></p><p>　　printf("******************************\n");</p><p>　　printf("*出現(xiàn)了非法字符或沒有以=結(jié)尾!*\n");</p><p>　　printf(&quo

27、t;******************************\n");</p><p><b>　　exit(0);</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　return GetTop(OPND)

28、;</p><p>　　return OK;</p><p><b>　　}</b></p><p><b>　　四. 結(jié)果與結(jié)論</b></p><p><b>　　4.1．運(yùn)算結(jié)果</b></p><p>　　1.當(dāng)出現(xiàn)非法字符或者是沒有以“=”結(jié)尾

29、時(shí)：</p><p><b>　　圖.1</b></p><p>　　圖.1表示運(yùn)算表達(dá)式中不能出現(xiàn)非法字符</p><p>　　2.沒有以“=”號(hào)結(jié)尾時(shí)</p><p><b>　　圖.2</b></p><p>　　圖.2表示運(yùn)算表達(dá)式要以“=”號(hào)結(jié)尾</p>

30、<p><b>　　結(jié)論：</b></p><p>　　在本次課程設(shè)計(jì)的程序所支持的表達(dá)式進(jìn)行運(yùn)算時(shí)不能出現(xiàn)非法字符，表達(dá)式必須要以“=”號(hào)結(jié)尾。</p><p><b>　　五. 收獲與致謝</b></p><p><b>　　5.1.收獲</b></p><p&g

31、t;　　通過這次課程設(shè)計(jì)，不僅僅讓我知道自己的只是還遠(yuǎn)遠(yuǎn)不夠，復(fù)習(xí)了我的Ｃ語</p><p>　　言的相關(guān)知識(shí)、還鞏固了數(shù)據(jù)結(jié)構(gòu)關(guān)于棧的算法的知識(shí)，更鍛煉了我的意志。</p><p><b>　　5.2.致謝</b></p><p>　　通過這次的課程設(shè)計(jì)讓我知道了老師說的很對，上課認(rèn)真聽下課多多的動(dòng)手操作很重要，在這里非常感謝xx老師這半年來

32、交給我們的知識(shí)，xx感謝我的組員們特別是組長，讓我了解到團(tuán)結(jié)真的很重要。</p><p><b>　　六. 參考文獻(xiàn)</b></p><p>　　[1] 嚴(yán)蔚敏，吳偉民．《數(shù)據(jù)結(jié)構(gòu)》（C語言版）清華大學(xué)出版社2010年10月</p><p>　　[2]（美）克林伯格．《算法設(shè)計(jì)》 清華大學(xué)出版社 2007年6月</p>