RPN短路評估

我現在正在製作一個簡單的字節碼解釋器，它使用RPN表達符號和真正的後綴表示法，但現在我的問題是：短路評估實際上可以用於後綴表達式？例如，在評估表達式時（錯誤的& &（factorial（7）> factorial（5）））C++知道運算符在兩個操作數上的結果甚至到達第二個操作數之前的結果爲false，因爲（false & &什麼）總是等於假。現在，當你把它放在RPN中時，你會得到（假（7階乘5階乘>）& &）。RPN短路評估

我想構建一個高效的RPN表達式解析器，所以問題是這樣的：我如何製作一個高效的RPN表達式解析器並進行短路評估？

來源

2016-07-22 Imanuel Habekotte

您可以編寫代碼。我們不是爲你設計你的系統，或是教你如何設計它。 –

@MarcB感謝您提供的信息。無論如何，我確實得到了一個有用的答案，所以是的。 –

RPN和postfix符號是相同的東西，而不是兩個不同的東西。您不會將RPN解析器構建到解釋器中。輸入已被解析並可以線性處理。如果你想短路評估，你需要引入分支。 – EJP

您會評估一個RPN表達式的兩個階段。

階段1：解析RPN，並構建RPN的樹形表示。因此，在此樹中，例如，&&節點對於表達式的每一半都有兩個子節點。構建此樹與評估RPN幾乎完全相同，除了評估部分被構建新節點的操作替換，並將其子節點鏈接到其新父節點，然後將父節點推回RPN評估堆棧。

階段2：使用遞歸下降評估構建的樹。此時，短路評估變得微不足道：評估&&的左側孩子，然後決定是否真的要評估右側孩子。

同上||節點等...

來源

2016-07-22 16:52:57

謝謝你是完美的！ :) –

問題：如果我改用PN代替RPN，會不一樣嗎？ –

第一階段當然會有所不同。構建樹的不同邏輯。或者，可以編寫PN解析器，以便它帶有「忽略」標誌，它只解析和吞下輸入，不進行評估，遞歸地向下傳遞標誌;如果左側評估使得評估右側不必要，那麼使用&&'和'||'運算符爲右側評估設置標誌。 –

回答

相關問題