(1、2.安順學院電子與信息工程學院，貴州 安順561000)

0 引言

表達式是由操作數(shù)、運算符和界限符組成。操作數(shù)可以是常數(shù)、變量、表達式，運算符可以是算術運算符、關系運算符和邏輯運算符，界限符有左右括弧和表達式結束符。表達式有中綴、前綴和后綴表示法。中綴表達式(通常稱表達式)，是運算符放在兩操作數(shù)的中間，如：a+b、4*3/(4-2)+8，它是表達式的常見表示法。前綴表達式是運算符放在兩操作數(shù)的前面，如：+ab、+/*43-428。后綴表達式是運算符放在兩操作數(shù)的后面，如：ab+、43*42-/8+。

表達式求值是數(shù)學中的一個基本問題，也是程序設計中的一個常見問題。對于表達式的三種表示法，計算機可以采用不同的運算規(guī)則來求解。表達式的運算規(guī)則：先乘除，后加減，從左到右計算，先括號內(nèi)，后括號外，即表達式運算不僅要依賴運算符優(yōu)先級，還要處理括號，在計算機中操作很不方便。前綴表達式的運算規(guī)則：連續(xù)出現(xiàn)的兩個操作數(shù)和在它之前出現(xiàn)且緊靠它的兩個操作數(shù)構成一個最小表達式。后綴表達式的運算規(guī)則：每個運算符和在它之前出現(xiàn)且緊靠它的兩個操作數(shù)構成一個最小表達式。由此可見，后綴表達式中運算符出現(xiàn)的順序正是表達式的運算順序。因此，在對表達式求值時，通常先將表達式轉(zhuǎn)換成相應的后綴表達式，再對后綴表達式進行求值。

1 表達式轉(zhuǎn)換研究現(xiàn)狀

目前，表達式之間的轉(zhuǎn)換已有很多研究。如：文獻[1]介紹了利用兩個棧及括號法實現(xiàn)表達式轉(zhuǎn)換為后綴表達式的方法，但對括號轉(zhuǎn)換法的描述：“移動所有運算符來取代所有的右括號，并以最近為原則進行替換?！?，容易把運算符和右括號對錯位；文獻[2]介紹了利用棧和數(shù)組實現(xiàn)表達式轉(zhuǎn)換為后綴表達式的方法；文獻[3]和[7]介紹了利用二叉樹實現(xiàn)表達式轉(zhuǎn)換為后綴表達式的方法，但對轉(zhuǎn)換過程的描述不夠清楚；文獻[5]介紹了用兩個棧、加括號及語法樹實現(xiàn)表達式轉(zhuǎn)換為后綴表達式的方法，但文中對括號轉(zhuǎn)換法的描述：“將每個運算符移到其所在括號的外面?！?，沒有說明清楚運算符是移到括號的前面還是后面，容易產(chǎn)生歧義。因為運算符移到其所在的括號前面和后面得到的是表達式不同的表示形式；文獻[6]和[9]介紹了用一個棧實現(xiàn)表達式轉(zhuǎn)換成后綴表達式的方法；文獻[10]、[11]及[12]介紹了利用兩個棧實現(xiàn)中綴表達式轉(zhuǎn)換后綴表達式方法及后綴表達式的求值。

通過分析、對比目前表達式轉(zhuǎn)換成后綴表達式的各種方法，總結得出目前表達式轉(zhuǎn)換為后綴表達式的方法主要有：(1)利用兩個棧進行轉(zhuǎn)換；(2)利用一個棧進行轉(zhuǎn)換；(3)利用二叉樹進行轉(zhuǎn)換；(4)用(加)括號法進行轉(zhuǎn)換。但這些轉(zhuǎn)換方法不夠全面和完整，本文提出了這幾種轉(zhuǎn)換方法：(1)利用棧和隊列進行轉(zhuǎn)換；(2)加括號去括號進行轉(zhuǎn)換；(3)直接轉(zhuǎn)換；(4)二叉樹進行轉(zhuǎn)換。以期對表達式轉(zhuǎn)換為后綴表達式的方法進行補充和完善。

2 表達式轉(zhuǎn)換成后綴表達式的方法

2.1 利用棧和隊列進行轉(zhuǎn)換

將一個表達式(exp)轉(zhuǎn)換成后綴表達式，操作數(shù)之間的相對次序不變，但運算符的相對次序可能要變，同時還要去掉括號。文章根據(jù)表達式中運算符優(yōu)先級、結合棧及隊列的特點，利用一個順序棧和一個順序隊列來實現(xiàn)表達式轉(zhuǎn)換為后綴表達式，其中順序棧S存儲運算符，順序隊列Q存儲中間結果，其具體轉(zhuǎn)換過程的偽代碼描述如下：

InitStack(S);

InitQueue(Q);

While(從exp讀取字符ch,ch!=’