內容來自尚硅谷Java數據結構與java算法（Java數據結構與算法）_嗶哩嗶哩_bilibili

寫在前面:本文內容大致和原視頻內老師的筆記內容相同，會偶爾插入自己的注釋和理解，盡量會完成作業(yè)

本次有一個加入括號的作業(yè)，但是老師提到了后面會講，所以當時想了一小會，然后決定繼續(xù)學習[del]其實就是不會[/del]

5.5棧實現綜合計算器(中綴表達式)

使用棧來實現綜合計算器

請輸入一個表達式

計算式:[7*2*2-5+1-5+3-3]

思路分析(圖解):

代碼實現

1.???? 先實現1位數的運算

2.???? 擴展到多位數的運算

5.6逆波蘭計算器

1.????? 輸入一個逆波蘭表達式(后綴表達式)，使用棧(Stack)，計算其結果

2.????? 支持小括號和多位數整數，因為這里我們主要講的是數據結構，因此計算器進行簡化，只支持對整數的計算。

3.????? 思路分析

例如:(3+4)×5-6對應的后綴表達式就是34+5 ×6-，針對后綴表達式求值步驟如下:

Step1.從左至右掃描，將3和4壓入堆棧;

Step2.遇到+運算符，因此彈出4和3(4為棧頂元素，3為次頂元素），計算出3+4的值，得7，再將7入棧;

Step3.將5入棧;

Step4.接下來是*運算符，因此彈出5和7，計算出7×5=35，將35入棧;

Step5.將6入棧;

最后是-運算符，計算出35-6的值，即29，由此得出最終結果

4.????? 代碼完成

5.7中綴表達式轉換為后綴表達式

大家看到，后綴表達式適合計算式進行運算，但是人卻不太容易寫出來，尤其是表達式很長的情況下，因此在開發(fā)中，我們需要將中綴表達式轉成后綴表達式。

5.7.1具體步驟如下:

1.初始化兩個棧:運算符棧s1和儲存中間結果的棧s2;

2.從左至右掃描中綴表達式;

3.遇到操作數時，將其壓s2;

4.遇到運算符時，比較其與s1棧頂運算符的優(yōu)先級:

4.1如果s1為空，或棧頂運算符為左括號“(”，則直接將此運算符入棧;

4.2否則，若優(yōu)先級比棧頂運算符的高，也將運算符壓入s1;

4.3否則，將s1棧頂的運算符彈出并壓入到s2中，再次轉到(4-1)與s1中新的棧頂運算符相比較;

5.遇到括號時:

5.1如果是左括號“(”，則直接壓入s1

5.2如果是右括號“)"，則依次彈出s1棧頂的運算符，并壓入s2，直到遇到左括號為止，此時將這一對括號丟棄

6.重復步驟2至5，直到表達式的最右邊

7.將s1中剩余的運算符依次彈出并壓入s2

8.依次彈出s2中的元素并輸出，結果的逆序即為中綴表達式對應的后綴表達書

5.7.2舉例說明

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

此結果為:”1 2 3 + 4 * + 5 -”

5.7.3代碼實現中綴表達式轉為后綴表達式

思路分析

代碼實現：