點擊藍色“五分鐘學算法”關注我喲

加個“星標”，一起學算法

后綴表達式，又稱逆波蘭式，指的是不包含括號，運算符放在兩個運算對象的后面，所有的計算按運算符出現的順序，嚴格從左向右進行(不再考慮運算符的優先規則)。

后綴表達式計算：
后綴表達式計算與前綴表達式類似，只是順序是從左至右，具體過程如下：
從左至右掃描表達式，遇到數字時，將數字壓入堆棧，遇到運算符時，彈出棧頂的兩個數，用運算符對它們做相應的計算(次頂元素 op 棧頂元素)，并將結果入棧；重復上述過程直到表達式最右端，最后運算得出的值即為表達式的結果

例如：后綴表達式為“2 3 + 4 × 5 -”計算過程如下：
??(1)從左至右掃描，將 2 和 3 壓入堆棧；
??(2)遇到 + 運算符，因此彈出 3 和 2( 3 為棧頂元素，2 為次頂元素，注意與前綴表達式做比較)，計算出 3+2 的值，得 5，再將 5 入棧；
??(3)將 4 入棧；
??(4)接下來是 × 運算符，因此彈出 4 和 5，計算出 4 × 5 = 20，將 20 入棧；
??(5)將 5 入棧；
??(6)最后是-運算符，計算出 20-5 的值，即 15，由此得出最終結果。

中綴表達式轉后綴表達式：
與轉換為前綴表達式相似，步驟如下：
??(1)初始化兩個棧：運算符棧s1和儲存中間結果的棧s2；
??(2)從左至右掃描中綴表達式；
??(3)遇到操作數時，將其壓s2；
??(4)遇到運算符時，比較其與 s1 棧頂運算符的優先級：
????a：如果 s1 為空，或棧頂運算符為左括號“(”，則直接將此運算符入棧；
????b：否則，若優先級比棧頂運算符的高，也將運算符壓入 s1(注意轉換為前綴表達式時是優先級較高或相同，而這里則不包括相同的情況);
????c：否則，將 s1 棧頂的運算符彈出并壓入到 s2 中，再次轉到(4)-(1)與s1中新的棧頂運算符相比較；
??(5)遇到括號時：
????a：如果是左括號“(”，則直接壓入 s1；
????b：如果是右括號“)”，則依次彈出 s1 棧頂的運算符，并壓入 s2 ，直到遇到左括號為止，此時將這一對括號丟棄；
??(6)重復步驟(2)至(5)，直到表達式的最右邊；
??(7)將 s1 中剩余的運算符依次彈出并壓入 s2；
??(8)依次彈出 s2 中的元素并輸出，結果的逆序即為中綴表達式對應的后綴表達式(轉換為前綴表達式時不用逆序)

例如，將中綴表達式“1+((2+3)×4)-5”轉換為后綴表達式的過程如下：

掃描到的元素s2(棧底->棧頂)s1 (棧底->棧頂)說明

1	1	空	數字，直接入棧
+	1	+	s1為空，運算符直接入棧
(	1	+ (	左括號，直接入棧
(	1	+ ( (	同上
2	1 2	+ ( (	數字
+	1 2	+ ( ( +	s1棧頂為左括號，運算符直接入棧
3	1 2 3	+ ( ( +	數字
)	1 2 3 +	+ (	右括號，彈出運算符直至遇到左括號
×	1 2 3 +	+ ( ×	s1棧頂為左括號，運算符直接入棧
4	1 2 3 + 4	+ ( ×	數字
)	1 2 3 + 4 ×	+	右括號，彈出運算符直至遇到左括號
-	1 2 3 + 4 × +	-	-與+優先級相同，因此彈出+，再壓入-
5	1 2 3 + 4 × + 5	-	數字
到達最右端	1 2 3 + 4 × + 5 -	空	s1中剩余的運算符

得到的最終結果為：“ 1 2 3 + 4 × + 5 - ”

END

推薦閱讀：

• 蓋爾-沙普利算法告訴你，你的對象在哪里？

• 面試官，我會寫二分查找法！對，沒有 bug 的那種！

• 如何有效的寫算法題

• 幾道 BAT 算法面試中經常問的「字符串」問題

• 鏈表算法面試問題？看我就夠了！

歡迎長按下圖關注公眾號五分鐘學算法，一起看動畫學算法。

總結

以上是生活随笔為你收集整理的前缀表达式后缀表达式_五分钟小知识之什么是后缀表达式的全部內容，希望文章能夠幫你解決所遇到的問題。

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