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

   我們從小就學(xué)習(xí)四則運(yùn)算——加減乘除四則。我們也知道，要先乘除后加減，遇到括號(hào)要先算括號(hào)內(nèi)的?？墒?，想讓計(jì)算機(jī)進(jìn)行這樣的四則運(yùn)算可不容易，它可不知道什么乘除優(yōu)先，然后加減。那么，該如何讓計(jì)算機(jī)也能進(jìn)行這樣的四則運(yùn)算呢？就是通過棧。

   我們?nèi)祟惙浅Ｊ煜ひ卜浅Ｏ矚g用中綴表示法進(jìn)行算數(shù)運(yùn)算，什么是中綴表示法呢？也就是，一個(gè)運(yùn)算符在兩個(gè)數(shù)字中間。比如，5+3,3*5,5/2等等，這些都是中綴表示法。這種表示法很適合人類使用，但是卻不適用于計(jì)算機(jī)，于是，我們就想出了一種適合計(jì)算機(jī)的表示方式，叫做，后綴表示法，也就是運(yùn)算符出現(xiàn)在待運(yùn)算數(shù)字的后面。比如，5+3，這種叫做中綴表示法，用后綴表示法就是，5 3 +，這樣的方式就是后綴表示法。也就是說，想讓計(jì)算機(jī)進(jìn)行運(yùn)算，首先就要把中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式。接著才是對(duì)后綴表達(dá)式進(jìn)行運(yùn)算。

   那么先來講，中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式是如何通過棧實(shí)現(xiàn)的。我們假設(shè)有這么一個(gè)中綴表達(dá)式：

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

我們遵循這樣的一個(gè)原則，遇到數(shù)字就直接將數(shù)字輸出，遇到運(yùn)算符就將運(yùn)算符壓入棧中。如果當(dāng)前運(yùn)算符跟棧頂運(yùn)算符相比，優(yōu)先級(jí)高于棧頂運(yùn)算符，就將此運(yùn)算符壓入棧中，該運(yùn)算符成為新的棧頂運(yùn)算符。換言之，如果該運(yùn)算符不高于棧頂運(yùn)算符，則棧頂元素依次出棧，并將當(dāng)前符號(hào)進(jìn)棧。好了，開始轉(zhuǎn)換。首先是5，所以，我們要將5輸出，因?yàn)?是數(shù)字，遇到數(shù)字就直接輸出，那么輸出為：

5

接著是一個(gè)“+”，因?yàn)槭沁\(yùn)算符，所以將運(yùn)算符入棧。

+

接著，仍然是數(shù)字，所以將4輸出，

5 4

由于接下來的是一個(gè)乘號(hào)，所以，要將它與棧頂?shù)倪\(yùn)算符進(jìn)行對(duì)比，發(fā)現(xiàn)*號(hào)優(yōu)先級(jí)高于+號(hào)優(yōu)先級(jí)，所以，將*號(hào)入棧，這樣以來，棧頂元素就為*號(hào)。

+ *

由于6也是數(shù)字，所以，可以將其輸出

5 4 6

接下來，是個(gè)關(guān)鍵。因?yàn)?，接下來的一個(gè)符號(hào)是/號(hào)，所以，當(dāng)它和*號(hào)對(duì)比時(shí)，發(fā)現(xiàn)/號(hào)優(yōu)先級(jí)并不高于*號(hào)優(yōu)先級(jí)，所以，將棧頂元素依次出棧，也就是

*

所以，目前，輸出元素為

5 4 6 *

然后，將/號(hào)入棧，此時(shí)棧中只有一個(gè)符號(hào)/

+ /

接著，是一個(gè)左括號(hào)( ，所以要將(入棧，直到碰到)是將括號(hào)內(nèi)的內(nèi)容出棧。

+ / (

因?yàn)槭菙?shù)字，所以將3出棧

5 4 6 * 3

接著將+號(hào)入棧

+ / ( +

接著是一個(gè)數(shù)字7，很明顯，將數(shù)字7出棧

5 4 6 * 3 7

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

5 4 6 * 3 7 +

此時(shí)，棧中元素為，

+ /

接著是一個(gè)*號(hào)，將它與/號(hào)對(duì)比，發(fā)現(xiàn)，它不高于*號(hào)，所以，將/出棧，然后跟+號(hào)對(duì)比，發(fā)現(xiàn)高于+號(hào)，所以，*可以入棧了，所以，輸出元素如下：

5 4 6 * 3 7 + /

棧中數(shù)據(jù)如下：

+ *

接著是一個(gè)數(shù)字2，將2直接輸出

5 4 6 * 3 7 + / 2

接著是一個(gè)+號(hào)，優(yōu)先級(jí)并不高于*號(hào)，也不高于棧底的+號(hào)，所以，將棧頂元素依次出棧，

5 4 6 * 3 7 + / 2 * +

然后將該+號(hào)入棧，所以，此時(shí)棧內(nèi)元素為

+

當(dāng)碰到最后一個(gè)1的時(shí)候，直接將1輸出。

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

最后了，已經(jīng)沒有元素了，此時(shí)，就將棧中的+號(hào)輸出，所以，最后，后綴表達(dá)式為：

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

   此時(shí)，已經(jīng)將我們?nèi)祟愓J(rèn)識(shí)的中綴表達(dá)式轉(zhuǎn)換成了機(jī)器認(rèn)識(shí)的后綴表達(dá)式。那么，此時(shí)，就可以開始運(yùn)算了，運(yùn)算還是需要借助棧。當(dāng)碰到數(shù)字時(shí)，還是需要將數(shù)字壓入棧，當(dāng)碰到運(yùn)算符時(shí)，從棧頂將元素取出，并進(jìn)行運(yùn)算。比如，5 4 6都是數(shù)字，于是，將5 4 6入棧，

5 4 6

接下來碰到了*號(hào)，所以，將6取出作為乘數(shù)，將4取出作為被乘數(shù)，進(jìn)行相乘運(yùn)算，4 * 6 = 24，此時(shí)，將運(yùn)算結(jié)果24存入棧中。所以，棧中元素為：

5 24

因?yàn)? 7都是數(shù)字，所以，將3 7保存至棧中。

5 24 3 7

因?yàn)榻酉聛砼龅搅艘粋€(gè)+號(hào)，所以，將7和3取出，進(jìn)行3 + 7 = 10的運(yùn)算，然后將運(yùn)算結(jié)果10放入棧中。

5 24 10

接下來是一個(gè)/號(hào)，所以，將10取出作為除數(shù)，將24取出作為被除數(shù)，所以，24 / 10 = 2.4，然后將2.4存入棧中，所以，

5 2.4

接下來，是一個(gè)數(shù)字2，所以，將2壓入棧中

5 2.4 2

然后是一個(gè)乘號(hào)，所以將2和2.4取出，執(zhí)行2.4 * 2 = 4.8，將4.8壓入棧中

5 4.8

因?yàn)榻酉聛硎且粋€(gè)+號(hào)，所以將5和4.8取出，執(zhí)行5 + 4.8 = 9.8，此時(shí)將9.8入棧

9.8

然后將數(shù)字1入棧

9.8 1

最后一個(gè)+號(hào)，所以將兩個(gè)數(shù)出棧，執(zhí)行9.8 + 1 = 10.8，最后運(yùn)算結(jié)果為，10.8。到此就完全結(jié)束了。

其實(shí)，我舉的這個(gè)例子是有問題的，棧中保存的是類型相同的元素，所以我這個(gè)例子舉的不好，不過不影響總結(jié)計(jì)算機(jī)執(zhí)行四則運(yùn)算的過程。