Инфикс для Postfix и унарные / бинарные операторы

Question

У меня есть фрагмент кода, который преобразует инфиксное выражение в дерево выражений в памяти. Это работает просто отлично. Есть только одна маленькая проблема. Я просто подключаюсь к тому, как правильно задействовать унарные операторы (правильные ассоциативные).

Со следующим выражением инфикса:

+1 + +2 - -3 - -4

Я бы ожидал, что RPN:

1+2++3-4--

Тем не менее, ни один из онлайновых конвертеров инфикс-постов, которые я могу найти, не справится с этим примером так, как я ожидал. У кого-нибудь есть четкое объяснение обработки правильных ассоциативных операторов, в частности бинарных, которые можно принять за унарные?

Редактировать / Разъяснение: Хотелось бы узнать, как бороться с унарными операторами при переводе с инфикса на постфикс. То есть: распознавание одного и того же символа «-», например, как унарного вместо бинарного оператора и, таким образом, другого приоритета. Я подумал бы об использовании конечного автомата, возможно, с двумя состояниями, но ...?

Answer 1

Ну, вам нужно определить, является ли данный оператор двоичным / унарным на этапе синтаксического анализа . Как только вы это сделаете, при создании RPN вы можете пометить операторы как принимающие 2 или 1 аргумент.

Вы можете попробовать использовать алгоритм Shunting Yard для анализа (и создания RPN одновременно), который также был разработан для работы с унарными операторами.

В любом случае, если все, что вас волнует, это одинарные + или -, вы можете просто вставить 0 в скобках, когда увидите + или -, который появляется «неожиданно».

Например,

+1 + +2 - -3 - -4

Вы должны быть в состоянии пройти через него и преобразовать в

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

Теперь вам не нужно беспокоиться об унарном + или - и вы можете забыть пометить операторы числом аргументов, которые они принимают.

Answer 2

может быть, этот хаотичный код C # поможет вам. унарный оператор имеет максимальный приоритет в арифметических операциях, поэтому приоритет для них будет выше. для идентификации унарного оператора я взял логическую переменную унарной, которая будет установлена ​​в true после каждого токена оператора и в false после операнда. Вы должны использовать другое обозначение для унарного оператора плюс и минус, чтобы вы могли различать унарный и бинарный оператор в PFE. Вот «#» и «~» используются для обозначения унарного плюса и унарного минуса в постфиксном выражении (PFE).

с помощью этого подхода вы можете обрабатывать все случаи, такие как 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;       
        }       
    }
}