我有一段代码将中缀表达式转换为内存中的表达式树。这工作得很好。只有一个小麻烦。我只是连接解决如何正确地涉及一元运算符（正确的关联运算符）。
使用以下中缀表达式：
+1 + +2 - -3 - -4
我希望 RPN 为：
1+2++3-4--
然而，我能找到的在线中缀后置转换器都没有以我期望的方式处理这个例子。有没有人对处理右关联运算符有明确的解释，特别是可能被误认为一元运算符的二元运算符？
编辑/澄清：我想知道在从中缀到后缀的翻译过程中如何处理一元运算符。即：例如将相同的“-”字符识别为一元而不是二元运算符，因此具有不同的优先级。我会考虑使用可能具有两种状态的状态机，但是......？
好吧，您需要在解析阶段确定给定运算符是否是二元/一元。完成此操作后，在创建 RPN 时，您可以将运算符标记为采用 2 个或 1 个参数。
您可以尝试使用Shutting 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;
}
}
}