逆波蘭表達式在VB中的算法設計與實現

楊 忠

YANG Zhong

（淄博職業學院，淄博 255013）

0 引言

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

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

1 確定運算符優先級

為了正確實現中綴向逆波蘭表達式轉換，必須明確操作符的優先級，如表1所示。

表1 算術操作符優先級設置

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

表2 數學函數和算術操作符優先級設置

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

2 算法設計

1）在VB中利用數組實現棧的原理應用。定義兩個數組chaarr和operator，定義一個操作符結構體數組op。

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

操作符棧operator用于存儲操作符，根據優先級的大小，實現棧的壓棧和彈棧操作。

op用于存儲操作符號本身，并賦予操作符在棧內和棧外優先級，用于彈棧和壓棧判斷。

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

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

3 程序實現

根據前面確定的運算符優先級和程序設計思想，可以如下代碼實現逆波蘭表達式轉換為后綴表達式。為了直觀的看到轉換結果，簡單的設計如圖1所示界面。

圖1 公式解釋器

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

程序實現核心代碼如下，只要在轉化按鈕單擊事件中調用該代碼塊即可，其中涉及到的先期部分條件不再一一列出，代碼塊中有部分說明。核心代碼中對于不同操作符的判斷部分已經刪除，其編寫原理與開始的“*”操作符類似，只要能合理設置操作符優先級即可保證程序的正確運行，不再贅述。

ReDim chararr(Len(strexp))

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

4 結束語

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

[1] 嚴蔚敏,吳偉民.數據結構[M].北京：清華大學出版社,2004.

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