逆波蘭式演算法c

㈠ 逆波蘭式的舉例

下面以(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了。
逆波蘭式除了可以實現上述類型的運算，它還可以派生出許多新的演算法，數據結構，這就需要靈活運用了。逆波蘭式只是一種序列體現形式。

㈡ 逆波蘭式怎麼判斷優先順序

什麼是波蘭表達式
我們日常的運算表達式通常是如下形式，這種成為中綴表達式，也就是運算符在運算數的中間。這種表達式人類人容易識別，並根據其進行計算，但計算機識別這種表達式非常困難。
a + b * (c - d) + e/f
因此，1920年，波蘭科學家揚·武卡謝維奇（Jan ukasiewicz）發明了一種不需要括弧的計算表達式的表示法將操作符號寫在操作數之前，也就是前綴表達式，即波蘭式（Polish Notation, PN）。上述中綴表達式轉換為波蘭表達式的格式如下：
+a+*b-cd/ef
從上面表達式可以看出，運算符在2個運算數的前面，因此波蘭表達式也稱為前綴表達式。為了便於理解，我們給出一個具體的實例，這個實例將上面的字母換成具體的數字（1 + 2 * (4 - 3) + 6/2），這個結果很容易看出來，也就是1 + 2*1 + 3 = 6。然後我們看一下波蘭表達式的表示形式及運算過程。
+1+*2-4 3/ 6 2 // 從右向左掃描，當遇到運算符時計算其最近的右側2個運算數
+1+*2-4 3 3 //先計算最右側的數據，也就是 6/2=3
+1+*2 1 3 // 同理，4-3 = 1
+1+2 3 // 同理， 2*1= 1
+1+5
6
通過上面示例可以大概理解波蘭表達式的計算過程，上面的運算符和運算數就可以通過通用的數據結構進行計算（請自己思考一下，我們後面再介紹）。
什麼是逆波蘭表達式
前面了解了波蘭表達式，那什麼是逆波蘭表達式呢？波蘭表達式也成為前綴表達式，而逆波蘭表達式則成為後綴表達式，對比可以猜出來運算符在運算數後面的表達式就是逆波蘭表達式。上述表達式如果採用逆波蘭表達式則如下：
1 2 4 3 -*+ 6 2 / + //計算方式正好相反，也就是從左向右掃描
1 2 1 *+ 6 2 / +
1 2 + 6 2 / +
3 6 2 / +
3 3 +
6
從中綴表達式轉換為逆波蘭（後綴）表達式
從中綴表達式轉換為後綴表達式的流程如下描述。需要注意的是，經過處理之後，中綴表達式中的括弧將被消除，也就是只剩下+-*/數學運算符。
從左至右掃描一中綴表達式。
若讀取的是操作數，則判斷該操作數的類型，並將該操作數存入操作數堆棧
若讀取的是運算符
該運算符為左括弧"("，則直接存入運算符堆棧。
該運算符為右括弧")"，則輸出運算符堆棧中的運算符到操作數堆棧，直到遇到左括弧為止。
該運算符為非括弧運算符：
- 若運算符堆棧棧頂的運算符為括弧，則直接存入運算符堆棧。
- 若比運算符堆棧棧頂的運算符優先順序高，則直接存入運算符堆棧。
- 若比運算符堆棧棧頂的運算符優先順序低或者相等，則輸出棧頂運算符到操作數堆棧，並將當前運算符壓入運算符堆棧。
4. 當表達式讀取完成後運算符堆棧中尚有運算符時，則依序取出運算符到操作數堆棧，直到運算符堆棧為空。
將中綴表達式轉換成逆波蘭表達式過程中，特別要注意對於中綴標到式中括弧的處理。
要注意的，如果算符是"（"，無論入棧中棧頂級別（只看棧頂）為何直接入棧，所以，「(」的等級
只用於對其後入棧的算符進行優先順序比較，在「（」入棧時是無視優先順序的。
在遇到"）"時候找到最後進入的"（"，並把"（"前面所有的符號都壓入出棧。不能僅憑運算符的級別來判斷。
註： 逆波蘭用的優先順序有以下幾種， 等級從高到低分別是：
1.*
2.+ -
3.(
4.)
上面關於流程的表示文字比較多，看起悶指螞來可能比較頭疼。為了便於理解上述流程，我們依然通過上面的實例（1 + 2 * (4 - 3) + 6/2）進行介紹。在實際操作過程中需要一個棧和一個隊列，分別存儲運算符和操作數。

通螞埋過上面整個過程的描述，並結合演算法，相信大家對中綴表達式轉換為後綴表達式（波蘭表達式逗蠢）已經非常清楚了。
逆波蘭表達式的計算
逆波蘭表達式的計算就比較簡單了。以上面結果中的隊列為輸入，同時再准備一個棧用於運算。具體流程如下：
將隊列中的數據依次出隊，然後壓棧；
在出隊的過程中如果遇到運算符，則從棧中彈出2個運算數，分別作為右運算數和左運算數，進行運算；
將步驟2的運算結果入棧；
跳入步驟1，繼續進行出隊操作。
依然以上述內容為例進行介紹。
如圖1中第一行左側為形成的隊列，右側是一個空棧。將隊列中操作數依次出隊，入棧。

圖1 操作數入棧

在出隊的過程中遇到運算符（-），此時將操作數出棧進行運算（注意這里操作數的順序）。

圖2 進行運算

重復上述操作，直到將隊列中所有內容出隊。

圖3 整個運算過程

好了，今天先到這里，後續在介紹其它數據結構。