一些思考…
上一篇文章中，我們在遇到與符號堆疊堆疊頂優先級相同的符號相同或不變的符號時，會進行數字堆疊和符號堆疊分別彈堆疊→運算→壓堆疊的操作，這是為什么呢？為什么不可以不彈堆疊運算，等到計算式掃描完成之后再統一進行彈堆疊運算呢？
—這種演算法看似簡化了時間復雜度，但是會遇到運算順序的問題，
考慮下面兩種情景：
- 1-2-3=？: 掃描完成后，如果按照先壓堆疊，到最后統一彈堆疊的方法，我們的數字堆疊為[1,2,3], 符號堆疊為[-，-]，此時運算結果為: 2-3=-1, 1-(-1)=2. 顯然錯誤
- 1/2/3=？：掃描完成后，運算順序實則為 1/(2/3)=3/2，同樣錯誤
為什么存在這種問題呢？很簡單，最后彈堆疊的操作改變了運算的順序，在接下來的后綴運算式轉換中同樣存在一個問題
中綴→后綴
思路
將思想“遇到優先級相同或更低的元素直接計算，遇到優先級更高的不進行運算”的思想轉化成一個運算式，根據運算該運算式得到最終值
方法
換湯不換藥，但是后綴運算式的突出優點是，沒有括號！！，我們這次考慮中綴運算式中存在符號的情景，來體會后綴運算式的優越性╰(°▽°)╯
- 建立一個堆疊快取結構
- 遇到數字直接輸出
- 遇到符號，如果堆疊為空則先壓堆疊，如果不為空，則比較堆疊頂元素和該符號的優先級：
3.1如果該符號優先級較大，則直接將該符號壓入堆疊中
3.2 如果該符號優先級和堆疊頂符號優先級相同或更小，則先彈出堆疊頂元素，輸出，再將該符號壓堆疊
3.3 如果堆疊頂為括號，則不彈堆疊 - 遇到左括號 ( 則直接壓堆疊
- 遇到右括號 **）**則輸出所有堆疊內符號，直到遇到左括號（ 注意左右括號都不輸出到運算式中）
一個栗子
中綴運算式 （3-5） * （6+17 * 8）/ 3
按照上面的方法：
- 左括號壓堆疊
- 3輸出
- 負號“-”壓堆疊
- 5輸出
- 遇到右括號—彈堆疊 運算式為“35-”
- 遇到乘號“*”，壓堆疊
- 遇到左括號，壓堆疊
- 6輸出
- 加號“+” ，此時堆疊頂為括號，按兵不動
- 17輸出
- 遇到乘號”*“，此時堆疊頂為加號，直接壓堆疊
- 8輸出
- 右括號，彈堆疊！此時運算式為：3 5 - 6 17 8 * +， 堆疊中只有一個乘號
- 遇到除號“/”，彈出乘號，壓入除號
- 輸出3
- 輸出除號，最終運算式為： 3 5 - 6 17 8 * + * 3/
后綴運算式的運算
后綴運算式的計算就很簡單了—
建立一個堆疊快取結構，遇到數字壓堆疊， 遇到符號則彈出堆疊頂兩個元素進行運算，再存入堆疊中，
第二個栗子
上一個栗子中的運算式： 3 5 - 6 17 8 * + * 3/
- 存入3，5
- 遇到“-”，彈出3，5，3-5=-2. 壓入-2
- 壓入6，17，8
- 遇到“”，彈出 17，8，178=136， 壓入136
- 遇到“+”，彈出6，136， 6+136=142，壓入142
- 遇到“*”，彈出-2，142，（-2）*142=-284
- 壓入3
- 遇到“/”，彈出-284，3，-284/3=-94.67
與中綴運算式運算結果相同，
代碼
懶得寫了，時間復雜度和空間復雜度均為O(n).
后記
很經典的題目，但是很有意思，思維要嚴謹，尋找其中的規律，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/265936.html
標籤：其他
下一篇：web前端開發之vue基礎