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

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

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

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

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

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

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

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

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

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

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

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

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

13、>　　1.4詳細(xì)設(shè)計(jì)</b></p><p>　　a.采用C語言定義相關(guān)的數(shù)據(jù)類型。</p><p>　　寫出各模塊的類C碼算法。</p><p>　　c.畫出各函數(shù)的調(diào)用關(guān)系圖、主要函數(shù)的流程圖。</p><p>　　1.4.1數(shù)據(jù)類型定義</p><p>　　表達(dá)式求值中運(yùn)算符對(duì)應(yīng)優(yōu)先級(jí)的定義&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ùn)算符優(yōu)先級(jí)的定義</p><p>　　1.4

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

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

18、的下標(biāo)</p><p>　　top++;//'='進(jìn)棧</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é)束的標(biāo)志</p><p><b>　　}</b></p><p>　　els

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

22、;b>　　top++;</b></p><p>　　st[top]=*exp;//進(jìn)棧</p><p>　　exp++;//繼續(xù)掃描其他字符</p><p><b>　　break;</b></p><p>　　case 0: //只有括號(hào)滿足這種情況</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]!='=')//此時(shí)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表達(dá)式添加結(jié)束標(biāo)識(shí)</p><p><b>　　}</b></p><p>　　1.4.3后綴表達(dá)式求值</p><p>　　從左到右讀入

27、后綴表達(dá)式，若讀入的是一個(gè)操作數(shù)，就將它入數(shù)值棧。若讀入的是一個(gè)運(yùn)算符。就從數(shù)值棧中連續(xù)出出棧兩個(gè)元素，并將計(jì)算結(jié)果入數(shù)值棧，對(duì)整個(gè)后綴表達(dá)式讀入結(jié)束時(shí)，棧頂元素就是計(jì)算結(jié)果。</p><p>　　float compvalue(char *postexp)//計(jì)算后綴表達(dá)式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;//計(jì)算結(jié)果進(jìn)棧 </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;//計(jì)算結(jié)果進(jìn)棧</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;//計(jì)算結(jié)果進(jìn)棧</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;//計(jì)算結(jié)果進(jìn)棧</p><p><b>　　else </b></p><p&

35、gt;<b>　　{</b></p><p>　　printf("\n\t除零錯(cuò)誤!\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)換成對(duì)應(yīng)的數(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)試分析以及設(shè)計(jì)體會(huì)</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ù)運(yùn)行</p><p>　　b.程序調(diào)試中遇到的問題以及解決問題的方法。</p><p>　　c.課程設(shè)計(jì)過程經(jīng)驗(yàn)教訓(xùn)、心得體會(huì)。</p><p><b>　　

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

42、在編寫后綴表達(dá)式求值函數(shù)時(shí)，忘了處理數(shù)字字符，因?yàn)橹骱瘮?shù)里定義的是字符數(shù)組，所以在對(duì)表達(dá)式求值時(shí)要轉(zhuǎn)換成對(duì)應(yīng)的數(shù)字。此外，在編寫程序的過程中，不能心急，煩躁，遇到問題要耐心查找資料，然后解決，有時(shí)候，會(huì)因?yàn)橐稽c(diǎn)小錯(cuò)誤導(dǎo)致編譯出現(xiàn)錯(cuò)誤，而這些錯(cuò)誤又很難被發(fā)現(xiàn)，這時(shí)就需要我們細(xì)心尋找，運(yùn)用所學(xué)的知識(shí)，一點(diǎn)一點(diǎn)地分析問題，再去解決這些問題。因?yàn)槌晒Φ谋澈蟊囟〞?huì)有辛勤和汗水。這也讓我體會(huì)到想要在軟件編程方面發(fā)展并取得成功所需要付出的努力。<

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

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

45、p>　　b.一級(jí)標(biāo)題用3號(hào)黑體,二級(jí)標(biāo)題用四號(hào)宋體加粗,正文用小四號(hào)宋體;行距為22。</p><p><b>　?。?）附錄</b></p><p>　　源程序清單（帶注釋）</p><p>　　計(jì)算機(jī)與通信學(xué)院課程設(shè)計(jì)評(píng)分表</p><p>　　課程名稱： &l