具有標記列表的解釋器遞歸波蘭表示法

我有解釋波蘭表示法的解釋器。我擁有令牌中的所有操作和數字，並且我有一個令牌列表。因此，例如- - 5 4 2是與這些標記列表：具有標記列表的解釋器遞歸波蘭表示法

SubtractionToken，SubtractionToken，NumberToken，NumberToken，NumberToken，STOPToken。

例令牌：

class SubstractToken : IBinaryOperation 
{ 
    public Number Interpret(Number value1, Number value2) 
    { 
     Number c = new Number(value1.Value() - value2.Value()); 
     return c; 
    } 
} 

class Number : IToken 
{ 
    private int value; 

    public Number(int val) 
    { 
     value = val; 
    } 

    public int Value() 
    { 
     return value; 
    } 

}

所以，我無法理解如何讓遞歸函數來解決這個問題。因爲當我SubstractionToken.Inrerpret（值，值）我需要從numberTokens給出的值應該從自身減去，但如果下一個標記是操作標記會發生什麼？或者我們有- 5 - 7 2？我不知道如何實現這樣的遞歸函數，它會檢測到第一個操作應該被執行 - 7 2 then - 5並返回結果（ - 7 2），記住結果並回到先前未完成的操作。任何幫助？

來源

2016-05-25 Blabla

聽起來像你需要比解釋器更多的解析器。 – stuartd

@stuartd：OP可能試圖同時解析和解釋。 – IAbstract

看看[this]（http://codereview.stackexchange.com/questions/48632/math-equation-as-string-to-reverse-polish-notation-parser）。我在2年前寫了這個作爲一個學習項目。它當然可以改進，但它應該有所幫助。 – JRLambert

您通常使用評估堆棧來存儲您迄今爲止看到的結果。當你在輸入中遇到一個數字時，你將它壓入堆棧，當你遇到二進制操作時（例如' - '），你從堆棧中彈出兩個值，解釋它們並推送結果。類似於：

public static Number Evaluate(List<IToken> tokens, Stack<Number> eval) { 
    if(tokens.Count == 0) { 
     if(eval.Count != 1) throw new InvalidArgumentException("Invalid expression"); 
     return eval.Pop(); 
    } 
    var tok = tokens[tokens.Count-1]; 
    tokens.RemoveAt(tokens.Count-1); 
    if (tok is Number) { 
     eval.Push(tok); 
    } 
    else if(tok is IBinaryOperation) { 
     var result = ((IBinaryOperation)tok).Evaluate(eval.Pop(), eval.Pop()); 
     eval.Push(result); 
    } 
    //handle other cases 
    return Evaluate(tokens, eval); 
}

如果需要，可以很容易地將其作爲迭代函數。

來源

2016-05-25 16:24:06 Lee

雖然沒有優先順序。不確定哪裏適合OP的範圍。 – IAbstract

好的，我需要什麼，如果我也有一元操作？如果我加上'else if（tok is IUnaryOperation）{var result =（（IUnaryOperation）tok）.Evaluate（eval.Pop（））; eval.Push（結果）'？ – Blabla

@IAbstract - RPM中沒有優先順序。可能存在源語法，但解析器會處理該語法。 – Lee

看來你試圖解釋沒有括號的波蘭語前綴，所以你必須知道每個操作符的操作數（沒有其他參數）。 STOPToken是多餘的，也許只是爲了捕捉短或長的表達式？

當你eval你的令牌列表，它碰巧是SubtractionToken你從列表中彈出它並運行eval兩次（每個參數一個），結果應用你的功能並返回答案。

例子：如果令牌- - 2 3 4 X

top is -, takes two arguments 
    top is -, takes two arguments 
    top is 2 
    top is 3, we have 2 arguments apply 
    5 
    top is 4, we have two arguments apply 
9 , finished (X is left on stack) 
check if X is the top to ensure the expression is valid

也許停止用振振有辭是現在- - 5 X

top is -, takes two arguments 
    top is -, takes two arguments 
    top is 5 
    top is X --> throw exception since the stop token is illegal as argument

用於可變數據結構，你只是彈出令牌關閉，但對於功能版本您需要返回值和，仍然可以讀取的令牌和第二個eval需要使用該值來獲取它的表達式，否則您將讀取相同的表達兩次。

來源

2016-05-25 17:08:55 Sylwester

具有標記列表的解釋器遞歸波蘭表示法

回答

相關問題