Wie bewerten Sie einen Ausdruck in der Präfix-notation

Wird es einfacher sein, wenn Sie verwendet postfix statt Präfix. Sehen Die umgekehrte polnische Notation (RPN). Gegeben ein Ausdruck in RPN, ist es leicht zu bewerten, dass mit nur einem stack.

Aber da du gefragt für einen Weg zu bewerten Präfix Ausdrücken ohne Rekursion und Verwendung von stacks (für einen evtl. einfacheren Weg, siehe EDIT: weiter unten), hier ist eine Möglichkeit:

Wir können dies tun, mit zwei stacks.

Einem stack (call-it-Evaluation) hält den Operatoren (wie +, sin etc) und Operanden (wie 3,4 etc) und der andere Stapel (nennen wir ihn Graf) hat ein Tupel in der Anzahl der Operanden, die Links zu sehen + die Anzahl der Operanden eines operators erwartet.

Wenn Sie sehen einen operator, drücken Sie den Betreiber auf die Auswertung stack und drücken Sie die entsprechende Tupel auf der Graf-stack.

Jederzeit sehen Sie einen Operanden (wie 3,5 etc), überprüfen Sie die top-Tupel der Count-stack und dekrementiert die Anzahl von Operanden, die Links zu sehen ist, dass Tupel.

Wenn die Anzahl der Operanden, die Links zu sehen null wird, wird Sie aus dem pop-Tupel aus der Count-stack. Dann von der Evaluation stack pop Sie aus der Anzahl der Operanden erforderlich (Sie weiß das, weil der andere Wert der Tupel), pop-off der Betreiber und die operation erhalten Sie einen neuen Wert ein (oder Operanden).

Nun schieben Sie das neue Operanden zurück auf die Evaluation stack. Diese neue operand push bewirkt, dass Sie zu einem anderen Blick auf die Spitze der Graf Haufen und Sie tun die gleiche Sache, die wir gerade haben (dekrementiert den Operanden gesehen, zu vergleichen mit null etc.).

Wenn der operand count nicht zu null, fahren Sie mit dem nächsten token in der Eingabe.

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

Die Stapel Aussehen wird (Links ist oben auf dem stack)

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:

Einem Freund vorgeschlagen, einen Weg, dies zu tun ohne mehrere stacks:

Anfang vom Ende, gehen Sie zu den ersten operator. Die tokens auf die Rechte Seite, wird Operanden. Auswerten und wiederherstellen. Scheint viel einfacher als es zu tun mit zwei stacks. Können wir eine doppelt verkettete Liste darstellen, die Eingabe, das ändern wir während der Verarbeitung. Wenn Sie auswerten möchten, löschen Sie den Knoten, und legen Sie dann das Ergebnis. Oder man könnte vielleicht einfach ein stack.

InformationsquelleAutor

So wie ich das sehe hast du zwei Optionen. Gehen Sie entweder Links nach rechts oder von rechts nach Links (wie Paulus es oben vorgeschlagen). Beide Methoden werden im folgenden code dargestellt.

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

InformationsquelleAutor Ohad Schneider