前綴運算式
前綴運算式（波蘭式）是一種沒有括號的算術運算式，與中綴運算式不同的是，其將運算子寫在前面，運算元寫在后面，即二元運算子總是置于與之相關的兩個運算物件之前，
中綴運算式
中綴運算式是一個通用的算識訓邏輯公式表示方法， 運算子是以中綴形式處于運算元的中間（如：1+2），也就是我們平時常用的算術表示方法，
后綴運算式
后綴運算式（逆波蘭式）則是將運算子置于與之相關的兩個運算物件之后，
前綴運算式和后綴運算式求值
前綴運算式求值
從右至左掃描運算式
遇到數字時，將數字壓入堆疊，遇到運算子時，彈出堆疊頂的兩個數，用運算子對它們做相應的計算（堆疊頂元素 op 次頂元素），并將結果入堆疊
重復上述程序直到運算式最左端，最后運算得出的值即為運算式的結果
示例：
計算前綴運算式的值：+ 1 × - 3 2 4
(1)從右至左掃描，將4，2，3壓入堆疊
(2)遇到-運算子，彈出3和2（3為堆疊頂元素，2為次頂元素），計算3-2的值，得到1，
將1壓入堆疊
(3)遇到×運算子，彈出1和4，計算1×4的值，得到4，將4壓入堆疊
(4)遇到1，將1壓入堆疊
(5)遇到+運算子，彈出1和4，計算1+4的值，得到5為最終結果
后綴運算式求值
與前綴運算式求值類似，不過順序是從左至右掃描運算式
遇到數字時，將數字壓入堆疊，遇到運算子時，彈出堆疊頂的兩個數，用運算子對它們做相應的計算（次頂元素op 堆疊頂元素 ），并將結果入堆疊
重復上述程序直到運算式最右端，最后運算得出的值即為運算式的結果
示例：
計算后綴運算式的值：1 3 2 - 4 × +
(1)從左至右掃描，將1，3，2壓入堆疊
(2)遇到-運算子，2和3彈出，計算3-2（這里注意不是2-3，是次頂元素 op 堆疊頂元素，所以是3-2，下面步驟的求值同理）的值，得到1，將1壓入堆疊
(3)遇到4，將4壓入堆疊
(4)遇到×運算子，彈出4和1，計算1×4的值，得到4，將4壓入堆疊
(5)遇到+運算子，彈出4和1，計算1+4的值，得到5即為最終結果
中綴運算式轉換為前綴運算式、后綴運算式
中綴運算式轉換為前綴運算式
轉換步驟如下:
初始化兩個堆疊:存盤運算子的堆疊1，儲存中間結果的堆疊2
(1)從右至左掃描中綴運算式
(2)遇到運算元時，將其壓入堆疊2
(3)遇到運算子時，比較其與堆疊1的堆疊頂運算子的優先級：
①若是堆疊1為空，或堆疊頂運算子為右括號“)”，則直接將此運算子入堆疊，若優先級比堆疊頂運算子更高或相等，也將運算子壓入堆疊1
②否則，將堆疊1的堆疊頂運算子彈出并壓入到堆疊2中，然后將其再次與堆疊1中新的堆疊頂運算子再次進行優先級的比較
(4)遇到括號時判斷：
①如果是右括號“)”，則直接壓入堆疊1
②如果是左括號“(”，則依次彈出堆疊1堆疊頂的運算子，并壓入堆疊2，直到遇到右括號為止，此時將這一對括號丟棄
(5)重復步驟(1)至(4)，直到運算式的最左邊
(6)將堆疊1中剩余的運算子依次彈出并壓入堆疊2，然后依次彈出堆疊2中的元素并輸出，結果即為中綴運算式對應的前綴運算式
中綴運算式轉換為后綴運算式
初始化兩個堆疊：存盤運算子的堆疊1，儲存中間結果的堆疊2；
(1)從左至右掃描中綴運算式
(2)遇到運算元時，將其壓入堆疊2
(3)遇到運算子時，比較其與堆疊1的堆疊頂運算子的優先級：
①若堆疊1為空，或堆疊頂運算子為左括號“(”，則直接將此運算子入堆疊；若優先級比堆疊頂運算子的高，也將運算子壓入堆疊1（注意轉換為前綴運算式時是優先級較高或相同，而這里則不包括相同的情況）
②否則，將堆疊1的堆疊頂運算子彈出并壓入到堆疊2中，然后將其與堆疊1中新的堆疊頂運算子再次進行優先級的比較
(4)遇到括號時判斷：
①如果是左括號“(”，則直接壓入堆疊1
②如果是右括號“)”，則依次彈出堆疊1堆疊頂的運算子，并壓入堆疊2，直到遇到左括號為止，此時將這一對括號丟棄
(5)重復步驟(1)至(4)，直到運算式的最右邊
(6)將堆疊1中剩余的運算子依次彈出并壓入堆疊2.依次彈出堆疊2中的元素并輸出，結果的逆序即為中綴運算式對應的后綴運算式（注意轉換為前綴運算式時不用逆序）
對于我們平時求中綴運算式轉換前綴運算式、后綴運算式，可以用下面這種簡單方便的方法得到結果：
(1)按照運算子的優先級對所有的運算單位加括號
(2)將運算子移動到其對應括號的前面（前綴運算式）或后面（后綴運算式），然后去掉所有括號，便可得到前綴或后綴運算式
示例：
中綴運算式為：1+(3-2)×4
加上括號后：( 1 + ( ( 3 - 2 ) × 4 ) )
將所有運算子移動到其對應的括號前面： + ( 1 × ( - ( 3 2 ) 4 ) )
去掉所有括號得到前綴運算式：+ 1 × - 3 2 4
同理可求后綴運算式：
將所有運算子移動到其對應的括號后面：( 1 ( ( 3 2 ) - 4 ) × ) +
去掉所有括號得到后綴運算式：1 3 2 - 4 × +
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/2193.html
標籤：其他
上一篇：0967. Numbers With Same Consecutive Differences (M)
下一篇：深入淺出二叉樹