之前在學習棧的時候老師講過這個問題

　　思路就是：

　　　　1.將表達式（中綴式）轉化成后綴式；

　　　　2.進行后綴式的計算。

?　　思路看起來很簡單，但是實際在敲代碼的時候還是要注意很多問題。下面分享一下個人做法，可以改進之處還希望大家可以指出來，共同進步！

　　一：將中綴式轉化為后綴式

　　個人采用的是邊輸入邊進行處理：首先設置兩個棧，一個是后綴式棧，一個是符號棧。如果是數字，直接放入到后綴式棧中；如果是符號：

　　(1)比較算符優先級，如果符號棧的棧頂符號比將要進棧的符號優先級高，那么將符號棧的棧頂元素彈出，進入到后綴式棧中，接著進行棧頂元素和待進棧元素的比較，直到棧頂元素優先級比待進棧符號優先級低。如果符號棧的棧頂符號優先級低，則將將要進棧的符號壓入到符號棧中，稱為新的棧頂元素。以上涉及到了：算符優先級的比較，實現代碼如下：

紫框詳解：我們知道，‘(’的優先級是最高的，那么如果它作為棧頂元素與其他符號比較之后，會被彈出到后綴式棧。然而我們后綴式棧不希望有括號的出現，而符號棧希望括號可以保留，因為我們需要找到后面的‘)’與左括號進行配對。所以這里需要約定，如果棧頂元素是左括號，那么下一個符號直接進棧不進行比較。

?

　　以上是我們后綴式轉化的代碼。在suffix函數（轉化成后綴式）中，我們是邊輸入邊處理，如果是數字，直接進棧，調用isNum函數；如果是符號，調用isSymbol函數。

　　在isSymbol函數中，我們做的不僅僅是優先級的判斷，因為有括號這個特殊的符號存在，所以我們需要給予特殊考慮。在遇到右括號的時候，我們應該將符號棧中的元素彈出，直到遇到左括號，但是左括號不彈入到后綴式棧中。

　　如果不是右括號，我們就判斷優先級，但是在這之前，還需要做的一步就是設置分界符，我們這里使用的是'#'號。為什么設置分界符呢？我們知道，讀入表達式的時候使用的是char型，一個一個讀的，這樣產生的問題是，如果數字是10以內的，沒有影響，但是如果大于等于10，則會分成多部分讀入，例如23讀進來是2，3，在不同的數組單元中，那么操作數字的時候就不知道到底是一位數還是兩位數，所以我們需要‘#’號，后綴式的形式就成了：1#23#4#+......這樣子的，很容易區分操作數是幾位。

　　我第一次做的時候，忽略了一個問題：就是將符號棧的剩余元素全部壓入到后綴式棧中。因為在優先級比較之后，很多符號可能因為在操作順序中靠后，所以并沒有進入到后綴式中，因此千萬不能忘了他們的存在。

　　到這里，我們的后綴式轉換就完成了。工程相當于完成了一半，接下來就應該是后綴式的計算：

　　前面說到過了，我們后綴式中通過'#'號對數字進行了區分，那么我們進行計算的時候，先要把操作數準確的計算出來，放入到數字棧（num[]）中。

紅框詳解：對于轉之后的后綴式，計算操作數我想到的辦法是設置一個first和last指針，在first和last之間的是一個操作數，那么區分的標志就是，兩個操作數之間一定有若干個符號。

大家再對照著代碼，應該可以理解（可能這里我的方法比較麻煩，希望大家可以指點一二）

?下面我們就開始進行計算了：

這里還是比較簡單的，遇到數字就調用cul_num函數，進行數字的計算，遇到符號就進行符號運算。這里需要注意的就是我們first和last的設置。此外，還應該考慮一下特殊的情況，我當時出現的一個問題就是：

例如：1#2#3-#4...進行到‘-’減號的時候程序就崩掉了，后來想想明白了問題所在，當last指向減號的時候，執行減法功能，然后i++，那么這個時候，指向的是后綴式棧中的‘#‘號，而在calculate函數中，沒有對＃的相關處理，所以程序崩了。分析得到：我們并不需要＃，所以再i++，指向后綴式棧中的下一個元素。這就是我上面代碼注釋的“忽略了”這里的含義。

?

?

?

?

（本人第一次寫博客，不到之處還希望大家批評指正，我會繼續努力！共勉！）

?

總結

以上是生活随笔為你收集整理的蓝桥杯_算法训练_表达式计算的全部內容，希望文章能夠幫你解決所遇到的問題。

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