Posted on 2009-12-01 16:03
Just Do It 閱讀(404)
評論(0) 編輯 收藏
摘自：http://www.ibm.com/developerworks/cn/java/j-w3eva/index.html#main
編寫代碼對算術表達式求值的經典方法由 Donald Knuth 描述于 1962 年（請參閱 參考資料）。Knuth 將此概括為三個步驟：
- 對中綴表達式進行語法分析
- 中綴表達式到后綴表達式的轉換
- 對后綴表達式求值
注意到我們談到的這個經典算法有些簡化：算術表達式只包含操作數、二元操作符和一種括號。此外，對于每個操作數和操作符，只用單個字符表示，使語法分析直觀。
表達式表示法
算術表達式中最常見的表示法形式有 中綴、前綴和 后綴表示法。中綴表示法是書寫表達式的常見方式，而前綴和后綴表示法主要用于計算機科學領域。
中綴表示法
中綴表示法是算術表達式的常規表示法。稱它為 中綴表示法是因為每個操作符都位于其操作數的中間，這種表示法只適用于操作符恰好對應兩個操作數的時候（在操作符是二元操作符如加、減、乘、除以及取模的情況下）。對以中綴表示法書寫的表達式進行語法分析時，需要用括號和優先規則排除多義性。
Syntax: operand1 operator operand2
Example: (A+B)*C-D/(E+F)
|
前綴表示法
前綴表示法中，操作符寫在操作數的前面。這種表示法經常用于計算機科學，特別是編譯器設計方面。為紀念其發明家 ― Jan Lukasiewicz（請參閱 參考資料），這種表示法也稱 波蘭表示法。
Syntax : operator operand1 operand2
Example : -*+ABC/D+EF
|
后綴表示法
在后綴表示法中，操作符位于操作數后面。后綴表示法也稱 逆波蘭表示法（reverse Polish notation，RPN），因其使表達式求值變得輕松，所以被普遍使用。
Syntax : operand1 operand2 operator
Example : AB+C*DEF+/-
|
前綴和后綴表示法有三項公共特征：
- 操作數的順序與等價的中綴表達式中操作數的順序一致
- 不需要括號
- 操作符的優先級不相關
中綴表達式到后綴表達式的轉換
要把表達式從中綴表達式的形式轉換成用后綴表示法表示的等價表達式，必須了解操作符的優先級和結合性。 優先級或者說操作符的強度決定求值順序；優先級高的操作符比優先級低的操作符先求值。 如果所有操作符優先級一樣，那么求值順序就取決于它們的 結合性。操作符的結合性定義了相同優先級操作符組合的順序（從右至左或從左至右）。
Left associativity : A+B+C = (A+B)+C
Right associativity : A^B^C = A^(B^C)
|
轉換過程包括用下面的算法讀入中綴表達式的操作數、操作符和括號：
- 初始化一個空堆棧，將結果字符串變量置空。
- 從左到右讀入中綴表達式，每次一個字符。
- 如果字符是操作數，將它添加到結果字符串。
- 如果字符是個操作符，彈出（pop）操作符，直至遇見開括號（opening parenthesis）、優先級較低的操作符或者同一優先級的右結合符號。把這個操作符壓入（push）堆棧。
- 如果字符是個開括號，把它壓入堆棧。
- 如果字符是個閉括號（closing parenthesis），在遇見開括號前，彈出所有操作符，然后把它們添加到結果字符串。
- 如果到達輸入字符串的末尾，彈出所有操作符并添加到結果字符串。
后綴表達式求值
對后綴表達式求值比直接對中綴表達式求值簡單。在后綴表達式中，不需要括號，而且操作符的優先級也不再起作用了。您可以用如下算法對后綴表達式求值：
- 初始化一個空堆棧
- 從左到右讀入后綴表達式
- 如果字符是一個操作數，把它壓入堆棧。
- 如果字符是個操作符，彈出兩個操作數，執行恰當操作，然后把結果壓入堆棧。如果您不能夠彈出兩個操作數，后綴表達式的語法就不正確。
- 到后綴表達式末尾，從堆棧中彈出結果。若后綴表達式格式正確，那么堆棧應該為空。