定義

　　逆波蘭式（Reverse Polish notation，RPN，或逆波蘭記法），也叫后綴表達式(將運算符寫在操作數之后)?
　　如：我們平時寫a+b，這是中綴表達式，寫成后綴表達式就是：ab+?
　　(a+b)*c-(a+b)/e的后綴表達式為：?
　　(a+b)*c-(a+b)/e?
　　→((a+b)*c)((a+b)/e)-?
　　→((a+b)c*)((a+b)e/)-?
　　→(ab+c*)(ab+e/)-?
　　→ab+c*ab+e/-

算法實現

　　將一個普通的中序表達式轉換為逆波蘭表達式的一般算法是：
　　(1)首先構造一個運算符棧，此運算符在棧內遵循越往棧頂優先級越高的原則。
　　(2)讀入一個用中綴表示的簡單算術表達式，為方便起見,設該簡單算術表達式的右端多加上了優先級最低的特殊符號“#”。
　　(3)從左至右掃描該算術表達式，從第一個字符開始判斷，如果該字符是數字，則分析到該數字串的結束并將該數字串直接輸出。
　　(4)如果不是數字，該字符則是運算符，此時需比較優先關系。
　　做法如下：將該字符與運算符棧頂的運算符的優先關系相比較。如果，該字符優先關系高于此運算符棧頂的運算符，則將該運算符入棧。倘若不是的話，則將棧頂的運算符從棧中彈出，直到棧頂運算符的優先級低于當前運算符，將該字符入棧。
　　(5)重復上述操作(1)-(2)直至掃描完整個簡單算術表達式，確定所有字符都得到正確處理，我們便可以將中綴式表示的簡單算術表達式轉化為逆波蘭表示的簡單算術表達式。

逆波蘭式的作用

　　對于實現逆波蘭式算法，難度并不大，但為什么要將看似簡單的中序表達式轉換為復雜的逆波蘭式？原因就在于這個簡單是相對人類的思維結構來說的，對計算機而言中序表達式是非常復雜的結構。相對的，逆波蘭式在計算機看來卻是比較簡單易懂的結構。因為計算機普遍采用的內存結構是棧式結構，它執行先進后出的順序。
　　下面以(a+b)*c為例子進行說明：
　　(a+b)*c的逆波蘭式為ab+c*，假設計算機把ab+c*按從左到右的順序壓入棧中，并且按照遇到運算符就把棧頂兩個元素出棧，執行運算，得到的結果再入棧的原則來進行處理，那么ab+c*的執行結果如下：
　　1）a入棧（0位置）
　　2）b入棧（1位置）
　　3）遇到運算符“+”，將a和b出棧，執行a+b的操作，得到結果d=a+b，再將d入棧（0位置）
　　4）c入棧（1位置）
　　5）遇到運算符“*”，將d和c出棧，執行d*c的操作，得到結果e，再將e入棧（0位置）
　　經過以上運算，計算機就可以得到(a+b)*c的運算結果e了。
　　逆波蘭式除了可以實現上述類型的運算，它還可以派生出許多新的算法，數據結構，這就需要靈活運用了。逆波蘭式只是一種序列體現形式。

程序實現

轉載于:https://blog.51cto.com/caixia/772433

總結

以上是生活随笔為你收集整理的PHP中的逆波兰式应用的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。