棧的應用----四則運算，后綴逆波蘭表示法(RPN)

   我們從小就學習四則運算——加減乘除四則。我們也知道，要先乘除后加減，遇到括號要先算括號內的。可是，想讓計算機進行這樣的四則運算可不容易，它可不知道什么乘除優先，然后加減。那么，該如何讓計算機也能進行這樣的四則運算呢？就是通過棧。

   我們人類非常熟悉也非常喜歡用中綴表示法進行算數運算，什么是中綴表示法呢？也就是，一個運算符在兩個數字中間。比如，5+3,3*5,5/2等等，這些都是中綴表示法。這種表示法很適合人類使用，但是卻不適用于計算機，于是，我們就想出了一種適合計算機的表示方式，叫做，后綴表示法，也就是運算符出現在待運算數字的后面。比如，5+3，這種叫做中綴表示法，用后綴表示法就是，5 3 +，這樣的方式就是后綴表示法。也就是說，想讓計算機進行運算，首先就要把中綴表達式轉換成后綴表達式。接著才是對后綴表達式進行運算。

   那么先來講，中綴表達式轉換成后綴表達式是如何通過棧實現的。我們假設有這么一個中綴表達式：

5 + 4 * 6 / ( 3 + 7 ) * 2 + 1

我們遵循這樣的一個原則，遇到數字就直接將數字輸出，遇到運算符就將運算符壓入棧中。如果當前運算符跟棧頂運算符相比，優先級高于棧頂運算符，就將此運算符壓入棧中，該運算符成為新的棧頂運算符。換言之，如果該運算符不高于棧頂運算符，則棧頂元素依次出棧，并將當前符號進棧。好了，開始轉換。首先是5，所以，我們要將5輸出，因為5是數字，遇到數字就直接輸出，那么輸出為：

5

接著是一個“+”，因為是運算符，所以將運算符入棧。

+

接著，仍然是數字，所以將4輸出，

5 4

由于接下來的是一個乘號，所以，要將它與棧頂的運算符進行對比，發現*號優先級高于+號優先級，所以，將*號入棧，這樣以來，棧頂元素就為*號。

+ *

由于6也是數字，所以，可以將其輸出

5 4 6

接下來，是個關鍵。因為，接下來的一個符號是/號，所以，當它和*號對比時，發現/號優先級并不高于*號優先級，所以，將棧頂元素依次出棧，也就是

*

所以，目前，輸出元素為

5 4 6 *

然后，將/號入棧，此時棧中只有一個符號/

+ /

接著，是一個左括號( ，所以要將(入棧，直到碰到)是將括號內的內容出棧。

+ / (

因為是數字，所以將3出棧

5 4 6 * 3

接著將+號入棧

+ / ( +

接著是一個數字7，很明顯，將數字7出棧

5 4 6 * 3 7

這時碰到了),所以要將+出棧，

5 4 6 * 3 7 +

此時，棧中元素為，

+ /

接著是一個*號，將它與/號對比，發現，它不高于*號，所以，將/出棧，然后跟+號對比，發現高于+號，所以，*可以入棧了，所以，輸出元素如下：

5 4 6 * 3 7 + /

棧中數據如下：

+ *

接著是一個數字2，將2直接輸出

5 4 6 * 3 7 + / 2

接著是一個+號，優先級并不高于*號，也不高于棧底的+號，所以，將棧頂元素依次出棧，

5 4 6 * 3 7 + / 2 * +

然后將該+號入棧，所以，此時棧內元素為

+

當碰到最后一個1的時候，直接將1輸出。

5 4 6 * 3 7 + / 2 * + 1

最后了，已經沒有元素了，此時，就將棧中的+號輸出，所以，最后，后綴表達式為：

5 4 6 * 3 7 + / 2 * + 1 +

   此時，已經將我們人類認識的中綴表達式轉換成了機器認識的后綴表達式。那么，此時，就可以開始運算了，運算還是需要借助棧。當碰到數字時，還是需要將數字壓入棧，當碰到運算符時，從棧頂將元素取出，并進行運算。比如，5 4 6都是數字，于是，將5 4 6入棧，

5 4 6

接下來碰到了*號，所以，將6取出作為乘數，將4取出作為被乘數，進行相乘運算，4 * 6 = 24，此時，將運算結果24存入棧中。所以，棧中元素為：

5 24

因為3 7都是數字，所以，將3 7保存至棧中。

5 24 3 7

因為接下來碰到了一個+號，所以，將7和3取出，進行3 + 7 = 10的運算，然后將運算結果10放入棧中。

5 24 10

接下來是一個/號，所以，將10取出作為除數，將24取出作為被除數，所以，24 / 10 = 2.4，然后將2.4存入棧中，所以，

5 2.4

接下來，是一個數字2，所以，將2壓入棧中

5 2.4 2

然后是一個乘號，所以將2和2.4取出，執行2.4 * 2 = 4.8，將4.8壓入棧中

5 4.8

因為接下來是一個+號，所以將5和4.8取出，執行5 + 4.8 = 9.8，此時將9.8入棧

9.8

然后將數字1入棧

9.8 1

最后一個+號，所以將兩個數出棧，執行9.8 + 1 = 10.8，最后運算結果為，10.8。到此就完全結束了。

其實，我舉的這個例子是有問題的，棧中保存的是類型相同的元素，所以我這個例子舉的不好，不過不影響總結計算機執行四則運算的過程。