Как оценить выражение в префиксной нотации

Question

Я пытаюсь оценить список, который представляет выражение в префиксной нотации.Вот пример такого списка:

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

Как лучше всего оценить значение списка

Answer 1

Будет проще, если вы используете постфикс вместо префикса.См. Обратная польская запись (RPN) .Учитывая выражение в RPN, легко оценить это, используя только один стек.

Но так как вы попросили способ вычисления выражений prefix без рекурсии и использования стеков (для, возможно, более простого)кстати, см. РЕДАКТИРОВАТЬ: ниже), вот один из способов:

Мы можем сделать это, используя два стека.

Один стек (назовите его Evaluation) содержит операторы (например, +, sin и т. д.)и операнды (например, 3,4 и т. д.), а другой стек (назовите его Count) содержит кортеж из числа оставшихся видимых операндов + количество операндов, ожидаемых оператором.

Каждый раз, когда вы видите операторвы помещаете оператор в стек оценки и помещаете соответствующий кортеж в стек счета.

Каждый раз, когда вы видите операнд (например, 3,5 и т. д.), вы проверяете верхний кортеж из стека счета и уменьшаетеколичество операндов, оставшихся для просмотра в этом кортеже.

Если количество операндов, оставшихся для просмотра, станет равным нулю, вы выталкиваете кортеж из стека подсчета.Затем из стека оценки вы получаете необходимое количество операндов (вы знаете это из-за другого значения кортежа), извлекаете оператор и выполняете операцию, чтобы получить новое значение (или операнд).

Теперь поместите новый операнд обратно в стек оценки.Этот новый толчок операнда заставляет вас еще раз взглянуть на вершину стека Count, и вы делаете то же самое, что мы только что сделали (уменьшаем количество увиденных операндов, сравниваем с нулем и т. Д.).

Если число операндов нестановясь нулем, вы переходите к следующему токену на входе.

Например, скажем, вы должны были оценить + 3 + 4/20 4

Стеки будут выглядеть так (слева вверхустек)

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

РЕДАКТИРОВАТЬ:

Друг предложил способ сделать это без нескольких стеков:

Начните с конца, перейдите к первому оператору.Токены справа от этого будут операндами.Оценить и повторить.Кажется, намного проще, чем делать это с двумя стеками.Мы можем использовать двусвязный список для представления входных данных, которые мы изменяем во время обработки.Когда вы оцениваете, вы удаляете узлы, а затем вставляете результат.Или вы могли бы просто использовать один стек.

Answer 2

ПОЦЕЛУЙ, оцените наоборот как постфиксное выражение.

Answer 3

Как я вижу, у вас есть два варианта.Либо идите слева направо или справа налево (как предложил Пол выше).Оба метода продемонстрированы в приведенном ниже коде.

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

Некоторые тесты:

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