Cómo evaluar una expresión en notación de prefijo

Question

Estoy tratando de evaluar una lista que representa una expresión en notación de prefijo. Este es un ejemplo de tal lista:

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

¿Cuál es la mejor manera de evaluar el valor de la lista

Answer 1

Será más simple si usa postfix en lugar del prefijo. Ver Reverse Polish Notation (RPN). Dada una expresión en RPN, es fácil evaluar eso usando solo una pila.

Pero ya que pedirá una forma de evaluar prefijo expresiones sin recursividad y el uso de pilas (por ser un medio más simple, consulte Edición: abajo), aquí es una manera:

Podemos hacer esto utilizando dos pilas.

Una pila (llámala Evaluación) contiene los operadores (como +, sin, etc.) y operandos (como 3,4, etc.) y la otra pila (llámala Cuenta) contiene una tupla del número de operandos restantes. visto + la cantidad de operandos que espera un operador.

Cada vez que vea un operador, empujará al operador hacia la pila de evaluación y colocará la tupla correspondiente en la pila de conteo.

Cada vez que vea un operando (como 3,5, etc.), compruebe la tupla superior de la pila de recuento y disminuya el número de operandos que quedan para verse en esa tupla.

Si el número de operandos que quedan por ver se convierte en cero, saca la tupla de la pila de recuento. Luego, desde la pila de evaluación, extraes la cantidad de operandos necesarios (lo sabes por el otro valor de la tupla), desconectas el operador y realizas la operación para obtener un nuevo valor (o operando).

Ahora vuelva a colocar el nuevo operando en la pila de evaluación. Este nuevo impulso de operando hace que eche otro vistazo a la parte superior de la pila de recuento y hace lo mismo que acabamos de hacer (disminuir los operandos vistos, comparar con cero, etc.).

Si el recuento de operandos no se convierte en cero, continúe con el siguiente token en la entrada.

Por ejemplo decir que había que evaluar + 3 + 4/20 4

Las pilas se verá como (izquierda es la parte superior de la pila)

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 amigo sugirió una forma de hacerlo sin múltiples pilas:

Comience desde el final, vaya al primer operador. Los tokens a la derecha de eso serán operandos. Evaluar y rehacer Parece mucho más simple que hacerlo con dos pilas. Podemos usar una lista doblemente vinculada para representar la entrada que cambiamos durante el procesamiento. Cuando evalúa, elimina nodos y luego inserta el resultado. O tal vez podrías simplemente usar una pila.

Answer 2

KISS, evaluar a la inversa como una expresión de sufijo.

Answer 3

De la manera en que lo veo, tiene dos opciones. O bien, vaya de izquierda a derecha o de derecha a izquierda (como lo sugirió paul arriba). Ambos métodos se demuestran en el siguiente código.

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

Algunas pruebas:

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