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

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

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

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

4、t;/b></p><p>　　（1）運行所設計的系統(tǒng)。</p><p>　?。?）回答有關問題。</p><p>　?。?）提交課程設計報告。</p><p>　?。?）提交軟盤（源程序、設計報告文檔）。</p><p>　?。?）依內容的創(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>　　正文的內容:一、課題的主要

7、功能；二、課題的功能模塊的劃分（要求畫出模塊圖）；三、主要功能的實現(xiàn)（至少要有一個主要模塊的流程圖）；四、程序調試；五、總結；六、附件（所有程序的原代碼，要求對程序寫出必要的注釋）。</p><p>　　正文總字數(shù)要求在5000字以上（不含程序原代碼）。</p><p><b>　　1.1設計內容</b></p><p>　　課題三：中綴算術表

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

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

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

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

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

13、>　　1.4詳細設計</b></p><p>　　a.采用C語言定義相關的數(shù)據(jù)類型。</p><p>　　寫出各模塊的類C碼算法。</p><p>　　c.畫出各函數(shù)的調用關系圖、主要函數(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將中綴表達式轉換成后綴表達式</p><p>　　先初始化棧，然后將‘=’進棧，從exp中讀取字符，若它為數(shù)字則一次存入postexp中，并以空格標志結束。若為運算符，則和棧頂運算符比較，如果棧頂運算符優(yōu)先級低則該運算符進棧。待字符串exp掃描完畢，則將運算符棧中‘=’之前所有運算符出棧并存放帶postexp中，最后得到后綴表達式postexp。</p><p>　　void tran

17、s(char *exp,char postexp[]) //將算術表達式exp轉換為后綴表達式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ù)值串結束的標志</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表達式添加結束標識</p><p><b>　　}</b></p><p>　　1.4.3后綴表達式求值</p><p>　　從左到右讀入

27、后綴表達式，若讀入的是一個操作數(shù)，就將它入數(shù)值棧。若讀入的是一個運算符。就從數(shù)值棧中連續(xù)出出棧兩個元素，并將計算結果入數(shù)值棧，對整個后綴表達式讀入結束時，棧頂元素就是計算結果。</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;//計算結果進棧 </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;//計算結果進棧</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;//計算結果進棧</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;//計算結果進棧</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ù)字字符轉換成對應的數(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調試分析以及設計體會</p><p>　　1.5.1調試分析。</p><p><b>　　1程序的界面&l

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

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

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

43、;/p><p>　　通過完成這次算術表達式求值的課程設計。我對數(shù)據(jù)結構這門課又有了更加深刻的了解，也提升了自己的邏輯思維能力。以及程序編寫能力，即使有時候晚上編程到很晚，但心里還是美滋滋的，因為看到自己親自編寫的程序可以執(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