棧是一種特殊的線性表，它只能在一端進行插入或者刪除操作，能進行操作的一端稱為棧頂，另一端則稱為棧底。利用棧的這個特性，我們可以實現表達式的求值。那么如何利用棧來進行表達式求值呢？關于棧的應用—表達式求值如何實現呢，接下來我們帶著問題去學習下面的內容。

利用棧來進行表達式求值有以下兩種方式：

一、逆波蘭表達式

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

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

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

1、從左到右依次遍歷表達式；

2、遇到數字就直接入棧；

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

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

二、中綴表達式轉后綴表達式

接下來看看中綴怎么轉后綴，我們先對比一下兩個表達式：

中綴表達式：2 + 9 / 3 - 5

后綴表達式：2 9 3 / + 5 -

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

1、從左到右遍歷中綴表達式；

2、如果是運算數，直接輸出；

3、如果是運算符號：若優先級大于棧頂的運算符號（棧不為空），則將該運算符號壓入棧中，因為如果該運算符號優先級比棧頂的大，說明要先被計算，那么它是后入的，因此在之后的操作中，一定比棧頂的符號先出，因此在后綴求值中，肯定先被計算；

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

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

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

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

棧的應用—表達式求值就差不多講清楚了，事實上棧是一種被廣泛應用的數據結構，除了上述的表達式求值之外，棧還用于函數調用及遞歸實現，回溯算法等等。在適當的時候選擇棧，可以更加高效的解決問題。想要了解棧的更多應用可以觀看本站的數據結構和算法教程，去探索和發現更多的棧的神奇之處！