Comment évaluer une expression en notation de préfixe

Question

J'essaie d'évaluer une liste qui représente une expression dans la notation de préfixe.Voici un exemple d'une telle liste:

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

Quel est le meilleur moyen d'évaluer la valeur de la liste

Answer 1

Ce sera plus simple si vous avez utilisé Postfix au lieu de préfixe. Voir NOTATION POLITIQUE REVERSE (RPN) . Étant donné une expression en RPN, il est facile d'évaluer qu'utilisant une seule pile.

Mais puisque vous avez demandé un moyen d'évaluer préfixe expressions sans récursion et en utilisant des piles (pour une manière éventuellement plus simple, voir Edition: ci-dessous), voici un moyen:

Nous pouvons le faire en utilisant deux piles.

Une pile (appel d'une évaluation informatique) contient les opérateurs (comme +, le péché, etc.) et des opérandes (comme 3,4, etc.) et l'autre pile (appeler le compte) contient un tuple du nombre d'opérandes laissés à voir. + Le nombre d'opérandes un opérateur s'attend à.

Chaque fois que vous voyez un opérateur, vous appuyez sur l'opérateur sur la pile d'évaluation et appuyez sur le tuple correspondant sur la pile de comptage.

Chaque fois que vous voyez un opérande (comme 3,5, etc.), vous vérifiez le tuple supérieur de la pile de comptage et décrémentez le nombre d'opérandes à voir dans ce tuple.

Si le nombre d'opérandes laissés à voir devient zéro, vous allez apparaître le tuple de la pile de comptage. Ensuite, à partir de la pile d'évaluation, vous avez indiqué le nombre d'opérandes requis (vous le savez en raison de l'autre valeur du tuple), apparaissez sur l'opérateur et effectuez l'opération pour obtenir une nouvelle valeur (ou opérande).

Poussez maintenant le nouvel opérande sur la pile d'évaluation. Ce nouvel opérande poussant vous entraîne un autre coup d'œil au sommet de la pile de comptabilisation et vous faites la même chose que nous venons de le faire (décrémenter les opérandes vus, comparer avec zéro, etc.).

Si le nombre d'opérandes ne devient pas zéro, vous continuez avec la prochaine jeton dans l'entrée.

Par exemple, disons que vous deviez évaluer + 3 + 4/20 4

Les piles à ressembler (à gauche est le haut de la pile)

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:

Un ami a suggéré un moyen de le faire sans plusieurs piles:

Début de la fin, allez au premier opérateur. Les jetons à droite de cela seront des opérandes. Évaluer et refaire. Semble beaucoup plus simple que de le faire avec deux piles. Nous pouvons utiliser une liste doublement liée pour représenter l'entrée que nous modifions pendant le traitement. Lorsque vous évaluez, vous supprimez des nœuds, puis insérez le résultat. Ou vous pouvez peut-être simplement utiliser une pile.

Answer 2

baiser, évaluez à l'envers en tant qu'expression postfix.

Answer 3

La façon dont je le vois, vous avez deux options.Soit aller à droite ou à droite à gauche (comme Paul suggéré ci-dessus).Les deux méthodes sont démontrées dans le code ci-dessous.

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

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