這一部分是王道書上沒有的內容，根據視頻內容整理
概念
Reverse Polish notation 逆波蘭運算式（后綴運算式）
Polish notation 波蘭運算式（前綴運算式）
中綴運算式：運算子在兩個運算元中間，（如：a+b）
后綴運算式：運算子在兩個運算元后面，（如：ab+）
前綴運算式：運算子在兩個運算元前面，（如：+ab）
轉換和計算
中綴運算式轉后綴運算式（手算）
①確定中綴運算式中各個運算子的運算順序（運算順序不唯一，因此對應的后綴運算式也不唯一）
②選擇下一個運算子，按照（左運算元 右運算元 運算子）的方式組成一個新的運算元
③如果還有運算子沒被處理，就繼續②
“左優先”原則：只要左邊的運算子能先計算，就優先算左邊的
中綴運算式轉后綴運算式（機算）
初始化一個堆疊，用于保存暫時還不能確定運算順序的運算子
從左到右處理各個元素，直到末尾，可能遇到三種情況
①遇到運算元，直接加入后綴運算式
②遇到界限符，遇到“(”直接入堆疊，遇到")"則依次彈出堆疊內運算子并加入后綴運算式，直到彈出“(”為止，注意：“(”不加入后綴運算式
③遇到運算子，依次彈出堆疊中優先級高于等于當前運算子的運算子，并加入后綴運算式，若碰到“(”則停止，之后再把當前運算子入堆疊
按上述方法處理完所有字符后，將堆疊中剩余運算子依次彈出，并加入后綴運算式
后綴運算式的計算（手算）
從左往右掃描，每遇到一個運算子，就讓運算子前面最近的兩個運算元執行對應運算，
注意：兩個運算元的左右順序
后綴運算式的計算（機算）
①從左到右掃描下一個元素，直到處理完所有元素
②若掃描到運算元則壓入堆疊，并回到①，否則執行③（注意：先出堆疊的是“右運算元”）
③若掃描到運算子，則彈出兩個堆疊頂元素，執行相應運算，運算結果壓回堆疊頂，然后回到①，若運算式合法，則最后堆疊中只會留下一個元素，就是最終結果
中綴運算式轉前綴運算式（手算）
①確定中綴運算式中各個運算子的運算順序
②選擇下一個運算子，按照（運算子 左運算元 右運算元）的方式組合成一個新的運算元
③如果還有運算子沒被處理，就繼續②
“右優先”原則：只要右邊的運算子能先計算，就優先算右邊的
前綴運算式的計算（手算）
①從右往左掃描下一個元素，直到處理完所有元素（注意：先出堆疊的是“左運算元”）
②若掃描到運算元則壓入堆疊，并回到①，否則執行③
③若掃描到運算子，則彈出兩個堆疊頂元素，執行相應運算，運算結果壓回堆疊頂，回到①
中綴運算式的計算（機算）（重點）
初始化兩個堆疊，運算元堆疊和運算子堆疊
若掃描到運算元，則壓入運算元堆疊
若掃描到運算子或界限符，則按照“中綴轉后綴”相同邏輯壓入運算子堆疊（期間也會彈出運算子，每當彈出一個運算子時，就需要再彈出兩個運算元堆疊中的堆疊頂元素，并執行相應計算，運算結果再壓回運算元堆疊）
參考文獻
[1]王道論壇. 2022年資料結構考研復習指導[M]. 北京：電子工業出版社，2021.1
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/263366.html
標籤：其他