Come valutare un'espressione nella notazione di prefisso

Question

Sto cercando di valutare un elenco che rappresenta un'espressione nella notazione prefisso.Ecco un esempio di tale lista:

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

.

Qual è il modo migliore per valutare il valore della lista

Answer 1

sarà più semplice se hai usato Postfix anziché prefisso. Vedi Notazione di retromarcia polacca (RPN) . Data un'espressione in RPN, è facile valutare che usando solo una pila.

Ma da quando hai chiesto un modo per valutare prefisso espressioni senza ricorsione e usando stack (per un modo possibilmente più semplice, vedere Modifica: sotto), ecco un modo:

Possiamo farlo usando due pile.

Uno stack (chiamare la valutazione) contiene gli operatori (come +, peccato ecc.) E gli operandi (come 3,4 ecc.) E l'altro stack (Call It Count) contiene una tupla del numero di operandi da cui essere visti + il numero di operandi che un operatore si aspetta.

Ogni volta che si vede un operatore, si preme l'operatore sullo stack di valutazione e premi la tupla corrispondente sulla pila di conteggio.

Ogni volta che vedi un operando (come 3,5 ecc.), Controlli la tupla superiore della pila di conteggio e decrementa il numero di operandi da vedere in quella tupla.

Se il numero di operandi da visualizzare diventa zero, si apre la tupla dalla pila di conteggio. Poi dallo impilato di valutazione viene spento il numero di operandi richiesti (lo sai a causa dell'altro valore della tupla), pop dall'operatore e fai l'operazione per ottenere un nuovo valore, (o operando).

Ora spinge il nuovo Operando sulla pila di valutazione. Questa nuova spinta dell'operando ti fa sì di dare un altro sguardo nella parte superiore della pila di conteggio e fai la stessa cosa che abbiamo appena fatto (decrementare gli operandi visti, confronta con zero ecc.).

Se il conteggio dell'operand non diventa zero, si continua con il token successivo nell'input.

Ad esempio dire che dovevi valutare + 3 + 4/20 4

Le pile sembrano (a sinistra è la parte superiore dello 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

.

Modifica:

Un amico ha suggerito un modo per farlo senza più pile:

Inizia dalla fine, vai al primo operatore. I token a destra di ciò saranno operandi. Valutare e ripetere. Sembra molto più semplice che farlo con due pile. Possiamo utilizzare un elenco doppiamente collegato per rappresentare l'input che cambiamo durante l'elaborazione. Quando si valuta, elimini i nodi, quindi inserisci il risultato. Oppure puoi forse usare uno stack.

Answer 2

bacio, valuta al contrario come espressione postfix.

Answer 3

Il modo in cui lo vedo hai due opzioni.O vai a sinistra a destra oa destra a sinistra (come suggerito Paolo sopra).Entrambi i metodi sono dimostrati nel codice qui sotto.

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

.

Alcuni test:

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

.