堆棧解析算術表達式

中綴表達式就是通常所說的算術表達式，比如(1+2)*3-4。

字尾表達式是指通過解析後，運算符在運算數之後的表達式，比如上式解析成字尾表達式就是12+3*4-。這種表達式可以直接利用棧來求解。

中綴->字尾 就是運算符的出入棧，操作數直接輸出，運算符按優先級高（低）是入（出）棧。

運算符的優先級

優先級

運算符

1

括号()

2

負号-

3

乘方**

4

乘*，除/，求餘%

5

加+，減-

6

小于<，小于等于<=，大于>，大于等于>=

7

等于==，不等于!=

8

邏輯與&&

9

邏輯或||

堆棧解析算術表達式的過程

中綴表達式翻譯成字尾表達式的方法如下：

（1）從右向左依次取得資料ch。

（2）如果ch是操作數，直接輸出。

（3）如果ch是運算符（含左右括号），則：

      a：如果ch = '('，放入堆棧。

      b：如果ch = ')'，依次輸出堆棧中的運算符，直到遇到'('為止。

      c：如果ch不是')'或者'('，那麼就和堆棧頂點位置的運算符top做優先級比較。

           1：如果ch優先級比top高，那麼将ch放入堆棧。

           2：如果ch優先級低于或者等于top，那麼輸出top，然後将ch放入堆棧。

（4）如果表達式已經讀取完成，而堆棧中還有運算符時，依次由頂端輸出。

如果我們有表達式(a-b)*c+d-e/f，要翻譯成字尾表達式，并且把字尾表達式存儲在一個名叫output的字元串中，可以用下面的步驟。

（1）讀取'('，壓入堆棧，output為空

（2）讀取a，是運算數，直接輸出到output字元串，output = a

（3）讀取'-'，此時棧裡面隻有一個'('，是以将'-'壓入棧，output = a

（4）讀取b，是運算數，直接輸出到output字元串，output = ab

（5）讀取')'，這時候依次輸出棧裡面的運算符'-'，然後就是'('，直接彈出，output = ab-

（6）讀取'*'，是運算符，由于此時棧為空，是以直接壓入棧，output = ab-

（7）讀取c，是運算數，直接輸出到output字元串，output = ab-c

（8）讀取'+'，是運算符，它的優先級比'*'低，那麼彈出'*'，壓入'+"，output = ab-c*

（9）讀取d，是運算數，直接輸出到output字元串，output = ab-c*d

（10）讀取'-'，是運算符，和'+'的優先級一樣，是以彈出'+'，然後壓入'-'，output = ab-c*d+

（11）讀取e，是運算數，直接輸出到output字元串，output = ab-c*d+e

（12）讀取'/'，是運算符，比'-'的優先級高，是以壓入棧，output = ab-c*d+e

（13）讀取f，是運算數，直接輸出到output字元串，output = ab-c*d+ef

（14）原始字元串已經讀取完畢，将棧裡面剩餘的運算符依次彈出，output = ab-c*d+ef/-

計算算術表達式

字尾表達式按照下面的流程來計算。

現在是操作數入棧，運算符進行兩兩比較。

（1）從左向右掃描表達式，一個取出一個資料data

（2）如果data是操作數，就壓入堆棧

（3）如果data是操作符，就從堆棧中彈出此操作符需要用到的資料的個數，進行運算，然後把結果壓入堆棧

（4）如果資料處理完畢，堆棧中最後剩餘的資料就是最終結果。

比如我們要處理一個字尾表達式1234+*+65/-，那麼具體的步驟如下。

（1）首先1，2，3，4都是操作數，将它們都壓入堆棧

（2）取得'+'，為運算符，彈出資料3，4，得到結果7，然後将7壓入堆棧

（3）取得'*'，為運算符，彈出資料7，2，得到資料14，然後将14壓入堆棧

（4）取得'+'，為運算符，彈出資料14，1，得到結果15，然後将15壓入堆棧

（5）6，5都是資料，都壓入堆棧

（6）取得'/'，為運算符，彈出資料6，5，得到結果1.2，然後将1.2壓入堆棧

（7）取得'-'，為運算符，彈出資料15，1.2，得到資料13.8，這就是最後的運算結果