Инфикс для Postfix и унарные / бинарные операторы
У меня есть кусок кода, который преобразует инфиксное выражение в дерево выражений в памяти. Это работает просто отлично. Есть только одна маленькая проблема. Я просто соединяю работу, как правильно задействовать унарные операторы (правильные ассоциативные).
Со следующим инфиксным выражением:
+1 + +2 - -3 - -4
Я ожидал бы RPN:
1+2++3-4--
Тем не менее, ни один из онлайн-конвертеров инфиксов, которые я могу найти, не справится с этим примером так, как я ожидал. У кого-нибудь есть четкое объяснение обработки правильных ассоциативных операторов, в частности, бинарных, которые можно принять за унарные?
Edit / Clarification: я хотел бы знать, как обращаться с унарными операторами при переводе из инфикса в постфикс. То есть: распознавание одного и того же символа "-", например, как унарного вместо бинарного оператора и, таким образом, другого приоритета. Я мог бы подумать об использовании конечного автомата, возможно, с двумя состояниями, но...?
2 ответа
Что ж, вам нужно определить, является ли данный оператор двоичным / унарным на этапе анализа. После того, как вы это сделаете, при создании RPN вы можете пометить операторы как принимающие 2 или 1 аргумент.
Вы можете попробовать использовать алгоритм Shunting Yard для анализа (и создания RPN одновременно), который также был разработан для работы с унарными операторами.
В любом случае, если все, что вас волнует, это унарный знак + или -, вы можете просто вставить 0 с квадратными скобками, когда увидите + или -, который появляется "неожиданно".
Например
+1 + +2 - -3 - -4
Вы должны быть в состоянии пройти через это и преобразовать в
(0+1) + (0+2) - (0-3) - (0-4)
Теперь вам не нужно беспокоиться об унарном + или - и вы можете забыть пометить операторы числом аргументов, которые они принимают.
Может быть, этот хаотичный код 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;
}
}
}