前置知識(shí)：人類使用的表達(dá)式一般為中綴表達(dá)式，這種表達(dá)式容易被人類理解，但不適合于機(jī)器計(jì)算。1920年，波蘭科學(xué)家揚(yáng)·武卡謝維奇（Jan ukasiewicz）發(fā)明了一種不需要括號(hào)的計(jì)算表達(dá)式的表示法將操作符號(hào)寫在操作數(shù)之前，也就是前綴表達(dá)式，即波蘭式（Polish Notation, PN）。將波蘭式倒轉(zhuǎn)，即逆波蘭式，廣泛用于使用堆棧的程序語(yǔ)言中。

Tips：源碼在文章最底下。

↓--------------------正文--------------------↓

對(duì)于四則運(yùn)算來說，程序的基本順序?yàn)椋狠斎?>獲取token->轉(zhuǎn)換為逆波蘭式->運(yùn)算結(jié)果->輸出。

--------------------輸入--------------------

輸入：這部分很簡(jiǎn)單，這里不細(xì)講。

--------------------轉(zhuǎn)化為逆波蘭式--------------------

獲取token：在四則運(yùn)算中，為了方便獲取，我們可以人為地定義一些符號(hào)的類型：

number : "0","1","2","3","4","5","6","7","8","9","."

left_bracket : "("

right_bracket : ")"

multiplication : "*"

division : "/"

addition : "+"

subtraction : "-"

這部分最復(fù)雜的地方在于"-"，因?yàn)樵跀?shù)字中，它既表示負(fù)號(hào)，又表示減號(hào)，所以要在這個(gè)階段就把負(fù)號(hào)連帶數(shù)字一起提取出來。

對(duì)于負(fù)號(hào)，它有兩種情況成立：

如果負(fù)號(hào)成立，那么可以把"-"當(dāng)做number，加入到number中。

處理完數(shù)字后，開始處理操作符，即"+" , "-" , "*" , "/" , "(" , ")"

對(duì)于數(shù)字和操作符的處理，網(wǎng)上有詳盡的規(guī)則：

例如：

檢測(cè)"*"，棧頂為"+"，入棧；

檢測(cè)"*"，棧頂為"/"，依次彈棧，直到?？栈驐ｍ敒?#34;("、"+"、"-"，停止彈棧，"*"壓棧；

檢測(cè)"+"，棧頂為"*"，依次彈棧，直到?？栈驐ｍ敒?#34;("，停止彈棧，"+"壓棧；

檢測(cè)"+"，棧頂為"-"，依次彈棧，直到棧空或棧頂為"("，停止彈棧，"+"壓棧；

檢測(cè)到")"，依次彈棧，直到棧頂為"("，"("彈棧剔除，")"壓棧。

為了debug方便，我選擇為操作符分別創(chuàng)建分支。

--------------------運(yùn)算結(jié)果--------------------

對(duì)于有堆棧的語(yǔ)言來說，逆波蘭式的計(jì)算很好理解，即：

從頭開始，遇到數(shù)字入棧，遇到操作符，彈出棧頂?shù)膬蓚€(gè)數(shù)字進(jìn)行計(jì)算，計(jì)算結(jié)果壓棧，運(yùn)行到表達(dá)式結(jié)束后，棧頂即運(yùn)算結(jié)果。

有個(gè)小細(xì)節(jié)是，假如彈棧的數(shù)字按順序分別是n1和n2，則n2為被減（除）數(shù)，n1是減（除）數(shù)。

--------------------輸出--------------------

這部分同樣很簡(jiǎn)單，就不提了。

--------------------總結(jié)--------------------

像我這種代碼新手，最難處理的部分反而是控制循環(huán)下的分支，其次才是數(shù)據(jù)結(jié)構(gòu)，所以我用了看起來非常弱智的方式來寫分支：

也就是

去除了else，加入了continue后，每一個(gè)分支的入口都被顯式控制了，debug效率倒是方便了不少，就是老程序員乍一眼看到嵌套地獄估計(jì)會(huì)高血壓。

--------------------代碼示例--------------------

最后附上測(cè)試結(jié)果和源碼，平臺(tái)是linqpad，主程序部分如果要用在控制臺(tái)或者winform還得自行修改。

debug結(jié)果示例：

源代碼：