Cách đánh giá biểu thức trong ký hiệu tiền tố

Question

Tôi đang cố gắng đánh giá một danh sách đại diện cho một biểu thức trong ký pháp tiền tố. Dưới đây là một ví dụ về một danh sách như vậy:

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

cách tốt nhất để đánh giá giá trị của danh sách

Answer 1

Sẽ đơn giản hơn nếu bạn sử dụng postfix thay vì tiền tố. Xem Reverse Polish Notation (RPN). Với một biểu thức trong RPN, rất dễ dàng để đánh giá rằng chỉ sử dụng một ngăn xếp.

Nhưng kể từ khi bạn yêu cầu một cách để đánh giá tiền tố biểu thức mà không đệ quy và sử dụng ngăn xếp (một cách có thể đơn giản hơn, xem EDIT: dưới đây), đây là một cách:

Chúng ta có thể làm điều này bằng hai ngăn xếp.

Một ngăn xếp (gọi là Đánh giá) giữ các toán tử (như +, sin ...) và toán hạng (như 3,4 vv) và ngăn xếp khác (gọi là Đếm) giữ một bộ số lượng toán hạng còn lại thấy + số toán hạng mà toán tử mong đợi.

Bất cứ khi nào bạn nhìn thấy toán tử, bạn đẩy toán tử lên ngăn Đánh giá và đẩy tuple tương ứng lên ngăn xếp Đếm.

Bất cứ khi nào bạn nhìn thấy một toán hạng (như 3,5 vv), bạn kiểm tra tuple trên cùng của ngăn xếp đếm và giảm số toán hạng còn lại để được nhìn thấy trong bộ dữ liệu đó.

Nếu số toán hạng còn lại để được xem là 0, bạn bật tuple từ ngăn xếp Đếm. Sau đó, từ ngăn xếp Đánh giá bạn bật ra số lượng toán hạng cần thiết (bạn biết điều này vì giá trị khác của bộ tuple), hãy tắt toán tử và thực hiện thao tác để lấy giá trị mới (hoặc toán hạng).

Bây giờ hãy đẩy toán hạng mới trở lại trên ngăn xếp Đánh giá. Toán hạng mới này khiến bạn phải nhìn vào phần trên của ngăn xếp Đếm và bạn làm điều tương tự mà chúng ta vừa làm (giảm các toán hạng nhìn thấy, so sánh với số không vv).

Nếu số hạng toán hạng không trở thành 0, bạn tiếp tục với mã thông báo tiếp theo trong đầu vào.

Ví dụ nói rằng bạn phải đánh giá + 3 + 4/20 4

Các ngăn xếp sẽ trông giống như (bên trái là đỉnh của ngăn xếp)

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:

Một bạn đã đề xuất một cách để thực hiện việc này mà không cần nhiều ngăn xếp:

Bắt đầu từ cuối, hãy chuyển đến toán tử đầu tiên. Mã thông báo ở bên phải sẽ là toán hạng. Đánh giá và làm lại. Có vẻ đơn giản hơn nhiều so với thực hiện nó với hai ngăn xếp. Chúng tôi có thể sử dụng danh sách được liên kết kép để thể hiện đầu vào mà chúng tôi thay đổi trong quá trình xử lý. Khi bạn đánh giá, bạn xóa các nút, và sau đó chèn kết quả. Hoặc bạn có lẽ chỉ cần sử dụng một ngăn xếp.

Answer 2

KISS là gì, đánh giá theo hướng ngược lại như một biểu thức postfix.

Answer 3

Cách tôi nhìn thấy bạn có hai tùy chọn. Hoặc là đi từ trái sang phải hoặc phải sang trái (như paul gợi ý ở trên). Cả hai phương pháp được thể hiện trong đoạn mã dưới đây.

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

Một số xét nghiệm:

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