利用棧實現表達式求值

前言

假如要你實現一個可以識別表達式的簡易計算器，你會怎麼實現？例如用戶輸入：

3 + 5 * (2 - 4)

可以直接得出計算結果：-7。對於人類來說，我們很容易計算出來，因為我們從左往右看，看到後面括弧時，知道括弧內的計算優先順序最高，因此可以先計算括弧內的，然後反過來計算乘法，最後計算加法，得到最終結果。

尾碼表達式

而對於電腦來說，實際也可以採用類似的順序，先記錄存儲3為a，然後存儲5為b，計算2-4結果存入c，再然後計算b*c存儲d，最終計算a+d得到最終結果。而這種計算過程的操作順序可描述如下(把操作符號放在操作數後面)：

3 5 2 4 - * +

這種記法叫做尾碼或逆波蘭記法（而我們平常見到的叫中綴記法），它的特點是不需要用括弧就能表示出整個表達式哪部分運算先進行，也就是說不需要考慮優先順序，這非常符合電腦的處理方式。這種記法很容易使用我們前面介紹的棧來求值，但是前提是需要將中綴表達式先轉換為尾碼表達式。對於這種轉換，我們也可以使用前面介紹的棧-C語言實現或者將要介紹的樹來完成，因篇幅有限，本文不准備介紹。

接下來將會介紹如何利用中綴表達式進行求值。

利用棧實現中綴表達式求值

前面也說到，所謂中綴表達式，就是我們能看到的正常表達式，中綴表達式求值，也就是直接對輸入的表達式進行求值。為簡單起見，我們這裡假設只涉及加減乘除和小括弧，並且操作數都是正整數，不涉及更加複雜的數據或運算。

計算思路：

• 使用兩個棧，stack0用於存儲操作數，stack1用於存儲操作符
• 從左往右掃描，遇到操作數入棧stack0
• 遇到操作符時，如果優先順序低於或等於棧頂操作符優先順序，則從stack0彈出兩個元素進行計算，並壓入stack0，繼續與棧頂操作符的比較優先順序
• 如果遇到操作符高於棧頂操作符優先順序，則直接入棧stack1
• 遇到左括弧，直接入棧stack1，遇到右括弧，則直接出棧並計算，直到遇到左括弧

上面的思路可能看起來不是很明確，我們舉一個簡單的例子，假如要對下麵的表達式求值：

6 * (2 + 3 )* 8 + 5

我們從左往右開始掃描。首先遇到操作數‘6’，和操作符‘*’，分別入棧
stack0:

stack1:

繼續往後掃描，遇到‘(’直接入棧，‘2’入棧，棧頂是左括弧，’+‘入棧，‘3’入棧
stack0:

stack1:

繼續往後掃描，遇到右括弧，它與棧頂操作符‘+’相比，優先順序要高，因此，將‘+’出棧，彈出兩個操作數‘3’,‘2’，計算結果得到‘5’，併入棧：

stack0:

stack1:

繼續出棧，直到遇到左括弧
stack0:

stack1:

繼續往後掃描，遇到操作符‘’,優先順序與棧頂‘’優先順序相同，因此彈出操作數並計算得到30入棧，最後‘*’入棧

stack0:

stack1:

繼續掃描，‘8’入棧，操作符‘+’優先順序小於‘*’，彈出操作數計算得到結果‘240’，並將其入棧，最後‘+’也入棧

stack0:

stack1:

最後‘5’入棧，發現操作符棧不為空，彈出操作符‘+’和兩個操作數，併進行計算，得到‘245’，入棧，得到最終結果。
stack0

stack1:

代碼實現

完整代碼實現請訪問利用棧實現表達式求值

總結

本文介紹了利用棧對中綴表達式進行求值，而代碼實現還有很多不足之處，例如對錶達式的正確性校驗不足，只能處理正整數等等，歡迎在此基礎上完善補充。儘管如此，整個過程對使用棧進行中綴表達式的求值做了一個較為完整的介紹，因此具有一定的參考性。

微信公眾號【編程珠璣】：專註但不限於分享電腦編程基礎，Linux，C語言，C++，數據結構與演算法，工具，資源等編程相關[原創]技術文章，號內包含大量經典電子書和視頻學習資源。歡迎一起交流學習，一起修煉電腦“內功”，知其然，更知其所以然。

公眾號編程珠璣