접두사 표기법의 표현식을 계산하는 방법

Question

접두사 표기법의 표현식을 나타내는 목록을 평가하려고합니다. 다음은 이러한 목록의 예입니다 목록

Answer 1

접두어 대신 접미사를 사용하면 더 간단 해집니다. Reverse Polish Notation (RPN)을 참조하십시오. RPN에 표현식이 주어지면 단 하나의 스택을 사용하여 평가할 수 있습니다.

하지만 당신은 (가능성이 간단한 방법에 대해 편집을 참조 : 아래) 재귀와 스택을 사용하지 않고 접두사 식을 평가하는 방법을 물었다 이후 :

우리는이 두 가지를 사용하여 작업을 수행 할 수 있습니다, 여기에 한 가지 방법입니다 스택.

하나의 스택 (평가라고 부름)은 연산자 (예 : +, sin 등)와 피연산자 (3,4 등)를 보유하고 다른 스택 (Count는 호출)은 남은 피연산자 seen + 오퍼레이터가 기대하는 피연산자의 수.

연산자를 볼 때마다 연산자를 평가 스택으로 밀어 넣고 해당하는 튜플을 Count 스택에 푸시합니다.

피연산자 (3,5 등)를 볼 때마다 Count 스택의 맨 위 튜플을 확인하고 해당 튜플에 남아있는 피연산자 수를 줄입니다.

표시 할 피연산자 수가 0이면 계수 스택에서 튜플을 팝합니다. 그런 다음 평가 스택에서 필요한 피연산자 수를 띄우고 (튜플의 다른 값으로 인해 이것을 알고 있음), 연산자를 팝 오프 한 다음 연산을 수행하여 새로운 값 (또는 피연산자)을 얻습니다.

이제 새로운 피연산자를 다시 평가 스택에 푸시하십시오. 이 새로운 피연산자 푸시를 사용하면 Count 스택의 맨 위를 다시 살펴보고 방금 수행 한 것과 동일한 작업을 수행합니다 (표시된 피연산자를 감소시키고 0과 비교).

피연산자 수가 0이되지 않으면 입력의 다음 토큰을 계속 사용합니다. 예를 들어

는 평가했다 말할 + 3 + 20분의 4 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의 가치를 평가하는 가장 좋은 방법은 무엇

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

는, 후위 표현식으로 역방향으로 평가한다.

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