c++課程設(shè)計---中綴表達式轉(zhuǎn)后綴表達式的實現(xiàn)

1、<p>　　《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計報告書</p><p>　　題目名稱: 中綴表達式轉(zhuǎn)后綴表達式的實現(xiàn) </p><p>　　1.設(shè)計的內(nèi)容與目的</p><p>　　計算機對于用戶所輸入的數(shù)據(jù)只能夠逐個字符編碼為二進制，并作為字符串表存，并不能夠判斷其整體意義，是否為算術(shù)表達式還是物理公式之類，因此，需要程序來解釋從而進行合理的處理。假定

2、我們要計算表達式10+（8-4）*3/4-6的值，這種書寫格式就是中綴表達式（運算符在兩個操作數(shù)之間），然而計算機在計算這個表達式值的時候會遇到相當(dāng)?shù)穆闊?，原因在于判斷計算?yōu)先級困難。然而在后綴表達式中，取消了括號，也不存在優(yōu)先級問題，計算過程完全按照運算符出現(xiàn)的先后次序進行，整個計算過程僅需一遍掃描就可完成，比中綴表達式的計算要簡單的得多。因此本次課程設(shè)計的內(nèi)容就是實現(xiàn)中綴表達式到后綴表達式的轉(zhuǎn)換。而本次課程設(shè)計的目的不僅僅在于實現(xiàn)中

3、后表達式的轉(zhuǎn)化以簡化計算機的工作，而且能加強我能對數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)與理解，特別是對堆棧的學(xué)習(xí)，理解甚至應(yīng)用。為我們將理論應(yīng)用于實際打下堅實的基礎(chǔ)。</p><p><b>　　2.數(shù)據(jù)結(jié)構(gòu)設(shè)計</b></p><p><b>　　創(chuàng)建順序堆棧類；</b></p><p>　　class SeqStack //順

4、序堆棧類的定義</p><p><b>　　{</b></p><p><b>　　private:</b></p><p>　　DataType data[MaxStackSize];</p><p><b>　　int top;</b></p><p&g

5、t;<b>　　public:</b></p><p>　　SeqStack(void) //順序堆棧構(gòu)造函數(shù)</p><p><b>　　{top=0;};</b></p><p>　　~SeqStack(void){}; //順序堆棧析構(gòu)函數(shù)</p><

6、;p>　　void Push(const DataType item); //入棧</p><p>　　DataType Pop(void);//出棧</p><p>　　DataType GetTop(void)const; //取棧頂元素</p><p>　　int NotEmpty(void)const//堆棧非空否</p><

7、;p>　　{return(top!=0);};</p><p><b>　　};</b></p><p><b>　　順序堆棧的實現(xiàn)；</b></p><p>　　void SeqStack::Push(const DataType item) //入棧的實現(xiàn)</p><p><b>

8、;　　{</b></p><p>　　if(top==MaxStackSize)</p><p><b>　　{</b></p><p>　　cout<<"堆棧已滿!"<<endl;</p><p><b>　　exit(0);</b><

9、/p><p><b>　　}</b></p><p>　　data[top]=item;</p><p><b>　　top++;</b></p><p><b>　　}</b></p><p>　　DataType SeqStack::Pop()

10、 //出棧的實現(xiàn)</p><p><b>　　{</b></p><p>　　if(top==0)</p><p><b>　　{</b></p><p>　　cout<<"堆棧已空!"<<endl;</p><p><

11、;b>　　exit(0);</b></p><p><b>　　}</b></p><p><b>　　top--;</b></p><p>　　return data[top];</p><p><b>　　}</b></p><p>

12、;　　DataType SeqStack::GetTop(void)const //取棧頂元素的實現(xiàn)</p><p><b>　　{</b></p><p>　　if(top==0)</p><p><b>　　{</b></p><p>　　cout<<"堆棧空!"

13、;<<endl;</p><p><b>　　exit(0);</b></p><p><b>　　}</b></p><p>　　return data[top-1];</p><p><b>　　}</b></p><p><b&g

14、t;　　3.核心算法</b></p><p>　?。?）建立順序堆棧op；</p><p>　　const int MaxStackSize=100;</p><p>　　typedef char DataType;</p><p>　　#include"SeqStack.h"</p><p

15、>　　void main()</p><p><b>　　{</b></p><p>　　SeqStack op; //堆棧op存放后綴</p><p>　　op.Push('#'); //將棧頂置為#</p><p><b>　　}</b></p>&

16、lt;p>　?。?）構(gòu)造運算符優(yōu)先級比較函數(shù)；</p><p>　　int change(char x1,char x2) //運算符優(yōu)先級比較函數(shù)</p><p><b>　　{</b></p><p><b>　　int ret;</b></p><p>　　if((x1==

17、'+'||x1=='-')&&(x2=='+'||x2=='-'||x2==')'||x2=='#'))</p><p><b>　　ret=1;</b></p><p>　　else if((x1=='+'||x1=='-'

18、)&&(x2=='*'||x2=='/'||x2==')'||x2=='('))</p><p><b>　　ret=0;</b></p><p>　　else if((x1=='*'||x1=='/')&&(x2=='+'|

19、|x2=='-'||x2=='*'||x2=='/'||x2==')'||x2=='#'))</p><p><b>　　ret=1;</b></p><p>　　else if((x1=='*'||x1=='/')&&(x2=='(

20、'))</p><p><b>　　ret=0;</b></p><p>　　else if((x1=='('||x1=='#')&&(x2=='+'||x2=='-'||x2=='*'||x2=='/'||x2=='('))<

21、/p><p><b>　　ret=0;</b></p><p>　　return ret;</p><p><b>　　}</b></p><p><b>　　輸入中綴表達式；</b></p><p>　　cout<<"請輸入中綴表達式

22、以#結(jié)尾！"<<endl; //輸出提示“輸入中綴以#結(jié)尾</p><p>　　char s[50]; //定義一個字符串，長度最長為50</p><p>　　cin.getline(s,50); //以字符串形式輸入中綴表達式</p><p>

23、　　中綴表達式的讀入與轉(zhuǎn)化；</p><p>　　順序讀入中綴表達式：</p><p><b>　　int j=0;</b></p><p>　　for(int j=0;j<=50;j++) //順序讀入中綴表達式</p><p>　　如果讀到字母，數(shù)字將其入棧：</p><p>　　i

24、f((s[j]>='A' && s[j]<='Z')||(s[j]>='0' && s[j]<='9')||(s[j]>='a' && s[j]<='z'))</p><p><b>　　{</b></p&g

25、t;<p>　　cout<<s[j]; //作為后綴表達式輸出</p><p><b>　　}</b></p><p>　　若讀到運算符且不為’)’時，則比較運算符與當(dāng)前棧頂運算符的優(yōu)先級，若當(dāng)前運算符優(yōu)先級大于棧頂運算符優(yōu)先級，則將當(dāng)前運算符入棧：</p><p>　　else

26、 //else表示讀到運算符，</p><p><b>　　{</b></p><p>　　if(s[j]!=')') //當(dāng)前運算符不為’)’時</p><p><b>　　{</b></p><p>　　if(change(op.GetTop(),s[j])==0) /

27、/比較運算符優(yōu)先級</p><p>　　op.Push(s[j]); </p><p>　　若當(dāng)前運算符優(yōu)先級小于棧頂運算符優(yōu)先級，則將棧頂運算符退棧并作為后綴表達式的一部分輸出，然后將當(dāng)前運算符入棧：</p><p>　　else if(change(op.GetTop(),s[j])==1) //比較運算符優(yōu)先級</p>

28、<p><b>　　{</b></p><p>　　cout<<op.GetTop(); //作為后綴表達式輸出</p><p><b>　　op.Pop();</b></p><p>　　op.Push(s[j]);</p><p><b>　　}</b&

29、gt;</p><p>　　若讀到的當(dāng)前運算符為’)’時，則不斷地將棧頂運算符出棧，直到棧頂運算符為’(‘時結(jié)束，并將’(‘出棧：</p><p>　　if(s[j]==')')</p><p><b>　　{</b></p><p>　　while(op.GetTop()!='(')

30、 //循環(huán)結(jié)束條件，當(dāng)前運算符為’(‘</p><p><b>　　{</b></p><p>　　cout<<op.GetTop(); //作為后綴表達式輸出</p><p>　　op.Pop(); //出棧</p><p><b>　　}</b></p>

31、;<p>　　if(op.GetTop()=='(') //當(dāng)棧頂為’(‘時，將其出棧</p><p>　　op.Pop(); //出棧</p><p><b>　　}</b></p><p>　　若讀到的當(dāng)前運算符為’#’時，判斷堆棧非空否，若不為空，則將當(dāng)前棧頂出棧并作為后綴表達式的一

32、個字符輸出，當(dāng)棧頂運算符為’#”時，結(jié)束算法：</p><p>　　if(s[j]=='#')</p><p><b>　　{</b></p><p>　　op.Pop(); //循環(huán)一次需將當(dāng)前棧頂出棧一次</p><p>　　while(op.GetTop()!='#') //判

33、斷是否為’#’</p><p><b>　　{</b></p><p>　　cout<<op.GetTop(); //輸出后綴的一個字符</p><p>　　op.Pop(); //出棧</p><p><b>　　}</b></p><p>&

34、lt;b>　　}</b></p><p>　?。?）完成以上步驟后，j++繼續(xù)第（4）步。</p><p><b>　　4.運行過程與結(jié)果</b></p><p><b>　　初始：</b></p><p><b>　　輸入：</b></p>&