這是Shunting Yard的錯還是我自己的錯？

給出的表達式：這是Shunting Yard的錯還是我自己的錯？

1/2/3/4*5

它到達表達式的結尾，並嘗試乘出圖4和5第一因爲它開始彈出堆棧這是錯誤的。我不一定在做RPN，而只是當場評估。我怎樣才能防止這一點？

// Expression was completely read - so we should try and make sense of 
// this now 
while (operatorStack.size() != 0) { 
    ApplyOperation(operatorStack, operandStack); 
}

在這一點上，我開始關閉操作員和操作。由於乘法和除法具有相同的存在，所以它們以乘法開始。

的跟蹤：

1/2/3/4*5 
Applying * to 5 and 4 
Result: 20 
Applying/to 20 and 3 
Result: 3/20 
Applying/to 3/20 and 2 
Result: 40/3 
Applying/to 40/3 and 1 
Result: 3/40

來源

2013-11-04 Vaughan Hilts

我們應該怎麼知道？你沒有發佈任何代碼。 – 2013-11-04 22:07:05

一個基本愚蠢的問題。分流碼算法自1961年以來一直運行。 – EJP

@MikeW對不起，這是一個普遍的問題。允許我添加一些上下文... –

分流碼算法中有一點需要比較堆棧頂部的運算符的優先級和輸入流中運算符的優先級，並決定是否彈出堆棧（對您的情況評估堆疊的操作員），或者推入新的操作員。

如果比較結果爲<或<=，則會產生很大的差異。其中一個會產生左結合性，另一個會產生右結合性。既然你得到了正確的結合性，並且你想要左結合性，我猜（看不到你的代碼）你正在使用錯誤的比較運算符。

順便說一句，你的教授是非常正確的。沒有必要明確產生RPN，並且評估算法在到達輸入結束時確實會彈出整個堆棧。（RPN算法也會這樣做;評估算法只是一條捷徑。）

來源

2013-11-04 23:29:24 rici

輝煌！這正是問題所在。你如何知道這有點瘋狂。 ;） –

@VaughanHilts：經驗是一位好老師。 –

什麼operatorStack？分流碼算法產生的RPN是列表，不是堆棧。它從左到右進行處理，而不是FIFO，

來源

2013-11-04 22:14:53 EJP

嗨，我的教授告訴我們我們正在使用這種變體。經過進一步檢查，他的情況不盡相同。我們被告知在我們去之後進行評估 - 使用優先級將操作數彈回堆棧。當你到最後時，把它們都以相反的順序彈出來...顯然這是一個壞主意。 –

聽起來像你的教授正在生產真正的波蘭語（真正的Lukasiewicz）符號，不知何故，然後使用一個堆棧來扭轉它。當SYA已經生成正確的訂單時，我看不到這一點。你甚至不需要列表/堆棧，你可以評估而不是產生輸出。 – EJP

那麼，你是否暗示我應該轉換爲列表，然後從左至右閱讀？我認爲可能有副作用.. –

這是Shunting Yard的錯還是我自己的錯？

回答

相關問題