【0】README

0.1） 本文旨在總結 中綴表達式轉后綴表達式并計算后綴表達式的值 的步驟，并給出源代碼實現；
0.2） 本文中涉及到的源代碼均為原創，是對中綴轉后綴和計算后綴的簡單實現，（旨在理清它的原理），故源代碼中 考慮的數字是一位整型數（因為如果是兩位數及以上的話，還涉及到字符串轉int類型，雖然，我們沒有加入其功能，但是還是定義了相關的函數，給出了接口的，朋友需要的話，可以自行實現）、還有就是 運算符的話，只考慮到了 *、+、（、），同樣，如果朋友些需要的話，可以自行增加case 語句 or if 語句添加上即可；
0.3） 需要注意的是，操作數operand 和 操作符（運算符）operator 只能用char 類型將它們區分開；在中綴轉后綴的過程中，只能用char類型的空間來存儲它們的ASCII值（當然int空間也可以，也是存儲它們的ASCII值）；
0.4） 在計算后綴的過程中，需要把數字字符串（如123，它的ASCII序列為 49 50 51）轉為int 類型或其他數據類型，所以本文中的源代碼只處理 一位 整數的情況；朋友需要的話，自行添加；
0.5） 對于寫算法代碼的感悟， 重在理清算法原理 or idea，不要把輸入輸出的各種情況都考慮到， 那樣很累，很燒精力，影響學習進度；其實只要實現了其 簡單版本，實現復雜情況 也不是那樣難；總之一句話，學習期間，我們不追求完美，一切從簡，重在理解算法idea；
0.6） 題外話，曾經看到一位前輩說，棧有兩種實現方法——數組實現+鏈表實現， 說在工作中，棧的數組實現應用的比較多，鏈表實現基本不怎么用，所以，你知道側重點在哪里了；（當然可以 看看 棧的鏈表實現 了解了解）

---

【1】中綴到后綴的轉換

1.1）此方法需要遵循幾個規則（Rule）：

• R1）如果讀入操作數，則直接放入輸出字符串；
• R2）如果讀入一般運算符如+-*/，則放入堆棧，但是放入堆棧之前必須要檢查棧頂，并確定棧頂運算符的優先級比放入的運算符的優先級低；如果放入的優先級較低或兩者相等的話，則需要將棧頂的運算符先放入輸出字符串， 然后再將剛讀入的運算符壓棧；
• R3）如果讀入(，因為左括號優先級最高，因此放入棧中，但是注意，當左括號放入棧中后，則優先級最低；
• R4）如果讀入），則將棧中運算符取出放入輸出字符串，直到取出（為止，注意：（）不輸出到輸出字符串；
• R5）順序讀完表達式，如果棧中還有操作符，則彈出，并放入輸出字符串；

1.2）看個荔枝【 將中綴表達式：a + b * c + (d * e + f) * g 轉換為 后綴表達式： a b c * + d e * f + g * + 】
我們來看轉換步驟：

• step1）讀入a，a被輸出；讀入+， 由于操作符棧空，故+進棧；讀入b，b被輸出；棧和輸出的狀態如下：
  

• step2）讀入*，由于棧頂+的優先級小于*，故*進棧；讀入c，c被輸出；棧和輸出的狀態如下：
  

• step3）讀入+，由于棧頂*的優先級大于+，*出棧被送往輸出；有由于棧頂+的優先級等于+，+出棧被送往輸出；棧和輸出的狀態如下：
  
• step4）讀入（，由于（的優先級最高，故（進棧；讀入d，d被輸出；棧和輸出的狀態如下：
  
• step5）讀入*，由于（和）不會被輸出，故*進棧；讀入e，e被輸出；棧和輸出的狀態如下：
  
• step6）讀入+， 由于棧頂*的優先級大于+，故*出棧被送往輸出；然后+進棧；讀入f，f被輸出；棧和輸出的狀態如下：
  
• step7）讀入），將棧中運算符出棧并被輸出，直到取出（為止，而（和）不會被輸出；棧和輸出的狀態如下：
  
• step8）讀入*， 由于棧頂+的優先級小于*，故*進棧；讀入g，g被輸出；棧和輸出的狀態如下：
  

• step9）讀完表達式后，棧中還有操作符，將它們出棧，并放入到輸出字符串；棧和輸出的狀態如下：
  

• 中綴轉后綴的源代碼： https://github.com/pacosonTang/dataStructure-algorithmAnalysis/tree/master/chapter3/p54_infix_to_postfix
  

---

【2】計算后綴表達式

2.1）后綴表達式定義： 4.99*1.06 + 5.99 + 6.99*1.06 轉換為后綴表達式為： 4.99 1.06 * 5.99 + 6.99 1.06 * +；這種記法叫做 后綴 或者 逆波蘭 記法；

2.2） 計算一個后綴表達式花費的時間是O（N）；

2.3）計算后綴表達式規則（Rules）：

• R1） 如果是操作數，則放入棧中；
• R2） 如果是操作符（運算符），則取出棧中兩個操作數，進行運算后，將結果放入棧中；
• R3） 直到最后棧中只有一個元素，此元素就是計算結果；

2.4）看個荔枝（計算后綴表達式 1 2 3 * + 4 5 * 6 +7 * + ）

• 我們看處理步驟：
• step1）1、2、3進棧，結果如下：
  
• step2）下面讀到一個*， 所以2、3彈出， 將它們的積6壓棧，結果如下：
  
• step3）下面讀到一個+，所以1、6彈出，將它們的和7壓棧，結果如下：
  
• step4）下面讀到 4、5 ， 將它們壓棧，結果如下：
  
• step5）下面讀到一個*，所以4、5彈出，將它們的積20壓棧，結果如下：
  
• step6）下面讀到6，所以6壓棧，結果如下：
  
• step7）下面讀到一個+，所以20、6彈出，將它們的和26壓棧，結果如下：
  
• step8）下面讀到7，所以7壓棧，結果如下：
  
• step9）下面讀到一個*，所以26、7彈出，將它們的積182壓棧，結果如下：
  
• step10）下面讀到一個+，所以7、182彈出，將它們的和189壓棧，結果如下：
  

• step11）最后棧中就只有一個元素189了，所以結果就是189，并將其返回到主函數；

• 計算后綴表達式（只考慮‘+’和 ‘*’） 的源代碼：
  https://github.com/pacosonTang/dataStructure-algorithmAnalysis/tree/master/chapter3/p52_compute_postfix

• • Attention）當一個表達式以 后綴記號 給出時，沒有必要知道任何優先級規則， 這是一個明顯的優點；
    

總結

以上是生活随笔為你收集整理的栈应用（中缀表达式转后缀表达式并计算后缀表达式的值）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。