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

楊 忠

YANG Zhong

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

0 引言

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

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

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

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

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

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

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

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

2 算法設(shè)計(jì)

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

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

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

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

2）利用函數(shù)mid從表達(dá)式中分離每個(gè)元素，當(dāng)判斷出該元素是操作數(shù)變量時(shí)直接把該變量存入chaarr中，當(dāng)分解出的是操作符時(shí)，首先定義該操作符的棧內(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ù)進(jìn)行彈棧、存入chaarr、比較優(yōu)先級過程，直至該操作符壓棧為止。如果括號彈棧，不把它存入chaarr中，因?yàn)楹缶Y形式已經(jīng)準(zhǔn)確的表明了公式的先后運(yùn)算次序關(guān)系。

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

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

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

圖1 公式解釋器

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

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

ReDim chararr(Len(strexp))

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

4 結(jié)束語

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

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

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