論中綴表達式與后綴表達式的轉換

摘 要：為了處理方便，編譯程序常把中綴表達式首先轉換成等價的后綴表達式。介紹如何使用順序棧這樣一種數據結構實現中綴表達式向后綴表達式的轉換。

關鍵詞：堆棧；中綴表達式；后綴表達式

中圖分類號：G40文獻標識碼：A文章編號：1672-3198（2008）06-0258-02

1 中綴表達式求值

首先我們來看一下什么叫作中綴表達式？所謂中綴表達式是指：每個二目運算符在兩個運算量的中間。例如：a+b。

這里假設所討論的算術運算符包括：+ 、－、*、/和括號（）。根據算術四則運算的規則：先乘除后加減、先括號內再括號外、同級別時先左后右，可以得出運算符的優先級為：（）→*、/ →+、－。如：a+b×c－(d+e)。我們根據優先級，計算出d+e的值x，再計算出b×c的值y，然后從左到右計算a+x－y。

它的的求值過程為：自左向右掃描表達式，當掃描到a+b時不能馬上計算，因為后面可能還有更高的運算。我們可以用兩個棧來處理這樣的問題：對象棧s1和算符棧s2。當自左至右掃描表達式的每一個字符時，若當前字符是運算對象，入對象棧，是運算符時，若這個運算符比棧頂運算符高則入棧，繼續向后處理，若這個運算符比棧頂運算符低則從對象棧出棧兩個運算量，從算符棧出棧一個運算符進行運算，并將其運算結果入對象棧，繼續處理當前字符，直到遇到結束符。

2 后綴表達式求值

所謂后綴表達式，是指運算符在運算對象之后。在后綴表達式中，不再引入括號，所有的計算按運算符出現的順序，嚴格從左向右進行，而不用再考慮運算規則和級別。例如：abcd/-e*+。從左向右，首先計算/，即c/d的值x，然后計算b-x的值y，再計算y*e的值z，最后計算a+z。

計算一個后綴表達式，算法上比計算一個中綴表達式簡單的多。這是因為表達式中即無括號又無優先級的約束。具體做法：只使用一個對象棧，當從左向右掃描表達式時，每遇到一個操作數就送入棧中保存，每遇到一個運算符就從棧中取出兩個操作數進行當前的計算，然后把結果再入棧，直到整個表達式結束，這時送入棧頂的值就是結果。

3 中綴表達式轉換成后綴表達式

為了處理方便，編譯程序常把中綴表達式首先轉換成等價的后綴表達式。

例如：一個中綴表達式：a+（b-c/d）*e

其相應的后綴表達式為：abcd/-e*+

我們可以用棧這樣一種數據結構實現中綴表達式向后綴表達式的轉換，具體步驟如下：

（1）設置一個堆棧，將棧頂預設置為‘＃’；

（2）順序讀入中綴表達式。當讀到的單詞為操作數時將其輸出，并接著讀入下一個單詞；當讀入的單詞為運算符時就賦給x2，比較x2與棧頂運算符x1的優先級：

①若x2的優先級高于x1，將x2進棧，繼續讀入下一個單詞；

②若x2的優先級低于x1，x1退棧并作為后綴表達式的一個單詞輸出，然后比較x2與新的棧頂運算符x1；

③若x2的優先級等于x1，且x1為'（'，x2為'）'，則x1出棧，然后繼續讀下一個單詞；

④若x2的優先級等于x1的，且x1為'＃'，x2也為'＃'，則算法結束。

假設中綴表達式存在字符串expression中，且堆棧采用順序棧，進出棧算法分別為PushQstuck（）和PopQstuck（），則中綴表達式變后綴表達式的算法為：

int postfix(qstype *s，char *expression) /*中綴表達式變后綴表達式*/

{

char x1，x2，x;

int j=0;

s->stack［0］='#';

s->top=0;

x2=expression［j］;

if((x1=gettopqstack(s))==nil) /* gettopqstack（）函數取棧頂元素*/

exit(0);

while(1)

{

if(x2!='+'x2!='-'x2!='*'x2!='/'x2!='('x2!=')'x2!='#')

{

cout<

x2=expression［++j］;

}

else if(proceed(x1，x2)=='<')/* proceed（）函數比較字符x1和x2的優先級*/

{

if(!pushqstack(s，x2))

exit(0);

if((x1=gettopqstack(s))==nil)

exit(0);

x2=expression［++j］;

}

else if(proceed(x1，x2)=='>')

{

if((x=popqstack(s))==nil)

exit(0);

cout<

if((x1=gettopqstack(s))==nil)

exit(0);

}

else if(proceed(x1，x2)=='='x1=='('x2==')')

{

if(popqstack(s)==nil)

exit(0);

if((x1=gettopqstack(s))==nil)

exit(0);

x2=expression［++j］;

}

else if(proceed(x1，x2)=='='x1=='#'x2=='#')return 1;

else if(proceed(x1，x2)==' ') break;

}

cout<<\"error\";

return 0;

}

若表達式expression為a+（b-c/d）*e則我們通過下表可以看出轉換的過程：

4 總結

為了處理方便，編譯程序常把中綴表達式首先轉換成等價的后綴表達式。棧是限制僅在表的一端進行插入和刪除運算的線性表，通常稱插入、刪除的這一端為棧頂（Top），另一端稱為棧底（Bottom）。棧的修改是按后進先出的原則進行的。利用棧的這一特點，我們利用順序棧這樣一種數據結構來實現中綴表達式轉換成后綴表達式是完全可行的。

參考文獻

［1］ 嚴蔚敏.數據結構［M］.北京：清華大學出版社.

［2］蔣文蓉.數據結構［M］.北京：高等教育出版社.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”