數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--《十進制表達式四則運算》

1、<p><b>　　目 錄</b></p><p><b>　　前言1</b></p><p><b>　　正文1</b></p><p>　　2.1 課程設(shè)計的教學(xué)目的和任務(wù)1</p><p>　　2.2課程設(shè)計的主要內(nèi)容2</p><p

2、>　　2.3課程設(shè)計報告的要求2</p><p>　　2.4算法設(shè)計基本要求2</p><p>　　2.4.1算法設(shè)計主要內(nèi)容3</p><p>　　2.4.2算法設(shè)計的思想3</p><p>　　2.5 算法描述3</p><p>　　2.6 設(shè)計方案3</p><p>

3、　　2.7 設(shè)計內(nèi)容4</p><p>　　2.7.1需求分析4</p><p>　　2.7.2概要設(shè)計4</p><p>　　2.7.3 詳細設(shè)計5</p><p>　　2.7.4 調(diào)試分析與結(jié)果8</p><p>　　2.7.5 算法分析10</p><p><b>

4、　　課程總結(jié)11</b></p><p><b>　　參考文獻12</b></p><p><b>　　附錄13</b></p><p><b>　　前 言</b></p><p>　　簡單的四則運算對我們來說很簡單，但是當(dāng)你一直都在重復(fù)這個簡單的腦力操作時，

5、也許你會疏忽，會不小心搞錯，從而影響工作，比如說會計等職業(yè)，所以我們就在考慮，當(dāng)今社會是信息時代，能否用計算機代替人類做這份工作呢？在數(shù)據(jù)結(jié)構(gòu)中，則能用棧實現(xiàn)簡單四則運算，為我們進行計算，避免不必要的錯誤。</p><p>　　棧（stack，又稱為堆棧）是一種特殊的線性表。棧（stack）是限定僅在表尾進行插入或刪除操作的線性表，允許進行插入和刪除操作的一端稱為棧頂(top)，另一端為棧底(bottom)；棧底

6、固定，而棧頂浮動；棧中元素個數(shù)為零時稱為空棧。棧中的元素的進出是按照“后進先出”的原則進行，根據(jù)棧的這種特征，因此棧又稱為后進先出表（LIFO表—Last In First Out）。</p><p>　　由于棧的結(jié)構(gòu)具有后進先出的固有特性，致使棧成為程序設(shè)計中的有用工具。運用棧來實現(xiàn)表達式求值問題也是程序設(shè)計語言編譯中的一個最基本的問題。</p><p><b>　　正 文&l

7、t;/b></p><p>　　2.1 課程設(shè)計的教學(xué)目的和任務(wù)</p><p>　　本學(xué)期我們對《數(shù)據(jù)結(jié)構(gòu)》這門課程進行了學(xué)習(xí)。這門課程是一門實踐性非常強的課程，為了讓大家更好地理解與運用所學(xué)知識，提高動手能力，我們進行了此次課程設(shè)計實習(xí)?！稊?shù)據(jù)結(jié)構(gòu)課程設(shè)計》是計算機專業(yè)集中實踐性環(huán)節(jié)之一，是學(xué)習(xí)完《數(shù)據(jù)結(jié)構(gòu)》課程后進行的一次全面的綜合練習(xí)。這次課程設(shè)計不但要求學(xué)生掌握《數(shù)據(jù)結(jié)構(gòu)》

8、中的各方面知識，還要求學(xué)生具備一定的C語言基礎(chǔ)和編程能力。</p><p><b>　　其目的是：</b></p><p>　　(1) 使學(xué)生進一步理解和掌握所學(xué)的各種數(shù)據(jù)類型的結(jié)構(gòu)和操作實現(xiàn)算法，以及它們在程序中的使用方法。</p><p>　　(2) 使學(xué)生初步掌握軟件開發(fā)過程的問題分析、設(shè)計、編碼、測試等基本方法和基本技能。</p&

9、gt;<p>　　(3) 使學(xué)生掌握使用各種計算機資料和有關(guān)參考資料，提高學(xué)生進行程序設(shè)計的基本能力。</p><p>　　(4) 使學(xué)生能用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。</p><p>　?。?）要達到理論與實際應(yīng)用相結(jié)合，使學(xué)生能夠根據(jù)數(shù)據(jù)對象的特性，學(xué)會數(shù)據(jù)組織的方法，能把現(xiàn)實世界中的實際問題在計算機內(nèi)部表示出

10、來，并培養(yǎng)良好的程序設(shè)計技能。 </p><p>　?。?）在實踐中認識為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，掌握數(shù)據(jù)結(jié)構(gòu)、程序設(shè)計語言、程序設(shè)計技術(shù)之間的關(guān)系，是前面所學(xué)知識的綜合和回顧。</p><p>　　2.2課程設(shè)計的主要內(nèi)容</p><p>　　(1) 問題分析和任務(wù)定義。</p><p>　　根據(jù)題目的要求，充分地分析問題，明確要求。</

11、p><p>　　(2)在這個過程中，要綜合考慮系統(tǒng)功能，使得系統(tǒng)結(jié)構(gòu)清晰、合理、簡單和易于調(diào)試，基本操作的規(guī)格說明盡可能明確具體。</p><p><b>　　(3)程序編碼。</b></p><p>　　把詳細設(shè)計的結(jié)果進一步求精為程序設(shè)計語言程序。同時加入一些注解和斷言，使程序中邏輯概念清楚。</p><p>　　(4)

12、 程序調(diào)試與測試。</p><p>　　能夠熟練掌握調(diào)試工具的各種功能，設(shè)計測試數(shù)據(jù)確定疑點，通過修改程序來證實它或繞過它。調(diào)試正確后，認真整理源程序及其注釋，形成格式和風(fēng)格良好的源程序清單和結(jié)果。</p><p><b>　　(5) 結(jié)果分析。</b></p><p>　　程序運行結(jié)果包括正確的輸入及其輸出結(jié)果和含有錯誤的輸入及其輸出結(jié)果。&

13、lt;/p><p><b>　　撰寫課程設(shè)計報告。</b></p><p>　　2.3課程設(shè)計報告的要求</p><p>　　課程設(shè)計報告要求規(guī)范書寫。應(yīng)當(dāng)包括如下內(nèi)容：</p><p>　?。?）問題描述：描述要求編程解決的問題。</p><p>　?。?）基本要求：給出程序要達到的具體的要求。&l

14、t;/p><p>　?。?） 算法思想：描述解決相應(yīng)問題算法的設(shè)計思想。</p><p>　?。?）源程序：給出所有源程序清單，要求程序有充分的注釋語句，至少要注釋每個函數(shù)參數(shù)的含義和函數(shù)返回值的含義。</p><p>　?。?）測試情況：給出程序的測試情況，并分析運行結(jié)果。</p><p>　?。?）參考文獻：列出參考的相關(guān)資料和書籍。<

15、/p><p>　　本課程設(shè)計以字符序列的形式從鍵盤輸入語法正確的、不含變量的整數(shù)（或?qū)崝?shù)）表達式，實現(xiàn)對算術(shù)四則混合運算表達式的求值。當(dāng)用戶輸入一個合法的算術(shù)表達式后，能夠返回正確的結(jié)果。能夠計算的運算符包括：加、減、乘、除、括號，對于異常表達式能給出錯誤提示。</p><p>　　2.4算法設(shè)計基本要求</p><p>　　掌握棧和隊列的定義、特性；</p>

16、;<p>　　熟練掌握棧的順序表示、鏈表表示以及相應(yīng)操作的實現(xiàn)；</p><p>　?。?） 掌握棧的基本運算，并能正確應(yīng)用它們解決實際問題；</p><p>　　2.4.1算法設(shè)計主要內(nèi)容</p><p>　　算術(shù)表達式由操作數(shù)、運算符和界限符組成。操作數(shù)是正整數(shù)，運算符為加減乘除，界限符有左右括號和表達式起始。</p><p&

17、gt;　　2.4.2算法設(shè)計的思想</p><p>　　已知輸入一個中綴表達式，利用棧（這里用棧的順序存儲結(jié)構(gòu)）的后進先出性，將一個中綴表達式轉(zhuǎn)換成一個后綴表達式，然后同樣利用棧的后進先出性，由后綴表達式求出這個表達式的值，并輸出。</p><p><b>　　2.5 算法描述</b></p><p>　　main ( ) （主函數(shù)）<

18、/p><p>　　在主函數(shù)中建兩個工作棧。一個稱為OPTR，用以寄存運算符；另一個稱作OPND，用以寄存操作數(shù)或運算結(jié)果。</p><p>　　首先置操作數(shù)棧為空棧，表達式起始符“#”為運算符棧的棧底元素；</p><p>　　一次讀入表達式中的每一個字符，若是操作數(shù)則進OPND棧，若是運算符則和OPRT棧的棧頂運算符比較優(yōu)先權(quán)后作相應(yīng)的操作，直至整個表達式求值完畢（即

19、OPRT棧的棧頂元素和當(dāng)前輸入的字符均為“#”）。</p><p><b>　　2.6設(shè)計方案</b></p><p>　　任何一個表達式都是由操作符，運算符組成的。我們分別用順序棧來寄存表達式的操作數(shù)和運算符。棧是限定于緊僅在表尾進行插入或刪除操作的線性表。順序棧的存儲結(jié)構(gòu)是利用一組連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素。</p><p&g

20、t;　　為了實現(xiàn)算符優(yōu)先算法?？梢允褂脙蓚€棧。一個稱為OPF，用以寄存運算符，另一個稱做OPS，用以寄存操作數(shù)或運算結(jié)果。</p><p>　　1.首先置操作數(shù)棧為空棧，表達式起始符”#”為運算符棧的棧底元素；</p><p>　　2.依次讀入表達式，若是操作符即進OPS棧，若是運算符則和OPF棧的棧頂運算符比較優(yōu)先權(quán)后作相應(yīng)的操作，直至整個表達式求值完畢（即OPF棧的棧頂元素和當(dāng)前讀入的

21、字符均為”#”）。</p><p><b>　　2.7設(shè)計內(nèi)容</b></p><p>　　2.7.1．需求分析</p><p>　　本程序所做的工作為：能直接求出四則表達式的值，并輸出；本程序可用于小學(xué)教師對學(xué)生作業(yè)的快速批改以及對數(shù)值位數(shù)要求較大的科學(xué)運算。</p><p>　　2.7.2．概要設(shè)計</p>

22、;<p>　　a.//用于存儲操作數(shù)和運算結(jié)果（OPS）:</p><p>　　ADT LinkStack{</p><p>　　數(shù)據(jù)元素：此鏈棧中的所有元素類型為字符型的數(shù)字字符</p><p>　　數(shù)據(jù)關(guān)系：棧中數(shù)據(jù)元素之間是線性關(guān)系。</p><p><b>　　基本操作:</b></p>

23、<p>　?。?）InitStack(LinkStack &head)</p><p>　　操作結(jié)果：構(gòu)造一個空棧head</p><p>　?。?）IsEmpty(LinkStack head)</p><p>　　初始條件：棧head已存在</p><p>　　操作結(jié)果：若棧為空棧，則返回TRUE,否則FALSE&l

24、t;/p><p>　?。?）Push(LinkStack &head,ElementType element)</p><p>　　初始條件：棧head已存在</p><p>　　操作結(jié)果：插入元素element為新的棧頂元素</p><p>　?。?）Pop(LinkStack &head,ElementType &el

25、ement)</p><p>　　初始條件：棧head已存在且非空</p><p>　　操作結(jié)果：刪除head的棧頂元素，并用e返回其值</p><p>　?。?）GetTop(LinkStack head, ElementType &element)</p><p>　　初始條件：棧head已存在并且非空</p>&l

26、t;p>　　操作結(jié)果：用e返回head的棧頂元素</p><p>　?。?）DestroyStack(LinkStack &head)</p><p>　　初始條件：棧head已存在</p><p>　　操作結(jié)果：棧head 被銷毀</p><p>　　}ADT LinkStack</p><p>　　b

27、．//用于存儲運算符(OPF)：</p><p>　　ADT LinkCharStack{</p><p>　　數(shù)據(jù)對象D：元素類型為字符型的符號字符</p><p><b>　　數(shù)據(jù)關(guān)系R：</b></p><p>　　基本操作：棧中數(shù)據(jù)元素之間是線性關(guān)系。</p><p>　?。?）CInit

28、Stack(LinkCharStack &head) </p><p>　　操作結(jié)果：構(gòu)造一個空棧head</p><p>　?。?）CIsEmpty(LinkCharStack head)</p><p>　　初始條件：棧head已存在</p><p>　　操作結(jié)果：若棧為空棧，則返回TRUE,否則FALSE</p>

29、<p>　?。?）CPush(LinkCharStack &head,ElementType element)</p><p>　　初始條件：棧head已存在</p><p>　　操作結(jié)果：插入元素element為新的棧頂元素</p><p>　?。?）CPop(LinkCharStack &head,ElementType &el

30、ement)</p><p>　　初始條件：棧head已存在且非空</p><p>　　操作結(jié)果：刪除head的棧頂元素，并用e返回其值</p><p>　?。?）CGetTop(LinkCharStack head, ElementType &element)</p><p>　　初始條件：棧head已存在并且非空</p>

31、;<p>　　操作結(jié)果：用e返回head的棧頂元素</p><p>　　（6）CDestroyStack(LinkCharStack &head)</p><p>　　初始條件：棧head已存在</p><p>　　操作結(jié)果：棧head 被銷毀</p><p>　　}ADT LinkCharStack</p>

32、<p>　　c.系統(tǒng)中子程序及功能要求：</p><p>　　if(!In(c[i]))：判斷讀入的字符不是運算符 是則進棧；</p><p>　　char Proceed(char op,char c)： op為棧頂元素，c為當(dāng)前讀入的運算符,比較二者的優(yōu)先級；</p><p>　　int EvalExpres(void)：表達式求解函數(shù)</

33、p><p>　　ElementType EvaluateExpression(char *exp)：這是此程序的核心函數(shù)，可以綜合其它子函數(shù)，實現(xiàn)最終的表達式求解。</p><p>　　各程序模塊之間的調(diào)用關(guān)系（子程序編號見上）：</p><p>　　主函數(shù)可調(diào)用子程序5，6，7。</p><p>　　子程序7可調(diào)用子程序1，2，3，4。 <

34、;/p><p>　　2.7.3 詳細設(shè)計</p><p><b>　　此算法的基本思想：</b></p><p>　　首先置操作數(shù)棧OPS為空棧，表達式起始符“#”為運算符的棧底元素；依次讀入表達式中每個字符，若是操作數(shù)則進棧，若是運算符則和OPF棧的棧頂運算符比較優(yōu)先權(quán)作相應(yīng)操作，直至整個表達式求值完畢（即OPF棧的棧頂元素和當(dāng)前讀入的字符均為“

35、#”）</p><p><b>　　此算法的偽代碼：</b></p><p>　　ElementType EvaluateExpression(char *exp)</p><p>　　{ 定義兩個字符變量c和ch,c代表輸入表達式中的字符，ch代表棧頂運算符;</p><p>　　定義字符指針 *p,*q,*temp

36、;temp指向運算符后面的一個字符</p><p>　　double i=0,a=0,b=0;</p><p>　　將傳入的實參賦給p,q;</p><p>　　定義一個運算符棧 OPF;</p><p>　　定義一個操作數(shù)棧 OPS;</p><p>　　調(diào)用函數(shù)InitStack()初始化棧OPS; </p&

37、gt;<p>　　調(diào)用函數(shù)CInitCharStack()初始化棧OPF;</p><p>　　調(diào)用函數(shù)CPush(OPF,'#')將#壓入運算符棧;</p><p>　　c=*p;temp=p;p++;</p><p>　　if(第一個字符就為‘-’)</p><p><b>　　{</b>

38、;</p><p>　　c=*p;temp=p;p++;</p><p><b>　　}</b></p><p>　　while(棧不為空或表達式?jīng)]有結(jié)束)</p><p>　　{//進入最外層循環(huán)</p><p>　　if(不是運算符)//則解析數(shù)字字符串然后進操作數(shù)棧</p>&

39、lt;p><b>　　{</b></p><p><b>　　整數(shù)部分m=0;</b></p><p><b>　　小數(shù)部分n=0;</b></p><p>　　while(沒有遇到小數(shù)點并且為數(shù)字字符)</p><p>　　{ 解析整數(shù)部分m }</p>

40、<p><b>　　if(遇到小數(shù)點)</b></p><p><b>　　{ 解析小數(shù)部分</b></p><p><b>　　c=*p;</b></p><p>　　將p指針移到第一個出現(xiàn)的字符;</p><p>　　將q指針指向小數(shù)的最后一位;</p

41、><p>　　while(p指針不指向’.’)</p><p><b>　　{</b></p><p>　　將p指向的字符轉(zhuǎn)為小數(shù)n</p><p><b>　　p--;</b></p><p><b>　　}</b></p><p>

42、;<b>　　p=q;</b></p><p><b>　　p++;</b></p><p><b>　　}</b></p><p>　　if(運算符為‘-’并且運算符前一個為‘（’或者為表達式的開始)</p><p>　　調(diào)用Push(OPS,-(m+n))將m+n的相反

43、數(shù)入棧;</p><p><b>　　else </b></p><p>　　調(diào)用Push(OPS,m+n)將m+n入棧;</p><p><b>　　}數(shù)字進棧結(jié)束</b></p><p>　　else//是運算符時則進棧OPF</p><p>　　{ if(運算符為‘-’

44、&&運算符前一個為‘（’)</p><p><b>　　{ c=*p;</b></p><p><b>　　temp=p;</b></p><p><b>　　p++;</b></p><p><b>　　}</b></p>

45、<p><b>　　else</b></p><p>　　{ 調(diào)用函數(shù)CGetTop(OP,ch)得到OPF的棧頂元素;</p><p>　　switch(調(diào)用函數(shù)Precede(ch,c)判斷棧頂元素與接收的字符的優(yōu)生級別)</p><p><b>　　{</b></p><p>　　

46、case 棧頂運算符優(yōu)先權(quán)低:</p><p>　　調(diào)用函數(shù)CPush(OPF,c)將c入運算符棧;</p><p><b>　　接收下一個字符;</b></p><p>　　case 棧頂運算符優(yōu)先權(quán)高：</p><p>　　運算符出棧得到ch;</p><p>　　數(shù)字棧連續(xù)出棧兩次得到a,b

47、 ;</p><p>　　調(diào)用Operate(a,ch,b)并將結(jié)果入棧到數(shù)字棧;break;</p><p>　　case 優(yōu)生權(quán)相等：脫括號并接收下一個字符;</p><p>　　調(diào)用CPop(OPF,ch)脫括號;接收下一個字符;</p><p>　　default:接收下一個字符;</p><p>　　}退出s

48、witch循環(huán)</p><p><b>　　}//else1</b></p><p><b>　　}//else2</b></p><p>　　}//退出最外層while循環(huán)</p><p>　　調(diào)用函數(shù)GetTop(OPS,i)得到棧頂元素i;</p><p><b&

49、gt;　　將兩個棧消毀;</b></p><p>　　}EvaluateExpression函數(shù)結(jié)束</p><p>　　利用該算法對算術(shù)表達式3*(7-2)求值操作過程如下：</p><p><b>　　表一</b></p><p>　　2.7.4 調(diào)試分析與結(jié)果</p><p>

50、<b>　　測試數(shù)據(jù)</b></p><p>　　第一組表達式測試結(jié)果：</p><p>　　圖1 12+（9-8）*7-（6*5）表達式運算結(jié)果</p><p>　　上示結(jié)果說明該程序能計算個位數(shù)組成的表達式。</p><p>　　第二組表達式的測試結(jié)果：</p><p>　　圖2 表達式3*

51、（67-65）+3表達式的運行結(jié)果</p><p>　　上示結(jié)果說明該程序能正常運行計算兩位數(shù)組成的表達式。</p><p>　　第三組表達式的測試結(jié)果：</p><p>　　圖3 表達式4-{2*[10/(2+3)]}的運行結(jié)果</p><p>　　上示結(jié)果說明本程序?qū)τ卸鄬ㄌ柕谋磉_式仍能正常運行。</p><p&g

52、t;　　第四組表達式的測試結(jié)果：</p><p>　　圖4 錯誤表達式12-（（（3-6*7）+8）-4的測試結(jié)果</p><p>　　上示結(jié)果表明當(dāng)我們輸入第五組錯誤的表達式時，程序能做出正確判斷，提醒用戶輸入的表達式錯誤。</p><p>　　2.7.5 算法分析</p><p>　　該算法的時間復(fù)雜度為O（n）</p>

53、<p>　　本算法有運行效率高優(yōu)點，缺點就是需要建兩個棧，所需空間較大。</p><p><b>　　課程總結(jié)</b></p><p>　　轉(zhuǎn)眼，為期兩周的《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計實習(xí)即將結(jié)束了。在這次實習(xí)中，自己的C語言知識和數(shù)據(jù)結(jié)構(gòu)知識得到了鞏固，編程能力也有了一定的提高。同時也學(xué)會了解決問題的方法?？偨Y(jié)起來，自己主要有以下幾點體會：</p>

54、<p>　　1.必須牢固掌握基礎(chǔ)知識。由于C語言是大一所學(xué)知識，有所遺忘，且未掌握好這學(xué)期所學(xué)的《數(shù)據(jù)結(jié)構(gòu)》這門課，所以在實習(xí)之初感到棘手。不知如何下手，但在后來的實習(xí)過程中自己通過看書和課外資料，并請教其他同學(xué)，慢慢地對C語言和數(shù)據(jù)結(jié)構(gòu)知識有所熟悉。這時才逐漸有了思路。所以，這次實習(xí)之后，我告誡自己：今后一定要牢固掌握好專業(yè)基礎(chǔ)知識。</p><p>　　2.必須培養(yǎng)嚴謹?shù)目茖W(xué)態(tài)度。自己在編程時經(jīng)常因

55、為一些類似于“少了分號”的小錯誤而導(dǎo)致錯誤，不夠認真細致，這給自己帶來了許多麻煩。編程是一件十分嚴謹?shù)氖虑?，容不得馬虎。所以在今后自己一定要培養(yǎng)嚴謹?shù)目茖W(xué)態(tài)度。我想這不僅是對于程序設(shè)計，做任何事都應(yīng)如此。</p><p>　　3.這次課程設(shè)計也讓我充分認識到《數(shù)據(jù)結(jié)構(gòu)》這門課的重要性。它給我們一個思想和大綱，讓我們在編程時容易找到思路，不至于無章可循。同時它也有廣泛的實際應(yīng)用。</p><p&

56、gt;　　總之，在這次實習(xí)中，自己的C語言以及數(shù)據(jù)結(jié)構(gòu)知識得到提高，編程能力也得到了提高。</p><p><b>　　參考文獻：</b></p><p>　　[1]譚浩強編著.C++課程設(shè)計.北京：清華大學(xué)社，2004</p><p>　　[2]S.B.Lippman，J.Lajoie著.潘愛民譯.C++Primer（3rd Edition）

57、中文版.北京：中國電力出版社，2002</p><p>　　[3]H.M.Deitel，Paul James Deitel著.薛萬鵬譯.C++程序設(shè)計教程.北京：機械工業(yè)出版社，2000</p><p>　　[4]Stephen R.Savis著.C++ For Dummies 4th edition，IDG Books Worldwide，Inc.，2002</p><

58、;p>　　[5]Harvey M.Deitel .Jack W.Davidson著.邱仲潘譯.C++大學(xué)教程（第二版）.北京：電子工業(yè)出版社，2002</p><p>　　[6]James P.Cohoon.Jack W.Davidson著.劉瑞挺等譯.C++程序設(shè)計（第三版）.北京：電子工業(yè)出版社</p><p>　　[7]Decoder編著.C/C++程序設(shè)計.北京：中國鐵道出版

59、社，2002</p><p>　　[8]Brian Overland著.董梁等譯.C++語言命令譯解（第二版）.北京：機械工業(yè)出版社，2002</p><p>　　[9] H.M.Deitel，Paul James Deitel著.薛萬鵬譯.C/C++程序設(shè)計大全.北京：機械工業(yè)出版社.1997</p><p>　　[10]Al Strevens,Clayton W

60、alnum著.林麗閩等譯.標(biāo)準(zhǔn)C++寶典.北京：電子工業(yè)出版社.2001</p><p>　　[11]Michael J.Young著.Mastering Visual C++6.0 Sybex Inc.1999</p><p>　　[12]Leen Ammeraal著.劉瑞挺等譯.C++程序設(shè)計教程（第三版）.北京：zhongguo 鐵道出版社，2003</p><p

61、>　　[13] 呂鳳翥著. C++語言程序設(shè)計.北方交通大學(xué)出版社，2003</p><p>　　[14] 袁啟昌著.C++語言程序設(shè)計.清華大學(xué)出版社，2004</p><p>　　[15] 劉振安，劉燕君，孫忱C++語言課程設(shè)計.機械工業(yè)出版社，2007</p><p>　　[16] 楊進才，沈顯君，劉蓉編.C++語言程序設(shè)計教程.清華大學(xué)出版社，2006

62、</p><p>　　[17] 宋振會著. C++語言編程基礎(chǔ)教程.清華大學(xué)出版社，2005</p><p><b>　　附錄：</b></p><p><b>　　源代碼：</b></p><p>　　#include <stdio.h></p><p>　　#

63、define MAXSIZE 16</p><p>　　typedef struct{</p><p>　　int data[MAXSIZE];</p><p><b>　　int top;</b></p><p><b>　　int base;</b></p><p&g

64、t;　　}seqstack; /* 順序棧的定義*/</p><p>　　/*以下為函數(shù)聲明*/</p><p>　　void InitStack(seqstack *); </p><p>　　int Empty(seqstack *);</p><p>　　void Push(seqstack *, int );&

65、lt;/p><p>　　int Pop(seqstack *);</p><p>　　int GetTop(seqstack *);</p><p>　　int Operate(int ,char ,int );</p><p>　　char Proceed(char ,char );</p><p>　　int

66、 In(char );</p><p>　　int EvalExpres(void);</p><p>　　/* 定義兩個棧分別存放運算符和操作數(shù)*/</p><p>　　seqstack StackR,StackD; </p><p><b>　　/*主函數(shù)*/</b></p><p>　　i

67、nt main()</p><p><b>　　{</b></p><p><b>　　int v;</b></p><p><b>　　char ch;</b></p><p><b>　　while(1)</b></p><p>

68、;<b>　　{</b></p><p>　　printf("\t本程序的功能為：用順序棧實現(xiàn)整型算術(shù)表達式的求值\n");</p><p>　　v = EvalExpres(); </p><p>　　printf("The result is:%d",v);</p><

69、;p>　　/*以下為程序控制*/ </p><p>　　printf("\nInput 'q' to quit and ENTER run again:"); </p><p><b>　　do{ </b></p><p>　　scanf("%c",&ch);

70、 </p><p>　　if(ch == 'q' || ch == 'Q')</p><p><b>　　exit(0);</b></p><p>　　}while(ch!='\n');</p><p>　　system("cls"); <

71、/p><p><b>　　}</b></p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　void InitStack(seqstack *s)</p><p>　　{ s->t

72、op = 0;</p><p>　　s->base = 0;</p><p>　　} /* 初始化棧*/</p><p>　　int Empty(seqstack *s)</p><p>　　{ if(s->top == s->base)</p><p><b>　　return

73、 1;</b></p><p><b>　　else</b></p><p><b>　　return 0;</b></p><p>　　} /* 判斷棧是否為空*/</p><p>　　void Push(seqstack *s, int x)</p><p&

74、gt;<b>　　{ </b></p><p>　　if(s->top == MAXSIZE)</p><p>　　{ printf("OVER FLOW!\n");</p><p><b>　　exit(0);</b></p><p><b>　　}&

75、lt;/b></p><p><b>　　else</b></p><p>　　{ s->data[s->top] = x;</p><p><b>　　s->top++;</b></p><p><b>　　} </b></p>

76、<p>　　} /* 進棧 */</p><p>　　int Pop(seqstack *s)</p><p>　　{ int e;</p><p>　　if(Empty(s))</p><p>　　{ printf("Under flow!\n");</p><p&g

77、t;<b>　　return 0;</b></p><p>　　} /* 下溢*/</p><p><b>　　else </b></p><p>　　{ s->top--;</p><p>　　e = s->data[s->top];</p><p&

78、gt;<b>　　return e;</b></p><p><b>　　}</b></p><p>　　} /* 出棧*/</p><p>　　int GetTop(seqstack *s) /*取棧頂元素*/</p><p><b>　　{ </b></p

79、><p>　　if(Empty(s))</p><p>　　{ printf("Under flow!\n");</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p><b>　　else

80、</b></p><p>　　return s->data[s->top-1]; </p><p><b>　　}</b></p><p>　　int EvalExpres(void) /* 表達式求解函數(shù)*/</p><p><b>　　{</b></

81、p><p>　　int a,b,i=0,s=0;</p><p>　　char c[80],r;</p><p>　　InitStack(&StackR);</p><p>　　Push(&StackR,'#');</p><p>　　InitStack(&StackD);</

82、p><p>　　printf(" 請輸入表達式并以‘#’結(jié)束：");</p><p><b>　　gets(c);</b></p><p>　　while(c[i]!='#' || GetTop(&StackR)!='#')</p><p><b>　　{

83、 </b></p><p>　　if(!In(c[i])) /* 判斷讀入的字符不是運算符 是則進棧*/</p><p>　　{ if(c[i] >= '0' && c[i] <= '9')</p><p><b>　　{</b></p><

84、;p>　　s += c[i]-'0'; </p><p>　　while(!In(c[++i])) /*此處實現(xiàn)的功能為當(dāng)輸入的數(shù)字為多位數(shù)時*/</p><p><b>　　{ s*=10;</b></p><p>　　s += c[i]-'0';</p><p>

85、<b>　　}</b></p><p>　　Push(&StackD,s+'0'); </p><p><b>　　s = 0;</b></p><p><b>　　}</b></p><p><b>　　else </b><

86、/p><p><b>　　{</b></p><p>　　printf("你輸入的表達式有誤!\n");</p><p>　　return 0; </p><p>　　} </p><p><b>　　} </b></p>&

87、lt;p>　　else </p><p>　　switch(Proceed(GetTop(&StackR),c[i])) /* 此函數(shù)用來比較讀取的運算符和棧頂運算符的優(yōu)先級*/</p><p><b>　　{</b></p><p>　　case '<': /* 棧頂?shù)脑貎?yōu)先級高*/&

88、lt;/p><p>　　Push(&StackR,c[i]);</p><p><b>　　i++;</b></p><p><b>　　break;</b></p><p>　　case '=': /* 遇到匹配的小括號時則去掉他*/</p><p>

89、;　　Pop(&StackR);</p><p><b>　　i++;</b></p><p><b>　　break;</b></p><p>　　case '>': /* 棧頂?shù)膬?yōu)先級低則出棧并將結(jié)果寫入棧內(nèi)*/</p><p>　　r = Pop(&St

90、ackR);</p><p>　　a = Pop(&StackD)-'0';</p><p>　　b = Pop(&StackD)-'0';</p><p>　　Push(&StackD,Operate(a,r,b)) ;</p><p>　　break; &

91、lt;/p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　return (GetTop(&StackD)-'0'); /* 返回運算結(jié)果*/</p><p><b>　　}</b></p>&

92、lt;p>　　int In(char c) /*問題2：解決In函數(shù)問題:判斷C是否為運算符是返回1否則返回0*/</p><p><b>　　{</b></p><p>　　char ch[7]={'+','-','*','/','#','(',&

93、#39;)'};</p><p><b>　　int i;</b></p><p>　　for(i = 0; i < 7; i++)</p><p>　　if(c == ch[i])</p><p><b>　　return 1;</b></p><p>　　r

94、eturn 0; </p><p><b>　　}</b></p><p>　　char Proceed(char op,char c) /*op為棧頂元素，c為當(dāng)前讀入的運算符,比較二者的優(yōu)先級*/</p><p>　　{

95、 /*問題1：解決Proceed函數(shù)*/</p><p>　　char ch; </p><p>　　if(op=='(' && c==')' || op=='#' && c=='#' )</p><p><b>　　ch = '

96、;=';</b></p><p><b>　　else</b></p><p>　　if(op=='+' || op=='-') /*棧頂元素為‘+’或‘-’的時候*/</p><p><b>　　switch(c)</b></p><p>

97、;<b>　　{</b></p><p><b>　　case '+':</b></p><p><b>　　case '-':</b></p><p><b>　　case ')':</b></p><p>

98、;　　case '#': ch = '>'; break;</p><p><b>　　case '*':</b></p><p><b>　　case '/':</b></p><p>　　case '(': ch = '&

99、lt;';</p><p><b>　　}</b></p><p><b>　　else</b></p><p>　　if(op=='*' || op=='/') /*棧頂元素為‘*’或‘/’的時候*/</p><p><b>　　switch

100、(c)</b></p><p><b>　　{</b></p><p><b>　　case '+':</b></p><p><b>　　case '-':</b></p><p><b>　　case '*

101、9;:</b></p><p>　　case '/': </p><p><b>　　case ')':</b></p><p>　　case '#': ch = '>'; break;</p><p>　　case '

102、(': ch = '<'; </p><p><b>　　}</b></p><p><b>　　else</b></p><p>　　if(op=='(') /*棧頂元素為‘(’的時候*/</p><p><b>

103、;　　switch(c)</b></p><p><b>　　{</b></p><p><b>　　case '+':</b></p><p><b>　　case '-':</b></p><p><b>　　case

104、'*':</b></p><p><b>　　case '/':</b></p><p>　　case '(': ch = '<'; break; </p><p>　　case '#': printf("Error!\n"

105、;); exit(0);</p><p><b>　　}</b></p><p><b>　　else</b></p><p>　　if(op==')') /*棧頂元素為‘)’的時候*/</p><p><b>　　switch(c)</b></

106、p><p><b>　　{</b></p><p><b>　　case '+':</b></p><p><b>　　case '-':</b></p><p><b>　　case '*':</b></

107、p><p><b>　　case '/':</b></p><p>　　case '#': ch = '>'; break; </p><p>　　case '(': printf("Error!\n"); exit(0);</p><

108、;p><b>　　}</b></p><p><b>　　else</b></p><p>　　if(op=='#') /*棧頂元素為‘#’的時候*/</p><p><b>　　switch(c)</b></p><p><

109、;b>　　{</b></p><p><b>　　case '+':</b></p><p><b>　　case '-':</b></p><p><b>　　case '*':</b></p><p><

110、;b>　　case '/':</b></p><p>　　case '(': ch = '<'; break; </p><p>　　case ')': printf("Error!\n"); exit(0);</p><p><b>　　}

111、</b></p><p>　　return ch; </p><p>　　} </p><p>　　/* 問題3：解決Operate函數(shù)*/</p><p>　　int Operate(int a,char r,int b) /*返回由aRb的值

112、 */</p><p><b>　　{ </b></p><p><b>　　int s;</b></p><p>　　int d1 = a;</p><p>　　int d2 = b; /*把字符ab變?yōu)閷?yīng)數(shù)字*/</p><p><b>　　switch(r

113、)</b></p><p><b>　　{</b></p><p>　　case '+': s = d1+d2; break;</p><p>　　case '-': s = d2-d1; break;</p><p>　　case '*': s = d1