Interpreter Rekursive Polnische Notation mit Token-Liste

Question

Ich habe einen Interpreter, der die polnische Notation löst. Ich habe alle Operationen und Zahlen in Token und ich habe eine Liste von Token. So zum Beispiel - - 5 4 2 ist eine Liste mit diesen Token:

SubtractionToken, SubtractionToken, NumberToken, NumberToken, NumberToken, STOPToken.

Beispiel Token:

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; 
    } 

} 

Also, ich kann nicht verstehen, wie rekursive Funktion, um diese Probleme zu lösen. Denn wenn ich SubtractionToken.Inrerpret (Wert, Wert) muss ich die Werte geben von numberTokens was Subtrahieren von sich selbst sein sollte, aber was passiert, wenn das nächste Token ein Operationstoken ist? oder wir haben - 5 - 7 2? Ich weiß nicht, wie man eine solche rekursive Funktion implementiert, die erkennt, dass die erste Operation durchgeführt werden sollte - 7 2 dann - 5 und Ergebnis von (- 7 2), erinnere mich an die Ergebnisse und zurück an die vorherigen nicht durchgeführten Operationen. Irgendeine Hilfe?

Answer 1

Sie tun dies normalerweise mit einem Auswertungsstapel, der die Ergebnisse speichert, die Sie bisher gesehen haben. Wenn Sie in der Eingabe auf eine Zahl stoßen, drücken Sie sie auf den Stapel, und wenn Sie auf eine binäre Operation (z. B. '-') stoßen, blättern Sie zwei Werte aus dem Stapel, interpretieren Sie sie und drücken Sie das Ergebnis. Etwas wie:

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); 
} 

Dies könnte leicht eine iterative Funktion gemacht werden, falls erforderlich.

Answer 2

Es scheint, dass Sie versuchen, das polnische Präfix ohne Klammern zu interpretieren, so dass Sie die Anzahl der Operanden pro Operator kennen müssten (keine Restargumente). Der STOPToken ist überflüssig oder vielleicht nur um kurze oder lange Ausdrücke einzufangen?

Wenn Sie eval Ihre Liste von Tokens und es zufällig sein SubtractionToken Sie pop es aus der Liste und führen Sie Eval zweimal (eins für jedes Argument) und mit den Ergebnissen wenden Sie Ihre Funktion und die Antwort zurück.

Beispiel: Wenn die Token sind - - 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 

Vielleicht ist die reson für Haltestelle ist - - 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 

nun für eine veränderbare Datenstruktur Sie nur die Token aus Pop, aber für eine funktionsfähige Version Sie müssten sowohl die Werte als auch die Token zurückgeben, die noch gelesen werden können, und die zweite eval muss diese verwenden, um ihren Ausdruck zu holen, sonst werden Sie gelesen der gleiche Ausdruck zweimal.