棧是一種特殊的線性表，它只能在一端進(jìn)行插入或者刪除操作，能進(jìn)行操作的一端稱為棧頂，另一端則稱為棧底。利用棧的這個特性，我們可以實現(xiàn)表達(dá)式的求值。那么如何利用棧來進(jìn)行表達(dá)式求值呢？關(guān)于棧的應(yīng)用—表達(dá)式求值如何實現(xiàn)呢，接下來我們帶著問題去學(xué)習(xí)下面的內(nèi)容。

利用棧來進(jìn)行表達(dá)式求值有以下兩種方式：

一、逆波蘭表達(dá)式

逆波蘭表達(dá)式（reverse Polish notation, RPN）又叫做后綴表達(dá)式，波蘭邏輯學(xué)家 J.Lukasiewicz 于1929年提出了這種表示表達(dá)式的方法，按此方法，每一運算符都置于其運算對象之后，故稱為后綴表達(dá)式。與此相對應(yīng)的，我們將我們平常所見到的將二元運算符置于與之相關(guān)的兩個運算對象之間的表達(dá)式稱作中綴表達(dá)式。

舉個例子大家就明白了，「1 + 2」就是中綴表達(dá)式，若把加號寫在最后面：「1 2 +」就是后綴表達(dá)式。再來一個復(fù)雜點的，中綴表達(dá)式「 (1 + 2) * 3 + 4」寫成后綴表達(dá)式就是「 1 2 + 3 * 4 +」。

這種表示方式簡直就是反人類的，為什么呢？因為很容易引起歧義，比如「123+」，我怎么知道這表示的是「1 + 23」還是「12 + 3」？即使是在 12 和 3 之間加一個空格，來讓「12 3 +」表示「12 + 3」，但是對我們?nèi)祟悂碚f還是不夠直觀。所以這種表示方式在日常生活中并不常見。但是從計算機(jī)的角度看，后綴表達(dá)式處理起來會更加簡便，因為計算機(jī)只要自左向右掃描后綴表達(dá)式，就可以完成表達(dá)式的求值。由于后綴表達(dá)式不需要考慮運算符的優(yōu)先規(guī)則，因此求值算法就變得簡單了：

1、從左到右依次遍歷表達(dá)式；

2、遇到數(shù)字就直接入棧；

3、遇到操作符就彈出兩個元素，先彈出的元素放到操作符的右邊，后彈出的元素放到操作符的左邊（左邊的運算數(shù)先入棧，因此后出），將計算得到的結(jié)果再壓入棧；

4、直到整個表達(dá)式遍歷完，最后彈出的棧頂元素就是表達(dá)式最終的值。

二、中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式

接下來看看中綴怎么轉(zhuǎn)后綴，我們先對比一下兩個表達(dá)式：

中綴表達(dá)式：2 + 9 / 3 - 5

后綴表達(dá)式：2 9 3 / + 5 -

可以看的出來，數(shù)字的相對位置是不變的，改變的是符號的位置，那么在轉(zhuǎn)換的過程，我們需要對比各種運算符號的優(yōu)先級，然后將優(yōu)先級高的運算符，先輸出，低的后輸出，這樣在后綴表達(dá)式求值的時候，就能保存計算順序不被改變。（左括號和右括號也看成運算符號）具體的算法步驟如下：

1、從左到右遍歷中綴表達(dá)式；

2、如果是運算數(shù)，直接輸出；

3、如果是運算符號：若優(yōu)先級大于棧頂?shù)倪\算符號（棧不為空），則將該運算符號壓入棧中，因為如果該運算符號優(yōu)先級比棧頂?shù)拇螅f明要先被計算，那么它是后入的，因此在之后的操作中，一定比棧頂?shù)姆栂瘸觯虼嗽诤缶Y求值中，肯定先被計算；

4、如果是運算符號：若優(yōu)先級小于等于棧頂?shù)倪\算符號（棧不為空），則將棧頂?shù)倪\算符號彈出并輸出，然后繼續(xù)和下一個新的棧頂元素對比，直到優(yōu)先級大于新的棧頂元素，就將該運算符號壓入棧中；

5、左括號：括號里的表達(dá)式肯定是要先計算的，因此當(dāng)掃描到左括號的時候，直接將左括號壓入棧中，而入了棧里的左括號，優(yōu)先級就變到最低了。因為括號里的運算符要先運算；

6、右括號：將棧頂元素彈出并輸入，直到遇到左括號（彈出，但不輸出）；

7、整個表達(dá)式遍歷完之后，則將棧里的元素一一彈出并輸出。

棧的應(yīng)用—表達(dá)式求值就差不多講清楚了，事實上棧是一種被廣泛應(yīng)用的數(shù)據(jù)結(jié)構(gòu)，除了上述的表達(dá)式求值之外，棧還用于函數(shù)調(diào)用及遞歸實現(xiàn)，回溯算法等等。在適當(dāng)?shù)臅r候選擇棧，可以更加高效的解決問題。想要了解棧的更多應(yīng)用可以觀看本站的數(shù)據(jù)結(jié)構(gòu)和算法教程，去探索和發(fā)現(xiàn)更多的棧的神奇之處！