So bewerten Sie einen Ausdruck in Präfix-Notation

Question

Ich versuche, eine Liste auszuwerten, die einen Ausdruck in Präfix-Notation darstellt. Hier ist ein Beispiel einer solchen Liste:

[+, [sin, 3], [- 10 5]] 

Was ist der beste Weg, um den Wert der Liste

Answer 1

Es wird einfacher, wenn Sie Postfix anstelle von Präfix verwenden. Siehe Reverse Polish Notation (RPN). Wenn ein Ausdruck in RPN gegeben ist, ist es leicht, dies mit nur einem Stapel zu bewerten.

Aber da Sie nach einer Möglichkeit gefragt Präfix Ausdrücke ohne Rekursion zu bewerten und unter Verwendung von Stapeln (für eine möglicherweise einfache Art und Weise, siehe EDIT: unten), hier ein Weg ist:

Wir zwei, dies mit tun Stapel.

Ein Stapel (nennen wir es Evaluation) enthält die Operatoren (wie +, sin etc) und Operanden (wie 3,4 usw.) und der andere Stapel (nennen wir Count) enthält ein Tupel der Anzahl der verbleibenden Operanden gesehen + die Anzahl der Operanden, die ein Operator erwartet.

Immer wenn Sie einen Operator sehen, schieben Sie den Operator auf den Auswertungs-Stack und drücken das entsprechende Tupel auf den Count-Stack.

Immer wenn Sie einen Operanden (wie 3,5 usw.) sehen, überprüfen Sie das oberste Tupel des Count-Stacks und dekrementieren Sie die Anzahl der Operanden, die in diesem Tupel verbleiben.

Wenn die Anzahl der noch zu beobachtenden Operanden gleich Null ist, wird das Tupel vom Stapel "Anzahl" entfernt. Dann wird aus dem Auswertungs-Stack die Anzahl der benötigten Operanden herausgesprungen (das wissen Sie wegen des anderen Wertes des Tupels), den Operator loslassen und die Operation ausführen, um einen neuen Wert (oder Operand) zu erhalten.

Drücken Sie nun den neuen Operanden auf den Evaluierungsstapel. Dieser neue Operanden-Push bewirkt, dass Sie einen weiteren Blick auf den oberen Teil des Count-Stacks werfen und dasselbe tun, was wir gerade getan haben (Dekrementieren der gesehenen Operanden, vergleichen mit Null etc.).

Wenn die Anzahl der Operanden nicht null wird, fahren Sie mit dem nächsten Token in der Eingabe fort.

Zum Beispiel sagen Sie hatte + bewerten 3 + 4/20 4

Die Stapel werden wie folgt aussehen (links oben auf dem Stapel)

Count     Evaluation     Input 
                + 3 + 4/20 4 

(2,2)     +       3 + 4/20 4 

(2,1)     3 +       + 4/20 4 

(2,2) (2,1)    + 3 +       4/20 4 

(2,1) (2,1)    4 + 3 +       /20 4 

(2,2) (2,1) (2,1)  /4 + 3 +       20 4 

(2,1) (2,1) (2,1)  20/4 + 3 +       4 

(2,0) (2,1) (2,1)  4 8/4 + 3 +     

Since it has become zero, you pop off two operands, the operator/
and evaluate and push back 5. You pop off (2,0) from the Count stack. 

(2,1) (2,1)    5 4 + 3 + 

Pushing back you decrement the current Count stack top. 

(2,0) (2,1)    5 4 + 3 + 

Since it has become zero, you pop off 5,4 and + and evaluate and push back 9. 
Also pop off (2,0) from the count stack. 

(2,0)       9 3 + 

           12 

EDIT:

A Freund schlug eine Möglichkeit vor, dies ohne mehrere Stapel zu tun:

Beginnen Sie am Ende, gehen Sie zum ersten Operator. Die Token rechts davon sind Operanden. Evaluieren und wiederholen. Scheint viel einfacher als mit zwei Stapeln. Wir können eine doppelt verknüpfte Liste verwenden, um die Eingabe darzustellen, die wir während der Verarbeitung ändern. Wenn Sie auswerten, löschen Sie Knoten und fügen Sie dann das Ergebnis ein. Oder Sie könnten vielleicht nur einen Stapel verwenden.

Answer 2

KISS bewerten in umgekehrter Richtung als Postfix Ausdruck auszuwerten.

Answer 3

Die Art, wie ich es sehe, haben Sie zwei Möglichkeiten. Gehe entweder von links nach rechts oder von rechts nach links (wie oben angedeutet). Beide Methoden werden im folgenden Code demonstriert.

public static class Evaluator 
{ 
    public static double EvaluatePrefix(string expr) 
    { 
     if (expr == null) throw new ArgumentNullException("expr"); 

     var symbols = expr.Split(','); 
     var stack = new Stack<Symbol>(); 

     foreach (var symbol in symbols) 
     { 
      double operand; 
      if (!double.TryParse(symbol, out operand)) //encountered an operator 
      { 
       stack.Push(new Operator(symbol)); 
       continue; 
      } 

      //encountered an operand 
      if (stack.Count == 0) throw new ArgumentException("Invalid expression"); 

      double right = operand; 
      var leftOperand = stack.Peek() as Operand; 
      while (leftOperand != null) 
      { 
       stack.Pop(); //pop left operand that we just peeked 
       if (stack.Count == 0) throw new ArgumentException("Invalid expression"); 
       double result = Calculate(leftOperand.Value, right, ((Operator)stack.Pop()).OperatorChar); 

       right = result; 
       leftOperand = (stack.Count == 0) ? null : stack.Peek() as Operand; 
      } 
      stack.Push(new Operand(right)); 
     } 

     if (stack.Count != 1) throw new ArgumentException("Invalid expression"); 
     var operandSymbol = stack.Pop() as Operand; 
     if (operandSymbol == null) throw new ArgumentException("Invalid expression"); 
     return operandSymbol.Value; 
    } 

    public static double EvaluatePrefixAlternative(string expr) 
    { 
     if (expr == null) throw new ArgumentNullException("expr"); 

     double d; 
     var stack = new Stack<Symbol>(
      expr.Split(',').Select(s => double.TryParse(s, out d) ? (Symbol) new Operand(d) : new Operator(s))); 

     var operands = new Stack<double>(); 
     while (stack.Count > 0) 
     { 
      var symbol = stack.Pop(); 
      var operand = symbol as Operand; 
      if (operand != null) 
      { 
       operands.Push(operand.Value); 
      } 
      else 
      { 
       if (operands.Count < 2) throw new ArgumentNullException("expr"); 
       operands.Push(Calculate(operands.Pop(), operands.Pop(), ((Operator) symbol).OperatorChar)); 
      } 
     } 

     if (operands.Count != 1) throw new ArgumentNullException("expr"); 
     return operands.Pop(); 
    } 

    private static double Calculate(double left, double right, char op) 
    { 
     switch (op) 
     { 
      case '*': 
       return (left * right); 
      case '+': 
       return (left + right); 
      case '-': 
       return (left - right); 
      case '/': 
       return (left/right); //May divide by zero ! 
      default: 
       throw new ArgumentException(string.Format("Unrecognized operand {0}", op), "op"); 
     } 
    } 

    abstract class Symbol 
    { 
    } 

    private class Operand : Symbol 
    { 
     public double Value { get; private set; } 

     public Operand(double value) 
     { 
      Value = value; 
     } 
    } 

    private class Operator : Symbol 
    { 
     public char OperatorChar { get; private set; } 

     public Operator(string symbol) 
     { 
      if (symbol.Trim().Length != 1) throw new ArgumentException("Invalid expression"); 
      OperatorChar = symbol[0]; 
     } 
    } 
} 

Einige Tests:

[TestMethod] 
public void TestPrefixEvaluation() 
{ 
    Assert.AreEqual(5, Evaluator.EvaluatePrefix("-,*,/,15,-,7,+,1,1,3,+,2,+,1,1")); 
    Assert.AreEqual(4, Evaluator.EvaluatePrefix("/,-,*,2,5,*,1,2,-,11,9")); 
    Assert.AreEqual(5, Evaluator.EvaluatePrefixAlternative("-,*,/,15,-,7,+,1,1,3,+,2,+,1,1")); 
    Assert.AreEqual(4, Evaluator.EvaluatePrefixAlternative("/,-,*,2,5,*,1,2,-,11,9")); 
}