중위 어와 단항/이항 연산자

Question

중온 표현식을 메모리의 표현식 트리로 변환하는 코드가 있습니다. 이것은 잘 작동합니다. 작은 문제가 하나 있습니다. 나는 단항 연산자를 올바르게 연관시키는 방법 (올바른 연관성있는 연산자)을 연결한다.

는

1+2++3-4-- 

는하지만, 내가 찾을 수있는 온라인 중위 포스트 컨버터 중 어느 것도 방법이 예제를 처리하지 : 나는의 RPN을 기대

+1 + +2 - -3 - -4 

: 다음과 같은 중위 식으로

나는 기대할 것이다. 누구든지 올바른 연관 연산자를 처리하는 명확한 설명을 갖고 있습니까? 특히 이진 연산자는 단항 연산자로 잘못 인식 될 수 있습니다.

편집/설명 : 중위 어에서 후미로 변환하는 동안 단항 연산자를 처리하는 방법을 알고 싶습니다. 예 : '-'문자를 이진 연산자 대신 단항 문자로 인식하므로 우선 순위가 다릅니다. 아마 2 개의 주와 상태 머신을 사용하는 것을 생각할 것입니다 ...?

Answer 1

음, 구문 분석 중 단계 동안 주어진 연산자가 2 진수/단항식인지 확인해야합니다. 이렇게하면 RPN을 만들 때 연산자에 2 개 또는 1 개의 인수를 사용하여 태그를 지정할 수 있습니다.

Shunting Yard 알고리즘을 사용하여 단항 연산자와 함께 작동하도록 설계된 구문 분석 (및 동시에 RPN 생성)을 시도해 볼 수 있습니다.

어쨌든 당신이 신경 쓰이는 것이 단항 + 또는 - 인 경우 + 또는 -가 표시되면 대괄호로 0을 삽입하면 '예기치 않게'나타납니다. 예를 들어

+1 + +2 - -3 - -4

당신은 그것을 통해 패스를하고 변환 할 수 있어야 이제

(0+1) + (0+2) - (0-3) - (0-4)

에 당신이 단항 +에 대해 걱정할 필요가 없습니다 또는 그리고 아마도 그들이 취하는 논증의 수를 연산자에 태깅하는 것을 잊어 버릴 수 있습니다.

Answer 2

이 혼란스러운 C# 코드가 도움이 될 수 있습니다. 단항 연산자는 산술 연산에서 최대 우선 순위를 가지므로 우선 순위가 더 높습니다. 단항 연산자를 식별하기위한 각 연산자 토큰 후에 true로 설정되고 피연산자 뒤에 false로 설정된 부울 변수 unary를 취했습니다. PFE에서 단항 연산자와 이진 연산자를 구별 할 수 있도록 단항 플러스 및 마이너스 연산자에 대해 다른 표기법을 사용해야합니다. 여기 '#'및 '~'는 PFE (후치 표현식)의 단항 플러스 및 단항 빼기를 나타내는 데 사용됩니다.

이 approch를 사용하여 1 + -1,1 + (- 1), 1 --- 1,1 + - 1과 같은 모든 사례를 처리 할 수 ​​있습니다.

using System; 
using System.Linq; 
using System.Text; 
using System.Threading.Tasks; 
namespace DSA 
{ 
    class Calculator 
    { 
     string PFE; 
     public Calculator() 
     { 
      Console.WriteLine("Intializing Calculator"); 
     } 

     public double Calculate(string expression) 
     { 
      ConvertToPost(expression); 
      return CalculatePOST(); 
     } 

     public void ConvertToPost(string expression) 
     { 
      expression = "(" + expression + ")"; 

      var temp = new DSA.Stack<char>(); 
      string ch = string.Empty; 
      bool unary = true; 
      char a; 
      foreach (var b in expression) 
      { 
       a = b; 
       if (!a.IsOperator()) { 
        ch += a.ToString(); 
        unary = false; 
       } 
       else 
       { 
        if (ch!=string.Empty) 
        PFE += ch+","; 
        ch = string.Empty; 
        if(a!='(' && a!=')') 
        { 
         if (unary == true) 
         { 
          if (a == '-') a = '~'; else if (a == '+') a = '#'; else throw new InvalidOperationException("invalid input string"); 
         } 
         try 
         { 
          if (a.Precedence() <= temp.Peek().Precedence()) 
          { 
           PFE += temp.Pop().ToString() + ","; 
          } 
          } 
         catch(InvalidOperationException e) 
         { 

         } 

          temp.Push(a); 
          unary = true; 
        } 
        if (a == '(') { temp.Push(a);} 
        if(a==')') 
        { 
         for(char t=temp.Pop();t!='(';t=temp.Pop()) 
         { 
          PFE += t.ToString() + ","; 
         } 
        } 
       } 

      } 

     } 

     public double CalculatePOST() 
     { 
      var eval = new Stack<double>(); 
      string ch = string.Empty; 
      bool skip = false; 
      foreach(char c in PFE) 
      { 
       if(!c.IsOperator()) 
       { 
        if (c == ',') 
        { 
         if (skip == true) 

         { 
          skip = false; 
          continue; 
         } 
         eval.Push(Double.Parse(ch)); 
         ch = string.Empty; 
        } 
        else ch += c; 
       } 
       else 
       { 
        if (c == '~') 
        { 
         var op1 = eval.Pop(); 
         eval.Push(-op1); 
        } 
        else if (c == '#') ; 
        else 
        { 
         var op2 = eval.Pop(); 
         var op1 = eval.Pop(); 
         eval.Push(Calc(op1, op2, c)); 
        } 
        skip = true; 
       } 
       } 
      return eval.Pop(); 
     } 

     private double Calc(double op1, double op2, char c) 
     { 
      switch(c) 
      { 

       case '+': 
        return op1 + op2; 
       case '-': 
        return op1 - op2; 
       case '*': 
        return op1 * op2; 
       case '%': 
        return op1 % op2; 
       case '/': 
        return op1/op2; 
       case '^': 
        return float.Parse(Math.Pow(op1,op2).ToString()); 
       default: 
        throw new InvalidOperationException(); 
      } 
     } 
    } 


    public static class extension 
    { 
     public static bool IsOperator(this char a) 
     { 
      char[] op = {'+','-','/','*','(',')','^','!','%','~','#'}; 
      return op.Contains(a); 
     } 

     public static int Precedence(this char a) 
     { 
      if (a == '~' || a== '#') 
       return 1; 
      if (a == '^') 
       return 0; 
      if (a == '*' || a == '/' || a=='%') 
       return -1; 
      if (a == '+' || a == '-') 
       return -2; 
      return -3;  
     }  
    } 
}