逆波蘭表達式在VB中的算法設(shè)計與實現(xiàn)

楊 忠

YANG Zhong

（淄博職業(yè)學(xué)院，淄博 255013）

0 引言

在高級語言中出現(xiàn)的算術(shù)表達式，如a+(b-c)d，其運算符一般出現(xiàn)在操作數(shù)之間，此為中綴表達式，而編譯系統(tǒng)不考慮表達式的優(yōu)先級別，只是對表達式從左到右進行掃描，當(dāng)遇到運算符時，就把其前面的兩個操作數(shù)取出進行操作。為達到上述目的，就要將中綴表達式改成abc-d+樣式，操作符均在操作數(shù)的后面，此為逆波蘭表達式。

在逆波蘭表達式中，不再出現(xiàn)括號，運算符放在兩個運算對象的后面，運算嚴格按照從左到右的順序進行，因而計算一個后綴表達式的值，其算法要比計算一個中綴表達式簡單得多。以下以VB為開發(fā)平臺，用順序棧的工作原理完成逆波蘭表達式的算法設(shè)計與實現(xiàn)。

1 確定運算符優(yōu)先級

為了正確實現(xiàn)中綴向逆波蘭表達式轉(zhuǎn)換，必須明確操作符的優(yōu)先級，如表1所示。

表1 算術(shù)操作符優(yōu)先級設(shè)置

如果公式中還有其他的數(shù)學(xué)函數(shù)參與運算，可以相應(yīng)定義優(yōu)先級，實現(xiàn)轉(zhuǎn)換，但必須定義某種規(guī)則用一個字母代替函數(shù)且嚴格按照書寫規(guī)范書寫。比如表達式sin(a)＋b，在表達式中含有數(shù)學(xué)運算函數(shù)sin()，我們可以用S表示該函數(shù)，然后如表2 所示設(shè)置操作符和函數(shù)的優(yōu)先級即可。

表2 數(shù)學(xué)函數(shù)和算術(shù)操作符優(yōu)先級設(shè)置

以上表中的#作為操作符棧棧底元素，用于第一個入棧操作符。isp表示操作符或函數(shù)在棧內(nèi)優(yōu)先級，icp表示操作符和函數(shù)在棧外優(yōu)先級。每個操作符均有棧內(nèi)和棧外兩種優(yōu)先級，用于決定壓棧還是彈棧。

2 算法設(shè)計

1）在VB中利用數(shù)組實現(xiàn)棧的原理應(yīng)用。定義兩個數(shù)組chaarr和operator，定義一個操作符結(jié)構(gòu)體數(shù)組op。

chaarr用于存儲表達式中所有的操作數(shù)變量和操作符，對于公式中含有常數(shù)情況本文未作考慮。

操作符棧operator用于存儲操作符，根據(jù)優(yōu)先級的大小，實現(xiàn)棧的壓棧和彈棧操作。

op用于存儲操作符號本身，并賦予操作符在棧內(nèi)和棧外優(yōu)先級，用于彈棧和壓棧判斷。

2）利用函數(shù)mid從表達式中分離每個元素，當(dāng)判斷出該元素是操作數(shù)變量時直接把該變量存入chaarr中，當(dāng)分解出的是操作符時，首先定義該操作符的棧內(nèi)棧外優(yōu)先級，存入操作符結(jié)構(gòu)體數(shù)組op，然后判斷該操作符的棧外優(yōu)先級和operator內(nèi)棧頂元素的棧內(nèi)優(yōu)先級的高低，如果是大于關(guān)系則把該操作符壓棧operator，如果是小于關(guān)系，則把operator棧頂元素彈棧并存入chaarr中，原分離出的操作符繼續(xù)與operatro內(nèi)棧頂元素比較優(yōu)先級，可能要重復(fù)進行彈棧、存入chaarr、比較優(yōu)先級過程，直至該操作符壓棧為止。如果括號彈棧，不把它存入chaarr中，因為后綴形式已經(jīng)準確的表明了公式的先后運算次序關(guān)系。

3）利用一個循環(huán)，重復(fù)執(zhí)行第2步，直至公式分解完畢，此時chaarr中存儲的所有字符實現(xiàn)連接后就是我們需要的后綴表達式。

3 程序?qū)崿F(xiàn)

根據(jù)前面確定的運算符優(yōu)先級和程序設(shè)計思想，可以如下代碼實現(xiàn)逆波蘭表達式轉(zhuǎn)換為后綴表達式。為了直觀的看到轉(zhuǎn)換結(jié)果，簡單的設(shè)計如圖1所示界面。

圖1 公式解釋器

只要在輸入公式文本框中輸入公式，點擊轉(zhuǎn)化按鈕就可以轉(zhuǎn)化為逆波蘭表達式。

程序?qū)崿F(xiàn)核心代碼如下，只要在轉(zhuǎn)化按鈕單擊事件中調(diào)用該代碼塊即可，其中涉及到的先期部分條件不再一一列出，代碼塊中有部分說明。核心代碼中對于不同操作符的判斷部分已經(jīng)刪除，其編寫原理與開始的“*”操作符類似，只要能合理設(shè)置操作符優(yōu)先級即可保證程序的正確運行，不再贅述。

ReDim chararr(Len(strexp))

'strexp表示通過界面輸入的公式，chararr()是定義的全局數(shù)組。

4 結(jié)束語

為了處理方便，編譯程序常把中綴表達式首先轉(zhuǎn)換成等價的逆波蘭表達式。在VB中，可以利用順序棧的工作原理使用數(shù)組實現(xiàn)表達式的中綴形式向逆波蘭表達式轉(zhuǎn)化，從而完成數(shù)值計算。

[1] 嚴蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社,2004.

[2] 林永.Visual Basic程序Widows API編程手冊[M].北京：人民郵電出版社,2002.