理解逆向波蘭語法，作業作業？

Question

我被要求在C語言中編寫一個簡單的反向波蘭語記法計算器，作爲家庭作業的一部分。我很難理解RPN。你能幫我理解逆波蘭標誌嗎？此外，如何解決這個問題的任何提示將不勝感激。

Answer 1

你可以找到http://www.codeproject.com/KB/cs/Reverse_Polish_Notation.aspx

Answer 2

Reverse Polish Notation教程就是首先你寫的值寫入表達式的具體方式，則操作要執行。因此，例如，要添加數字3和4，您會寫3 4 +。

所以寫一個RPN計算器，你需要

• 接受輸入，如從控制檯的一種手段
• 的tokenizing輸入（A裝置，你在做什麼，上破空白是可能就足夠了）
• 甲stack用於存儲的值（操作數）（如圖3和4在上述）
• 操作的字典

然後循環將成爲在本質：

while (there's a token available) { 
    token = get_the_token 
    if (token is known operator) { 
     get the number of values from stack this operation requires (usually two); fail if stack doesn't have enough 
     perform operation on values 
     push result on the stack 
    } 
    else if (token is valid value) { 
     push it on the stack 
    } 
    else { 
     show error: invalid input 
    } 
} 
show result remaining on stack 

你可以看到爲什麼RPN使得編寫一個calcuator相當簡單：你不必擔心有他們所操作的值之間的運營商，而你不知道不需要使用小括號來進行分組，因爲您可以使用更常用的記號形式infix。例如，我們在中間記號中寫(10 + (4 * 2))/9，我們會在RPN中編寫10 4 2 * + 9 /。計算器會處理這樣的標記：

• 10：這是一個值，將其推到堆棧
• 4：這是一個值，將其推到堆棧
• 2：這是一個值，推它在堆棧上
• *：這是一個操作符，彈出窗口2和4離開堆棧並將它們相乘（4 * 2）;將結果（8）推送到堆棧上
• +：這是一個操作符，彈出8和10堆棧並添加它們（10 + 8）;堆棧
• 9上推的結果（18）：這是一個值，將其推到堆棧
• /：這是一個操作符，彈出9和18從堆棧中和將它們劃分（18/9）;在堆棧上推的結果（2）（注意，在堆疊  — 9的頂部的值，在這種情況下  —是除數，在它之下  —的下一個值是被除數）
• 輸入的結束，在堆棧上顯示的值（或多個）：2

Answer 3

Reverse Polish Notation是表示法，其中運營商按照操作數的數學表達式的形式。在評估RPN表達式時，每個二元運算符引用緊接在其之前之前的兩個操作數。藉此RPN表達，例如：

5 4 3 + * 

開始從左側的掃描表達，直到你來到第一家運營商，這是+。該運算符的操作數爲4和3（緊接它之前的那些），所以我們可以用結果7替換全部三個。 （請注意，括號不是必需的，但我正在使用它們來幫助澄清含義）。

5 (4 3 +) * => 5 7 * 

現在我們有運營商*，和兩個操作數5和7（這是真正的4 + 3的結果）。我們乘以5和7，整個表達式評估爲35。

5 7 * => 35 

這是評估任何RPN表達式的通用算法。

---

RPN表達式是特別適合用於通過使用被稱爲stack的數據結構的計算機計算結果爲。

堆棧是一個有序集合，其中一端指定爲「頂部」。項目總是添加到堆棧或從頂部的堆棧中移除。這樣，唯一要移除的項目始終是最近添加的項目。由於這個原因，堆棧有時被稱爲Last In First Out（或LIFO），因爲推入堆棧的最後一個元素位於頂部，因此將首先被刪除。

在C中，您可以實現一個包含兩個變量的堆棧：一個數組（足夠容納期望堆棧需要的最大數量的元素）以及一個指示數組中當前哪個索引位於頂部的整數。

堆棧非常適合評估RPN表達式，因爲當遇到運算符時，它總是適用於最近遇到的操作數。因此，當您從左側掃描表達式時，可以將操作數保存在堆棧中。再以我們的例子：

5 4 3 + * 

這裏的第一件事情是一個操作數（5），所以將其推送到堆棧（其初始爲空）。然後我們遇到4並將它推入堆棧。它成爲新的頂部。然後我們與3一樣。

5 4 3 <-- top 
+ * // Remaining expression 

接下來我們遇到了+運算符。我們知道它適用於以前遇到的操作數，但我們在哪裏可以找到它們？當然，在堆棧頂部！從堆棧彈出3和4，並添加它們以獲得7。但是如何處理結果呢？那麼，它可能是操作數另算，所以將其推回棧上（就像我們更換了操作數和運算符的結果，當我們評估用手錶達）：

5 7 <-- top 
* // Remaining expression 

現在我們看到* 。再一次，最近遇到的操作數是堆棧中的兩個最高操作數。我們彈出它們並乘法得到35，然後將它推回棧上。

35 <-- top 
// No expression remaining 

在這一點上，我們已經達到了表達式的結束和堆棧上的唯一的事情就是結果。我們完成了！您可以看到操作數堆棧如何「保存」遇到的第一個操作數，直到遇到相應的操作符（可能位於表達式的另一端）。

如果我們想走到了盡頭，發現還剩下的堆棧多個號碼，會告訴我們，有在表達操作數​​過多而沒有足夠的運營商。另一方面，如果我們在某個時間遇到了一個操作符，並且在堆棧中的操作數少於兩個，我們就會知道該表達式中操作符太多且操作數不足。

Answer 4

你可以在http://expressionoasis.vedantatree.com/找到一個簡單的實現