处理一元运算符的中缀到后缀算法

Question

算法的 I/p 将是这样的表达式：

a+(-b)
a*-b+c

即标准 C 编译器支持的任何表达式。

现在我已经将输入格式化为标记流，标记包含信息，无论是运算符还是操作数。 该算法应该接受这个并给我一个我可以评估的后缀表达式。

如果我使用标准转换算法，我无法区分一元操作和二进制操作。 就像 a*(-b) 会给我 ab-* ，这会以错误的方式评估。

Answer 1

如果运算符是表达式中的第一个运算符，or 位于另一个运算符之后，or 位于左括号之后，则它是一元运算符。

您必须在输出字符串中使用其他符号来表示一元运算符，因为否则无法区分后缀表示法中的二进制和一元变体。

Answer 2

在您的输入中，当您有 2 个连续的运算符时，第二个运算符将为一元。 如果您有更多连续的运算符，则除了第一个运算符之外的所有运算符都将是一元运算符。

将所有一元

-

运算符转换为操作数

-1

和运算符

*

，并删除所有一元

+

运算符。

如果第一个元素是运算符，则它是一元运算符。

括号是一种特殊情况，但您可以在第一遍中忽略它们。在以下示例中，

-

与

*

连续。

4*(-(5))

你的代币将变成：

4
*
(
-1
*
(
5
)
)

Answer 3

您可以简单地将

-6

转换为

06-

来完全消除一元运算符。我喜欢这种方法，因为它更加正交，并且在处理时不需要处理特殊情况。

另一种方法是对使用相同符号的运算符的一元和二进制版本使用不同的符号，例如。

-

仍为二进制减号，

~

变为负号。

Answer 4

我发现用等效的操作替换一元减号（在预处理阶段）：

(0-1)*

，很有帮助。

使用@n。米。可能是人工智能的声明：

如果运算符是表达式中的第一个运算符，或者位于另一个运算符之后，或者位于左括号之后，则它是一元运算符。

我们可以找到一个一元运算符，然后对于一元减号，代入表达式：

(0-1)*

然后正常继续评估阶段。

例如

-(1 + 1) and (2 + (-1))*-5

会变成

(0-1)*(1+1) and (2+((0-1)*1)*(0-1)*5

分别在处理一元减法（并删除空格）的预处理之后，使用常规调车场算法可以更轻松地将表达式转换为 RPN。