Comment évaluer une expression dans la notation de préfixe

Question

J'essaye 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]] 

Quelle est la meilleure façon d'évaluer la valeur de la liste

Answer 1

Ce sera plus simple si vous avez utilisé postfix au lieu du préfixe. Voir Reverse Polish Notation (RPN). Étant donné une expression dans RPN, il est facile d'évaluer cela en utilisant une seule pile.

Mais puisque vous avez demandé un moyen d'évaluer le préfixe expressions sans récursivité et en utilisant des piles (pour une manière peut-être plus simple, voir EDIT: ci-dessous), voici une façon:

Nous pouvons le faire en utilisant deux des piles. Une pile (appelez-la évaluation) contient les opérateurs (comme +, sin etc) et les opérandes (comme 3.4 etc) et l'autre pile (appelez-le Count) contient un nombre d'opérandes restant à être vu + le nombre d'opérandes qu'un opérateur attend.

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

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

Si le nombre d'opérandes restant à afficher est égal à zéro, vous supprimez le tuple de la pile Count. Ensuite, à partir de la pile d'évaluation, vous faites apparaître le nombre d'opérandes requis (vous le savez en raison de l'autre valeur de l'uplet), déplacez l'opérateur et effectuez l'opération pour obtenir une nouvelle valeur (ou opérande).

Maintenant, repoussez le nouvel opérande sur la pile d'évaluation. Cette nouvelle poussée d'opérande vous oblige à jeter un autre coup d'œil au sommet de la pile de Count et vous faites la même chose que nous venons de faire (décrémenter les opérandes vues, comparer avec zéro etc).

Si le nombre d'opérandes ne devient pas nul, vous continuez avec le jeton suivant dans l'entrée.

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

Les piles ressembleront (à 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:

A ami a suggéré un moyen de le faire sans piles multiples:

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

Answer 2

KISS, évaluer dans le sens inverse comme une expression de Postfix.

Answer 3

La façon dont je le vois vous avez deux options. Soit aller de gauche à droite ou de droite à gauche (comme 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]; 
     } 
    } 
} 

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