表達式求值--堆棧應用

了解對運算數和運算符的操作：

 重要的下面三個問題：

• 中綴表達式如何直接求值？
• 字尾表達式如何直接求值？
• 中綴表達式如何轉換為字尾表達式？

     将一個中序表達式轉化成為逆波蘭表達式的方法其實很簡單，也是一個成型的算法。通過逆波蘭表達式求一個計算式子的值，也是很簡單的，隻要遇到過會用就行了。

1、将一個中序表達式轉化成為逆波蘭表達式。(逆波蘭表達式又叫做字尾表達式)

       首先維護的是兩個棧，我們這裡暫且稱為S1和S2，S1中的結果最後存的就是逆波蘭表達式，S2中将用于暫時存放運算符并且在最終形成逆波蘭表達式的時候，該棧是會清空的。下面我們看看怎樣具體的形成逆波蘭表達式。

       在此首先定義一下運算符的優先級關系，從小到達排序，相同優先級沒有用逗号隔開：（，+-，*\，負号，）。

       從左至右周遊一個給定的中序表達式，也就是我們正常的數學計算的表達式。

（1）如果遇到的是數字，我們直接加入到棧S1中；

（2）如果遇到的是左括号，則直接将該左括号加入到棧S2中；

（3）如果遇到的是右括号，那麼将棧S2中的運算符一次出棧加入到棧S1中，直到遇到左括号，但是該左括号出棧S2并不加入到棧S1中；

（4）如果遇到的是運算符，包括單目運算符和雙目運算符，我們按照下面的規則進行操作：

          （1）如果此時棧S2為空，則直接将運算符加入到棧S2中；

          （2）如果此時棧S2不為空，目前周遊的運算符的優先級大于等于棧頂運算符的優先級，那麼直接入棧S2；

          （3）如果此時棧S2不為空，目前周遊的運算符的優先級小于棧頂運算符的優先級，則将棧頂運算符一直出棧加入到棧S1中，直到棧為空或者遇到一個運算符的優先級小于等于目前周遊的運算符的優先級，此時将該運算符加入到棧S2中；

（5）直到周遊完整個中序表達式之後，棧S2中仍然存在運算符，那麼将這些運算符依次出棧加入到棧S1中，直到棧為空。

       按照上面的五條操作反複進行完成，那麼棧S1中存放的就是逆波蘭表達式。

2、利用逆波蘭表達式求值

       利用逆波蘭表達式求計算式的值其實很簡單，正式因為這一點，是以逆波蘭表達式才在編譯原理中被用于計算一個表達式的值。

       下面來具體看看如何求一個逆波蘭表達式的值：

       我們此時維護一個資料結果棧S3，我們将會看到該棧中最後存放的是最終的表達式的值。我們從左至右的周遊棧S1，然後按照下面的規則進行操作棧S3.

（1）如果遇到的是數字，那麼直接将數字壓入到S3中；

（2）如果遇到的是單目運算符，那麼取S3棧頂的一個元素進行單目運算之後，将結果再次壓入到棧S3中；

（3）如果遇到的是雙目運算符，那麼取S3棧頂的兩個元素進行，首先出棧的在左，後出棧的在右進行雙目運算符的計算，将結果再次壓入到S3中。

       按照上面的三個規則，周遊完整個棧S1，那麼最後S3中的值就是逆波蘭表達式的值了，是以我們可以看出來使用逆波蘭表達式進行求值是很簡單的，隻有兩種操作要麼是直接壓棧，要麼是運算之後将結果壓棧。

reference：中綴表達式求值問題

C/C++基本文法學習

STL

C++ primer