中綴及后綴算術(shù)表達(dá)式在運(yùn)算中的應(yīng)用研究

摘要:表達(dá)式求值是程序設(shè)計語言編譯中的一個最基本問題。與人們習(xí)慣的中綴表示的表達(dá)式相比，后綴表達(dá)式不存在括號，沒有優(yōu)先級的差別，表達(dá)式中各個運(yùn)算是按照運(yùn)算符出現(xiàn)的順序進(jìn)行的。因此非常適合串行工作的計算機(jī)處理方式。該文首先對這兩種表達(dá)式表示方法進(jìn)行了分析比較，然后通過具體分析實(shí)現(xiàn)這兩種表達(dá)式求值的算法來論證表達(dá)式后綴表示優(yōu)于中綴表示。最后簡要談一下中綴表達(dá)式到后綴表達(dá)式的轉(zhuǎn)換。

關(guān)鍵詞:中綴表達(dá)式;后綴表達(dá)式;算符優(yōu)先;堆棧

中圖分類號:TP31文獻(xiàn)標(biāo)識碼:A文章編號:1009-3044(2009)32-8921-03

A Study of Index and Suffix Arithmetic Expression in the Operation Applied Research

GUO Meng-meng， XU Yong-chang

(Shandong Yingcai College， Jinan 250104， China)

Abstract: The expression evaluation is the most basic question in programming language translation. Compared with infix expression with which people are familiar， suffix expression does not have the parenthesis， nor does it have the priority difference; each operation is carried out according to the order in which the operator appears. Therefore it is suitable for the serial work of the computer processing mode. This article first analyses and compares these two kinds of expression， then attempts to prove that suffix expression is superior to infix expression through the concrete analysis of the realization of evaluation algorithm of these two kinds of expression. Finally it discusses briefly the transformation of infix expression into the suffix expression.

Key words: infix expression; suffix expression; priority operator; stack

表達(dá)式求值是程序設(shè)計語言編譯中的一個最基本問題。通常書寫的算術(shù)表達(dá)式是由操作數(shù)和運(yùn)算符以及改變運(yùn)算次序的圓括號連接而成的式子。運(yùn)算符包括單目運(yùn)算符和雙目運(yùn)算符兩類，單目運(yùn)算符只要求一個操作數(shù)，并被置于該操作數(shù)的前面，雙目運(yùn)算符要求有兩個操作數(shù)，其位置因表示方法不同而有所差異。按照運(yùn)算符與運(yùn)算對象的位置關(guān)系，算術(shù)表達(dá)式的表示方法分為前綴表達(dá)式、中綴表達(dá)式和后綴表達(dá)式三種，其中后兩者較為常用。為了簡便起見，在本文的討論中只考慮雙目運(yùn)算符(僅+、-、*、/四種)以及括號。

1 分析

中綴算術(shù)表達(dá)式最為常見，其雙目運(yùn)算符置于與之相關(guān)的兩個運(yùn)算對象之間。對中綴表達(dá)式的求值，并非按照運(yùn)算符出現(xiàn)的自然順序來執(zhí)行其中的各個運(yùn)算，而是根據(jù)算符間的優(yōu)先關(guān)系來確定運(yùn)算的次序，此外，還需要顧及括號規(guī)則。中綴表達(dá)式的計算比較復(fù)雜，它必須遵守以下三條規(guī)則:

1) 先計算括號內(nèi)，后計算括號外;

2) 在無括號或同層括號內(nèi)，先乘除運(yùn)算，后加減運(yùn)算，即乘除運(yùn)算的優(yōu)先級高于加減運(yùn)算的優(yōu)先級;

3) 同一優(yōu)先級運(yùn)算，從左向右依次進(jìn)行。

從以上規(guī)則可以看出，在中綴表達(dá)式的計算過程中，既要考慮括號的作用，又要考慮運(yùn)算符的優(yōu)先級，還要考慮運(yùn)算符出現(xiàn)的先后次序。因此，各運(yùn)算符實(shí)際的運(yùn)算次序往往同它們在表達(dá)式中出現(xiàn)的先后次序是不一致的，是不可預(yù)測的。中綴算術(shù)表達(dá)式符合人的思維方式，我們憑直觀判別一個中綴表達(dá)式中運(yùn)算符運(yùn)算順序并不困難，但對于計算機(jī)處理起來就比較復(fù)雜了。由于傳統(tǒng)計算機(jī)一維的計算模型，只能一個字符一個字符地掃描，要想確定哪一個運(yùn)算符優(yōu)先計算，就必須對整個中綴表達(dá)式掃描一遍，一個中綴表達(dá)式中有多少個運(yùn)算符，原則上就需要掃描多少遍才能計算完畢，這樣算法的時間復(fù)雜性就差了，顯然是不可取的。

那么，能否把中綴算術(shù)表達(dá)式轉(zhuǎn)換成另一種形式的算術(shù)表達(dá)式，使計算簡單化呢? 回答是肯定的。波蘭科學(xué)家盧卡謝維奇(J.Lukasiewicz)很早就提出了算術(shù)表達(dá)式的另一種表示，即后綴表示，又稱逆波蘭式，其定義是把運(yùn)算符放在兩個運(yùn)算對象的后面。采用后綴表示的算術(shù)表達(dá)式被稱為后綴算術(shù)表達(dá)式或后綴表達(dá)式。在后綴表達(dá)式中，不存在括號，也不存在優(yōu)先級的差別，計算過程完全按照運(yùn)算符出現(xiàn)的先后次序進(jìn)行，整個計算過程僅需掃描一遍表達(dá)式便可完成，顯然比中綴表達(dá)式的計算要簡單得多。例如，對于后綴表達(dá)式“12◆4◆–◆5◆/”，其中‘◆’字符表示成分之間的空格，因減法運(yùn)算符在前，除法運(yùn)算符在后，所以應(yīng)先做減法，后做除法;減法的兩個操作數(shù)是它前面的12和4，其中第一個數(shù)12是被減數(shù)，第二個數(shù)4是減數(shù);除法的兩個操作數(shù)是它前面的12減4的差(即8)和5，其中8是被除數(shù)，5是除數(shù)。

那么中綴算術(shù)表達(dá)式轉(zhuǎn)換成對應(yīng)的后綴算術(shù)表達(dá)式的基本思想是什么呢?其實(shí)很簡單，就是把每個運(yùn)算符都移到它的兩個運(yùn)算對象之后，而后刪除掉所有的括號即可。

實(shí)際上J.Lukasiewicz最先提出的是表達(dá)式的前綴表示方法，即把每一個運(yùn)算符置于運(yùn)算對象之前，例如表達(dá)式“10+(20-5*3)/(13-8)”其前綴表示形式為“+ 10 / - 20 * 5 3 -13 8”。前綴表達(dá)式的優(yōu)點(diǎn)與后綴表達(dá)式的相同，也不含有括號，表達(dá)式中的運(yùn)算也是按照運(yùn)算符出現(xiàn)的順序進(jìn)行的，計算也很容易實(shí)現(xiàn)。但由于其表示方法與人們的習(xí)慣相差甚遠(yuǎn)，因而并不常用。

對于簡單的中綴表達(dá)式我們很容易得到其后綴表達(dá)式，但對于較為復(fù)雜的中綴表達(dá)式就很難從直觀上得到其后綴表達(dá)式。

我們可以用一棵二叉樹來表示算術(shù)表達(dá)式，非終端結(jié)點(diǎn)表示運(yùn)算符，終端(葉子)結(jié)點(diǎn)代表運(yùn)算對象，如10+(20-5*3)/(13-8)，那么按照先序、中序、后序遍歷二叉樹，就可以分別得到前綴、中綴和后綴算術(shù)表達(dá)式。如此可以很方便地實(shí)現(xiàn)三種算術(shù)表達(dá)式的相互轉(zhuǎn)換。

用計算機(jī)又是怎樣實(shí)現(xiàn)它們之間的轉(zhuǎn)化的呢?以下是自然語言描述的表達(dá)式轉(zhuǎn)前綴算法:

1) 求輸入串的逆序。

2) 檢查輸入的下一元素。

3) 假若是操作數(shù)，把它添加到輸出串中。繼續(xù)輸入下一個字符。

4) 假若是閉括號(‘)’)，將其入棧。繼續(xù)輸入下一個字符。

5) 假如是運(yùn)算符，則

① 假如棧空，此運(yùn)算符入棧。繼續(xù)輸入下一個字符。

② 假如棧頂是閉括號，此運(yùn)算符入棧。繼續(xù)輸入下一個字符。

③ 假如它的優(yōu)先級高于或等于棧頂運(yùn)算符，此運(yùn)算符入棧。繼續(xù)輸入下一個字符。

④ 否則，棧頂運(yùn)算符出棧并添加到輸出串中，重復(fù)步驟5)。

6) 假如是開括號(‘(’)，棧中運(yùn)算符逐個出棧并輸出，直到遇到閉括號。閉括號出棧并丟棄。繼續(xù)輸入下一個字符。

7) 假如輸入還未完畢，跳轉(zhuǎn)到步驟2)。

8) 假如輸入完畢，棧中剩余的所有操作符出棧并加到輸出串中。

9) 求輸出串的逆序。

假設(shè)我們要將表達(dá)式“2*3/(2-1)+5*(4-1)”轉(zhuǎn)換成前綴形式，原表達(dá)式的逆序是“)1-4(*5+)1-2(/3*2”，輸出串的逆序?yàn)椤?/*23-21*5-41”，所以，最終求得的前綴表達(dá)式是“+/*23-21*5-41”。

2 實(shí)現(xiàn)

在計算機(jī)中進(jìn)行算術(shù)表達(dá)式的求值是通過堆棧來實(shí)現(xiàn)的。后綴表達(dá)式由于其本身所具有的優(yōu)點(diǎn)，表達(dá)式中各個運(yùn)算是按照運(yùn)算符出現(xiàn)的順序進(jìn)行的，其計算求值比較簡單，掃描一遍即可完成。它只需要使用一個棧，用來存儲后綴表達(dá)式中的操作數(shù)、計算過程中的中間數(shù)據(jù)以及最后結(jié)果。

而具體的求值比較簡單，掃描一遍即可完成。它需要使用一個棧，假定用S表示，其元素類型應(yīng)為操作數(shù)的類型，假定為整型int，用此棧存儲后綴表達(dá)式中的操作數(shù)、計算過程中的中間數(shù)據(jù)以及最后結(jié)果。假定一個后綴算術(shù)表達(dá)式以字符‘$’作為結(jié)束符，并且以一個字符串的方式提供。后綴表達(dá)式求值算法的基本思路是:把包含后綴算術(shù)表達(dá)式的字符串定義為一個輸入字符串流對象，每次從中讀入一個字符(空格作為數(shù)據(jù)之間的分隔符，不會被作為字符讀入)時，若是運(yùn)算符，則表明它的兩個操作數(shù)已經(jīng)在棧S中，其中棧頂元素為運(yùn)算符的后一個操作數(shù)，棧頂元素的下一個元素為運(yùn)算符的前一個操作數(shù)，把它們出棧后進(jìn)行相應(yīng)運(yùn)算即可，然后把運(yùn)算結(jié)果再壓入棧S中;否則，讀入的字符必為操作數(shù)的最高位數(shù)字，應(yīng)把它重新送回輸入流中，然后把下一個數(shù)據(jù)作為整型數(shù)據(jù)輸入，并將其壓入棧S中。依次掃描每一個字符(對于整型數(shù)據(jù)僅需掃描它的最高位并一次輸入整個數(shù)值)并進(jìn)行上述處理，直到遇到結(jié)束符‘$’為止，表明后綴表達(dá)式計算完畢，最終結(jié)果保存在棧中，并且棧中僅存這一個值，把它彈出返回即可。用類C++語言描述的表達(dá)式后綴表達(dá)式求值的算法如下所述:

int postexpression (char* str)

{// 計算由str字符串所表示的后綴表達(dá)式的值，表達(dá)式要以‘$’字符結(jié)束。

stack S;// 用S棧存儲操作數(shù)和中間計算結(jié)果

InitStack(S); // 初始化棧

istrstream ins(str);// 把str定義為輸入字符串流對象ins

char ch;// 用于輸入字符型數(shù)據(jù)

float x;// 用于輸入整型數(shù)據(jù)

ins>>ch;// 從ins流對象(即str字符串)中順序讀入一個字符

while (ch! =‘$’)

{ // 掃描每一個字符并進(jìn)行相應(yīng)處理

switch (ch)

{case‘+’:x=Pop(S) +Pop(S); break;

case‘-’:x=Pop(S);// Pop(S)彈出減數(shù)

x=Pop(S)-x;// Pop(S)彈出的是被減數(shù)

break;

case‘*’:x=Pop(S)*Pop(S); break;

case‘/’:x=Pop(S);// Pop(S)彈出除數(shù)

if(x! =0.0)x=Pop(S)/x; // Pop(S)彈出的是被除數(shù)

else {// 除數(shù)為0時終止運(yùn)行

cerr<<\"Divide by 0!\"< exit (1) ;}

break;

default: // 讀入的必為一個整型數(shù)的最高位數(shù)字

ins.putback(ch); // 把它重新回送到輸入流中

ins>>x;// 從字符串輸入流中讀入一個整型數(shù)據(jù)

}

Push(S，x); // 把讀入的一個整型數(shù)據(jù)或進(jìn)行相應(yīng)運(yùn)算的結(jié)果壓入到S棧中

ins>>ch; // 輸入下一個字符，以便進(jìn)行下一輪循環(huán)處理

}

if (! StackEmpty(S)) // 若棧中僅有一個元素，則它是后綴表達(dá)式的值，否則為出錯

{x=Pop(S);

if (Stack Empty(S)) return x;

else {cerr<<\"expression error!\"< exit (1) ;}

}

else {// 若最后棧為空，則終止運(yùn)行

cerr<<\"Stack is empty!\"< exit (1) ;}

此算法的運(yùn)行時間主要用在while循環(huán)上，它從頭至尾掃描后綴表達(dá)式中的每一個數(shù)據(jù)(每個操作數(shù)或運(yùn)算符均為一個數(shù)據(jù))，若后綴表達(dá)式由n個數(shù)據(jù)組成，則此算法的時間復(fù)雜度為O(n)。此算法在運(yùn)行時所占用的臨時空間主要取決于操作數(shù)棧的大小，顯然，它的最大深度不會超過表達(dá)式中操作數(shù)的個數(shù)，因?yàn)椴僮鲾?shù)的個數(shù)與運(yùn)算符(假定把‘$’也看作為一個特殊運(yùn)算符，即結(jié)束運(yùn)算符)的個數(shù)相等，所以此算法的空間復(fù)雜度也同樣為O(n)。

中綴表達(dá)式求值同樣也可以用堆棧來實(shí)現(xiàn)，但實(shí)現(xiàn)相對于后綴表達(dá)式較為復(fù)雜，它采用一種稱為“算符優(yōu)先法”的算法，它必須嚴(yán)格按照前面所述的三條規(guī)則來進(jìn)行計算。為了實(shí)現(xiàn)算符優(yōu)先算法，要使用兩個工作棧。一個稱為OPTR，用以寄存運(yùn)算符;另一個稱為OPND，用以寄存操作數(shù)或運(yùn)算結(jié)果，它的基本思想較后綴表達(dá)式計算的不同在于:當(dāng)讀取到運(yùn)算符時并不可能作相應(yīng)運(yùn)算，必須首先比較運(yùn)算符棧中棧頂元素與當(dāng)前運(yùn)算符的優(yōu)先級。若為‘<’則運(yùn)算符入棧;若為‘=’則說明是一對括號，需脫括號;若‘>’則作相應(yīng)運(yùn)算并將結(jié)果入棧。

用類C++語言描述的中綴表達(dá)式求值算法描述如下:

int middexpression (char *exp)

{ stack *opnd=new(stack);//操作數(shù)棧

stack *optr=new(stack);//運(yùn)算符棧

char ch=*exp;

int x=0，y，z;

int result;

optr→push(‘$’);

while(ch!=‘$’||optr→gettop()!=‘$’)

//字符掃描完畢且運(yùn)算符棧僅有‘#’時運(yùn)算結(jié)束

{ if(!Operator(ch))//取操作數(shù)并入棧

{ x=x*10+(int)(ch)-48;

if(Operator(*(exp+1)))

{opnd->push(x);x=0; }

ch=*++exp;}

else

{ switch(Precede(optr→gettop()，ch))

{ case‘<’:optr→push(ch);ch=*++exp; break; //棧頂元素優(yōu)先權(quán)低

case‘=’:optr→pop(); ch=*++exp;break;//脫括號并接收下一字符

case‘>’://退棧并將運(yùn)算結(jié)果入棧，但不取下一表達(dá)式字符

x=opnd→pop();y=opnd→pop(); z=calc(y，optr→pop()，x);

opnd->push(z);x=0;break; }}}

result=opnd→pop();

return(result);}

分析上述算法，運(yùn)算時間主要用在字符串掃描和算符優(yōu)先權(quán)的比較上。把‘$’看作運(yùn)算符，操作數(shù)與運(yùn)算符個數(shù)相同，最壞情況下優(yōu)先級比較是n/2次，即運(yùn)算順序完全是逆序的，每個字符掃描一遍是O(n)的，所以整個算法復(fù)雜度是O(n2)的。算法中用到兩個棧，其算法空間復(fù)雜度是O(n)。

3 比較

從兩個算法的分析比較中，我們可以看到優(yōu)先級的比較、運(yùn)算不按順序進(jìn)行使中綴表達(dá)計算的時間復(fù)雜性從O(n)到O(n2)，花費(fèi)了大量的運(yùn)行時間。若在計算機(jī)上具體運(yùn)行，從中我們還會發(fā)現(xiàn)，后綴表達(dá)式運(yùn)算時間比較穩(wěn)定，而中綴表達(dá)式由于運(yùn)算順序不同運(yùn)行時間相差較大，可見在時間復(fù)雜度和效率方面后綴表示方法要明顯優(yōu)于中綴表示方法。

4 結(jié)束語

經(jīng)以上的分析比較可以發(fā)現(xiàn)，后綴表達(dá)式要優(yōu)于中綴表達(dá)式，非常適合用計算機(jī)求解。但是比起中綴表達(dá)式，后綴表達(dá)式在形式上沒有中綴表達(dá)直觀，后者更適于人類的思維方式。因此利用計算機(jī)進(jìn)行科學(xué)計算，在高級語言程序設(shè)計中我們用中綴表達(dá)式來表示，而在計算機(jī)內(nèi)部是用后綴表達(dá)式來進(jìn)行計算的，因此為了處理方便，編譯程序常把中綴表達(dá)式首先轉(zhuǎn)換為后綴表達(dá)式然后再進(jìn)行運(yùn)算。中綴表達(dá)式與后綴表達(dá)式轉(zhuǎn)換算法的思想與中綴表達(dá)式求值算法基本相似，這里就不再贅述。但值得一提的是，轉(zhuǎn)換的時間復(fù)雜度是O(n)的，且只需要一個O(n/2)的運(yùn)算符棧。利用表達(dá)式的后綴表示和堆棧技術(shù)只需要兩遍掃描就可完成中綴算術(shù)表達(dá)式的計算，時間復(fù)雜度依然是O(n)的，顯然要大大優(yōu)于直接進(jìn)行中綴算術(shù)表達(dá)式計算。

參考文獻(xiàn):

[1] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)題集(C語言版)[M].北京:清華大學(xué)出版社，1997.

[2] 譚浩強(qiáng).C語言程序設(shè)計[M].2版北京:清華大學(xué)出版社，2000.

[3] 張乃孝，裘宗燕.數(shù)據(jù)結(jié)構(gòu)—C++與面向?qū)ο蟮耐緩絒M].北京:高等教育出版社，2004.

[4] 王曉東.算法設(shè)計與分析[M].北京:清華大學(xué)出版社，2003.

[5] 殷人昆.數(shù)據(jù)結(jié)構(gòu)(用面向?qū)ο蠓椒ㄅcC++描述)[M].北京:清華大學(xué)出版社，1999.