數(shù)據(jù)結(jié)構(gòu)課程設計---中綴算術表達式求值

1、<p>　　課 程 設 計 報 告</p><p>　　課程名稱 數(shù)據(jù)結(jié)構(gòu)課程設計 </p><p>　　課題名稱 中綴算術表達式求值 </p><p>　　2012年 7 月 6 日</p><p><b>　　1. 考核方式</b></p>&

2、lt;p>　　指導老師負責驗收程序的運行結(jié)果，并結(jié)合學生的工作態(tài)度、實際動手能力、創(chuàng)新精神和設計報告等進行綜合考評，并按優(yōu)秀、良好、中等、及格和不及格五個等級給出每位同學的課程設計成績。具體考核標準包含以下幾個部分：</p><p>　　（1）平時出勤 （占10%）</p><p>　?。?）系統(tǒng)需求分析、功能設計、數(shù)據(jù)結(jié)構(gòu)設計及程序總體結(jié)構(gòu)合理與否（占10%）</p>

3、<p>　?。?）程序能否完整、準確地運行，個人能否獨立、熟練地調(diào)試程序（占40%）</p><p>　　（4）設計報告（占30%）</p><p>　　注意：不得抄襲他人的報告（或給他人抄襲），一旦發(fā)現(xiàn)，成績?yōu)榱惴帧?lt;/p><p>　?。?）獨立完成情況（占10%）。</p><p><b>　　2.課程驗收要求&l

4、t;/b></p><p>　?。?）運行所設計的系統(tǒng)。</p><p>　?。?）回答有關問題。</p><p>　?。?）提交課程設計報告。</p><p>　?。?）提交軟盤（源程序、設計報告文檔）。</p><p>　　（5）依內(nèi)容的創(chuàng)新程度，完善程序情況及對程序講解情況打分。</p>&l

5、t;p><b>　　3．進度安排</b></p><p>　　第 20 周：星期一 8：00——12：00 上課 </p><p>　　星期一 14：30——18：30 上機</p><p>　　星期二 14：30——18：30 上機</p><p>　　星期三 8：00——12：00

6、 上機</p><p><b>　　附：</b></p><p>　　課程設計報告裝訂順序：封面、任務書、目錄、正文、評分表、附件（A4大小的圖紙及程序清單）。 </p><p>　　正文的格式:一級標題用3號黑體,二級標題用四號宋體加粗,正文用小四號宋體;行距為22。</p><p>　　正文的內(nèi)容:一、課題的主要

7、功能；二、課題的功能模塊的劃分（要求畫出模塊圖）；三、主要功能的實現(xiàn)（至少要有一個主要模塊的流程圖）；四、程序調(diào)試；五、總結(jié)；六、附件（所有程序的原代碼，要求對程序?qū)懗霰匾淖⑨專?lt;/p><p>　　正文總字數(shù)要求在5000字以上（不含程序原代碼）。</p><p><b>　　1.1設計內(nèi)容</b></p><p>　　課題三：中綴算術表

8、達式求值</p><p>　　我們很早就學習如何書寫及計算表達式，諸如：8+5*（7-3）之類的表達式，先算括號內(nèi)的7減去3，得到4，然后再算5乘以4，得到20，再計算8加上20，得到28，因此該表達式的值為28。這是人們熟悉的運算規(guī)則額：有括號先算括號內(nèi)；無括號時，先做乘除法，后做加減法；對于相同級別的運算按從左到右的次序運算。而計算機是如何實現(xiàn)表達式的計算的呢？應用棧的相關知識，編程序?qū)崿F(xiàn)之。</p&g

9、t;<p>　　設計思路：從鍵盤輸入中綴表達式，然后將中綴表達式轉(zhuǎn)換為后綴表達式，利用后綴表達式求值。要求以字符序列的形式從終端輸入語法正確的、不含變量的整數(shù)表達式，利用給定的算術符優(yōu)先關系，實現(xiàn)對算數(shù)四則混合運算表達式的求值，并演示在求值過程中運算符棧、操作符棧、輸入字符和主要操作的變化過程。</p><p><b>　　1.2需求分析</b></p><

10、p><b>　　a.程序的功能。</b></p><p>　　該程序能夠?qū)θ我獾乃膭t運算表達式進行中綴表達式向后綴表達式的轉(zhuǎn)換，并得出其計算結(jié)果。</p><p>　　b.輸入輸出的要求。</p><p>　　輸入輸出均是阿拉伯數(shù)字和四則運算操作符以及括號運算符，按照程序所給提示進行標準輸入輸出即可。</p><p&g

11、t;<b>　　1.3概要設計</b></p><p>　　a.程序由哪些模塊組成以及模塊之間的層次結(jié)構(gòu)、各模塊的調(diào)用關系；每個模塊的功能。</p><p>　　b.課題涉及的數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫結(jié)構(gòu)；即要存儲什么數(shù)據(jù)，這些數(shù)據(jù)是什么樣的結(jié)構(gòu)，它們之間有什么關系等。</p><p>　　根據(jù)問題描述和要求，系統(tǒng)要求能夠正確求出算術表達式的值。在進行

12、算術表達式求值過程中，考慮到我們輸入的是中綴表達式，采用后綴表達式比較容易計算，因此先將中綴表達式轉(zhuǎn)換成后綴表達式。程序應該具有：“將算術表達式轉(zhuǎn)化為后綴表達式”、“利用后綴表達式求值”等基本模塊。由于有優(yōu)先級的問題，根據(jù)優(yōu)先級不同的運算符運算的次序是不同的，因此更具其優(yōu)先級的大小抽象的將其定義為不同的大小。本程序的數(shù)據(jù)結(jié)構(gòu)為棧。程序的主要模塊可以分為運算符棧，操作數(shù)棧，以及各類函數(shù)。</p><p><b

13、>　　1.4詳細設計</b></p><p>　　a.采用C語言定義相關的數(shù)據(jù)類型。</p><p>　　寫出各模塊的類C碼算法。</p><p>　　c.畫出各函數(shù)的調(diào)用關系圖、主要函數(shù)的流程圖。</p><p>　　1.4.1數(shù)據(jù)類型定義</p><p>　　表達式求值中運算符對應優(yōu)先級的定義&l

14、t;/p><p><b>　　struct</b></p><p>　　{char ch;</p><p><b>　　int pri;</b></p><p>　　}lpri[7]={{'=',0},{'(',1},{'*',5},{'/

15、9;,5},{'+',3},{'-',3},{')',6}},rpri[7]={{'=',0},{'(',6},{'*',4},{'/',4},{'+',2},{'-',2},{')',1}};//運算符優(yōu)先級的定義</p><p>　　1.4

16、.2將中綴表達式轉(zhuǎn)換成后綴表達式</p><p>　　先初始化棧，然后將‘=’進棧，從exp中讀取字符，若它為數(shù)字則一次存入postexp中，并以空格標志結(jié)束。若為運算符，則和棧頂運算符比較，如果棧頂運算符優(yōu)先級低則該運算符進棧。待字符串exp掃描完畢，則將運算符棧中‘=’之前所有運算符出棧并存放帶postexp中，最后得到后綴表達式postexp。</p><p>　　void tran

17、s(char *exp,char postexp[]) //將算術表達式exp轉(zhuǎn)換為后綴表達式postexp</p><p><b>　　{</b></p><p>　　char st[MaxSize];</p><p>　　int top=-1;</p><p>　　int i=0;//i作為postexp

18、的下標</p><p>　　top++;//'='進棧</p><p>　　st[top]='=';</p><p>　　while(*exp!='\0')</p><p><b>　　{</b></p><p>　　if(!InOp(*exp

19、))//為數(shù)字字符</p><p><b>　　{</b></p><p>　　while(*exp>='0'&&*exp<='9')</p><p><b>　　{</b></p><p>　　postexp[i++]=*exp;&

20、lt;/p><p><b>　　exp++;</b></p><p><b>　　}</b></p><p>　　postexp[i++]=' ';//數(shù)值串結(jié)束的標志</p><p><b>　　}</b></p><p>　　els

21、e//為運算符</p><p><b>　　{</b></p><p>　　switch(Precede(st[top],*exp))</p><p><b>　　{</b></p><p>　　case -1://棧頂運算符的優(yōu)先級低</p><p><

22、;b>　　top++;</b></p><p>　　st[top]=*exp;//進棧</p><p>　　exp++;//繼續(xù)掃描其他字符</p><p><b>　　break;</b></p><p>　　case 0: //只有括號滿足這種情況</p><

23、p>　　top--; //棧頂元素退棧</p><p><b>　　exp++;</b></p><p><b>　　break;</b></p><p>　　case 1://退棧并輸出到postexp中</p><p>　　postexp[i++]=st[top];

24、</p><p><b>　　top--;</b></p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</

25、b></p><p>　　while(st[top]!='=')//此時exp掃描完畢，退棧到'='為止</p><p><b>　　{</b></p><p>　　postexp[i++]=st[top];</p><p><b>　　top--;</b&g

26、t;</p><p><b>　　}</b></p><p>　　postexp[i]='\0';//給postexp表達式添加結(jié)束標識</p><p><b>　　}</b></p><p>　　1.4.3后綴表達式求值</p><p>　　從左到右讀入

27、后綴表達式，若讀入的是一個操作數(shù)，就將它入數(shù)值棧。若讀入的是一個運算符。就從數(shù)值棧中連續(xù)出出棧兩個元素，并將計算結(jié)果入數(shù)值棧，對整個后綴表達式讀入結(jié)束時，棧頂元素就是計算結(jié)果。</p><p>　　float compvalue(char *postexp)//計算后綴表達式postexp的值</p><p><b>　　{</b></p>&l

28、t;p>　　float s[MaxSize];//數(shù)值棧</p><p>　　float a,b,d;</p><p>　　int top=-1;</p><p>　　while(*postexp!='\0')</p><p><b>　　{</b></p><p>

29、　　switch(*postexp)</p><p><b>　　{</b></p><p><b>　　case '+':</b></p><p>　　a=s[top];//棧頂元素退棧</p><p><b>　　top--;</b></p>

30、<p>　　b=s[top];//棧頂元素退棧 </p><p>　　s[top]=a+b;//計算結(jié)果進棧 </p><p><b>　　break;</b></p><p><b>　　case '-':</b></p><p><b>　

31、　a=s[top];</b></p><p><b>　　top--;</b></p><p><b>　　b=s[top];</b></p><p>　　s[top]=b-a;//計算結(jié)果進棧</p><p><b>　　break;</b></p>

32、;<p><b>　　case '*':</b></p><p><b>　　a=s[top];</b></p><p><b>　　top--;</b></p><p><b>　　b=s[top];</b></p><p>

33、;　　s[top]=a*b;//計算結(jié)果進棧</p><p><b>　　break;</b></p><p><b>　　case '/':</b></p><p><b>　　a=s[top];</b></p><p><b>　　top--;

34、</b></p><p><b>　　b=s[top];</b></p><p><b>　　if(a!=0)</b></p><p>　　s[top]=b/a;//計算結(jié)果進棧</p><p><b>　　else </b></p><p&

35、gt;<b>　　{</b></p><p>　　printf("\n\t除零錯誤!\n");</p><p>　　exit(0);//異常退出</p><p><b>　　}</b></p><p><b>　　break;</b></p&g

36、t;<p>　　default ://處理數(shù)字字符</p><p><b>　　d=0;</b></p><p>　　//將連續(xù)的數(shù)字字符轉(zhuǎn)換成對應的數(shù)值存到d中</p><p>　　while(*postexp>='0'&&*postexp<='9')&l

37、t;/p><p><b>　　{</b></p><p>　　d=d*10 + *postexp - '0';</p><p>　　postexp++;</p><p><b>　　}</b></p><p><b>　　top++;</b>

38、</p><p><b>　　s[top]=d;</b></p><p><b>　　}</b></p><p>　　postexp++;//繼續(xù)處理其他的字符</p><p><b>　　}</b></p><p>　　returns[top];

39、</p><p><b>　　}</b></p><p>　　1.4.4主要函數(shù)流程圖</p><p>　　圖一 主要函數(shù)流程圖</p><p>　　1.5調(diào)試分析以及設計體會</p><p>　　1.5.1調(diào)試分析。</p><p><b>　　1程序的界面&l

40、t;/b></p><p><b>　　2正確的執(zhí)行結(jié)果</b></p><p>　　3如果選擇T或是t程序終止，其他則繼續(xù)運行</p><p>　　b.程序調(diào)試中遇到的問題以及解決問題的方法。</p><p>　　c.課程設計過程經(jīng)驗教訓、心得體會。</p><p><b>　　

41、1.5.2心得體會</b></p><p>　　完成這次數(shù)據(jù)結(jié)構(gòu)的課程設計的時間雖然不長，但是我還是學到了不少東西。</p><p>　　在做課程設計前，我首先讀懂老師給的課題，然后仔細閱讀課本。有不懂的知識點就和同學交流并向老師咨詢。這個課題最主要的是要明白棧的相關知識點，尤其是棧“后進先出”特點，在比較完運算符優(yōu)先級后，將比棧頂運算符高優(yōu)先級放入棧中，待表達式全部被掃描完。

42、在編寫后綴表達式求值函數(shù)時，忘了處理數(shù)字字符，因為主函數(shù)里定義的是字符數(shù)組，所以在對表達式求值時要轉(zhuǎn)換成對應的數(shù)字。此外，在編寫程序的過程中，不能心急，煩躁，遇到問題要耐心查找資料，然后解決，有時候，會因為一點小錯誤導致編譯出現(xiàn)錯誤，而這些錯誤又很難被發(fā)現(xiàn)，這時就需要我們細心尋找，運用所學的知識，一點一點地分析問題，再去解決這些問題。因為成功的背后必定會有辛勤和汗水。這也讓我體會到想要在軟件編程方面發(fā)展并取得成功所需要付出的努力。<

43、;/p><p>　　通過完成這次算術表達式求值的課程設計。我對數(shù)據(jù)結(jié)構(gòu)這門課又有了更加深刻的了解，也提升了自己的邏輯思維能力。以及程序編寫能力，即使有時候晚上編程到很晚，但心里還是美滋滋的，因為看到自己親自編寫的程序可以執(zhí)行，達到所必須的要求，之前的苦累全都拋在腦后了。</p><p>　　最后，非常感謝xx老師和田老師的幫助，每次問的問題都很耐心地為我講解，即使是連我都認為很笨的問題，也都為

44、我詳細的分析。謝謝！</p><p><b>　?。?）使用說明</b></p><p>　　用戶使用手冊：說明如何使用你編寫的程序，詳細列出每一步的操作步驟。</p><p><b>　?。?）書寫格式</b></p><p>　　a.設計報告要求用A4紙打印成冊：</p><

45、p>　　b.一級標題用3號黑體,二級標題用四號宋體加粗,正文用小四號宋體;行距為22。</p><p><b>　　（7）附錄</b></p><p>　　源程序清單（帶注釋）</p><p>　　計算機與通信學院課程設計評分表</p><p>　　課程名稱： &l