expression-trees - プレフィックス表記で式を評価する方法

Question

プレフィックス表記で式を表すリストを評価しようとしています。このようなリストの例を次に示します。

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

リストの価値を評価するための最良の方法は何ですか

Answer 1

プレフィックスの代わりにポストフィックスを使用すると、より簡単になります。逆ポーランド記法（RPN）を参照してください。RPNの式が与えられると、1つのスタックだけを使用してそれを評価するのは簡単です。

しかし、再帰を使用せずにスタックを使用してプレフィックス式を評価する方法を求めたので（おそらくより簡単な方法については、以下の編集を参照してください）、次の1つの方法があります。

これは、2つのスタックを使用して実行できます。

1つのスタック（評価と呼びます）は、演算子（+、sinなど）とオペランド（3,4など）を保持し、もう1つのスタック（カウントと呼びます）は、表示される残りのオペランドの数+数のタプルを保持します。演算子が期待するオペランドの数。

演算子が表示されたら、その演算子を評価スタックにプッシュし、対応するタプルをカウントスタックにプッシュします。

オペランド（3,5など）が表示されるたびに、カウントスタックの最上位のタプルをチェックし、そのタプルに表示される残りのオペランドの数をデクリメントします。

表示される残りのオペランドの数がゼロになった場合は、カウントスタックからタプルをポップします。次に、評価スタックから、必要なオペランドの数をポップオフし（タプルの他の値のためにこれを知っています）、演算子をポップオフし、新しい値（またはオペランド）を取得するための操作を実行します。

次に、新しいオペランドを評価スタックにプッシュバックします。この新しいオペランドプッシュにより、カウントスタックの最上位をもう一度確認し、今行ったのと同じことを実行します（表示されたオペランドをデクリメントし、ゼロと比較します）。

オペランド数がゼロにならない場合は、入力の次のトークンに進みます。

たとえば、+ 3 +4/204を評価する必要があるとします。

スタックは次のようになります（左がスタックの一番上です）

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

編集：

友人は、複数のスタックなしでこれを行う方法を提案しました：

最後から始めて、最初のオペレーターに行きます。その右側のトークンがオペランドになります。評価してやり直します。2つのスタックで行うよりもはるかに簡単なようです。二重リンクリストを使用して、処理中に変更する入力を表すことができます。評価するときは、ノードを削除してから、結果を挿入します。または、1つのスタックを使用することもできます。

Answer 2

KISS、接尾辞式として逆に評価します。

Answer 3

私の見方では、2つの選択肢があります。左から右または右から左に移動します（ポールが上で提案したように）。両方の方法は、以下のコードで示されています。

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