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

0 引言

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

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

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

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

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

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

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

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

InitStack(S);

InitQueue(Q);

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