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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3、如果是運(yùn)算符號(hào)：若優(yōu)先級(jí)大于棧頂?shù)倪\(yùn)算符號(hào)（棧不為空），則將該運(yùn)算符號(hào)壓入棧中，因?yàn)槿绻撨\(yùn)算符號(hào)優(yōu)先級(jí)比棧頂?shù)拇螅f(shuō)明要先被計(jì)算，那么它是后入的，因此在之后的操作中，一定比棧頂?shù)姆?hào)先出，因此在后綴求值中，肯定先被計(jì)算；

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

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

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

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

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