如何評估前綴表示法中的表達式

Question

我正在嘗試評估表示前綴表示法的表達式。這裏是這樣的列表的一個示例：

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

什麼是評價列表

Answer 1

如果您使用了postfix而不是前綴，這將會更簡單。見Reverse Polish Notation (RPN)。給定RPN中的表達式，很容易評估只使用一個堆棧。

不過既然你問了一個方法來評估前綴表情沒有遞歸和使用堆棧（對於可能更簡單的方法，請參見編輯：下面），這裏是一個辦法：

我們可以在此使用兩個做棧。

一個堆棧（稱爲評估）包含操作符（如+，sin等）和操作數（如3,4等），另一個堆棧（稱爲Count）包含剩餘操作數數目的元組見+操作員期望的操作數的數量。

無論何時您看到一位操作員，您都會將操作員推到評估堆棧上，並將相應的元組推入Count堆棧。當你看到一個操作數（如3,5等）時，你檢查Count堆棧的頂層元組，並減少剩餘操作數的數目以在該元組中看到。

如果剩餘要查看的操作數數量變爲零，則從Count堆棧彈出元組。然後從評估堆棧中彈出所需操作數的數量（您知道這是因爲元組的另一個值），彈出操作員並執行操作以獲取新值（或操作數）。

現在將新操作數推回到評估堆棧上。這個新的操作數推使你再次看一下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

KISS的值的最佳方式，評估反向作爲後綴表達式。

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