計算
運用後綴表達式進行計算的具體做法:
建立一個棧S 。從左到右讀表達式,如果讀到運算元就將它壓入棧S中,如果讀到n元運算符(即需要參數個數為n的運算符)則取出由棧頂向下的n項按運算元運算,再將運算的結果代替原棧頂的n項,壓入棧S中 。如果後綴表達式未讀完,則重複上面過程,最後輸出棧頂的數值則為結束。
轉換
計算機實現轉換:
將中綴表達式轉換為後綴表達式的算法思想:
·開始掃描;
·數字時,加入後綴表達式;
·運算符:
a. 若為 '(',入棧;
b. 若為 ')',則依次把棧中的的運算符加入後綴表達式中,直到出現'(',從棧中刪除'(' ;
c. 若為 除括弧外的其他運算符, 當其優先權高於除'('以外的棧頂運算符時,直接入棧。否則從棧頂開始,依次彈出比當前處理的運算符優先權高和優先權相等的運算符,直到一個比它優先權低的或者遇到了一個左括弧為止,然後將其自身壓入棧中(先出後入)。
·當掃描的中綴表達式結束時,棧中的的所有運算符出棧;
人工實現轉換
這裡我給出一個中綴表達式:a+b*c-(d+e)
第一步:按照運算符的優先權對所有的運算單位加括弧:式子變成了:((a+(b*c))-(d+e))
第二步:轉換前綴與後綴表達式
前綴:把運算符號移動到對應的括弧前面
則變成了:-( +(a *(bc)) +(de))
把括弧去掉:-+a*bc+de 前綴式子出現
後綴:把運算符號移動到對應的括弧後面
則變成了:((a(bc)* )+ (de)+ )-
把括弧去掉:abc*+de+- 後綴式子出現
發現沒有,前綴式,後綴式是不需要用括弧來進行優先權的確定的。如表達式:3+(2-5)*6/3
後綴表達式 棧
3_________________+
3 ________________+(
3 2 _______________+(-
3 2 5 -_____________ +
3 2 5 - _____________+*
3 2 5 - 6 * ___________+/
3 2 5 - 6 *3 __________+/
3 2 5 - 6 *3 /+________
("_____"用於隔開後綴表達式與棧)
另外一個人認為正確的轉換方法:
遍歷中綴表達式的每個節點,如果:
1、 該節點為運算元:
直接拷貝進入後綴表達式
2、 該節點是運算符,分以下幾種情況:
A、 為“(”運算符:
壓入臨時堆疊中
B、 為“)”運算符:
不斷地彈出臨時堆疊頂部運算符直到頂部的運算符是“(”為止,從棧中刪除'('。並把彈出的運算符都添加到後綴表達式中。
C、 為其他運算符,有以下步驟進行:
比較該運算符與臨時棧棧頂指針的運算符的優先權,如果臨時棧棧頂指針的優先權大於等於該運算符的優先權,彈出並添加到後綴表達式中,反覆執行前面的比較工作,直到遇到一個棧頂指針的優先權低於該運算符的優先權,停止彈出添加並把該運算符壓入棧中。
此時的比較過程如果出現棧頂的指針為‘(’,則停止循環並把該運算符壓入棧中,注意:‘(’不要彈出來。
遍歷完中綴表達式之後,檢查臨時棧,如果還有運算符,則全部彈出,並添加到後綴表達式中。
代碼
c++代碼
pascal代碼
Java代碼
求值
後綴表達式的求值 pascal
註:輸入時符號和數字要空一格