簡單的表達式求值

一直很想做個比Windows自帶的高級一點的計算器，能將整個表達式輸入，然後求值。這個程序要求讀者具備編譯原理的一些知識。舉個實例來說明程序處理過程。假設要求值的表達式為 ：

-25*（56+15）# (其中＃號作為表達式結束標志)。

首先對表達式進行詞法分析，允許出現的字符為：

{0 ，1， 2 ，3 ，4 ，5 ，6， 7 ，8， 9 . ，+ ，-， *， / ，（ ，），＃}

分析的結果產生兩種類型的單詞：操作符和操作數。

操作符包括：

{+, - ,* ,/ ,（ ,）}

操作數包括：

int 和 double 類型。

上面表達式產生的單詞序列為：

{-25,*,(,56,+,15,)}。

這些單詞的類型也需要保存。

詞法分析正確後將對產生的單詞序列進行語法分析。

定義E為表達式，N為常數（視為終結符）。表達式的產生式可表示如下：

E ' N
E ' (E)
E ' E+E
E ' E-E
E ' E*E
E ' E/E消除左遞歸後的產生式(E_為新產生的符號):

E->NE_
E->(E)E_
E_->+EE_
E_->-EE_
E_->*EE_
E_->/EE_
E_->NULL (空串)

可以根據這個產生式構造遞歸的語法分析器。具體細節就不敘述了，可以閱讀源代碼。

語法分析正確後就可以求值了，求值時用到一個操作數堆棧和操作符堆棧，以及一個算符優先表（存儲了運算符之間的優先關系），具體細節可以閱讀源碼。

本文配套源碼