Shunting-yard算法中如何处理一元减号

Question

在将中缀表达式转换为后缀表达式时，是否有更好的处理一元“-”的方法？

显而易见的方法是在每个一元“-”之前添加一个0。是否有更好的实现方法？谢谢！

- JASON

---

据我所知，解决这个问题有几种方法，但它们都在某种程度上有些hackish。 - harold

两年后我看到了你的帖子，我也有同样的问题。这是一种永远都会存在的问题。这里有一个观察结果：添加一个零（我也考虑过）并不总是有效的。例如： --3 会被转换为 0 - 3 -3 = -6 大多数解析器会将减号视为乘以负一的乘积，即：

• (-3) = 6。干杯！

- MrVelez

@MrVelez：你说的加前缀零是不行的，但原因不同。对于预处理'--3'，通过添加前缀零应该得到'0-0-3'（而不是'0-3-3'，第二个3从哪里来？）。即',--3' --> '0-,-3' --> '0-0-,3' --> '0-0-3,'，这将导致后缀'0 0 - 3 -'。这将评估为-3，这可能不是我们想要的结果。如果我们可以让'0-0-3'翻译成后缀'0 0 3 - -'，那么它将评估为所需的3。 - A. I. Breveleri

Answer 1

我多年前解决这个问题的方法是为后缀表达式发明一个新的运算符。当我在中缀表达式中遇到一元减号时，我将其转换为#。因此，对于a + -b，我的后缀表达式变成了ab#+。

当然，我的求值器必须知道#只弹出一个操作数。

这有点取决于你构建后缀表达式后如何使用它。如果你想显示它，那么你的特殊#运算符可能会让人感到困惑。但如果你只是在内部使用它（就像我一样），那么它非常好用。

- Jim Mischel

---

我也这样做。我能确定我已经“在中缀中遇到了一元减号”的唯一方法是维护一个布尔上下文，定义下一个期望的是运算符还是操作数。我想知道其他人是如何决定连字符是一元还是二元的。 - A. I. Breveleri

@A.I.Breveleri：如果您使用递归下降解析器来处理中缀表达式，您可以在不显式维护状态的情况下识别一元运算符。例如，请参见http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm。 - Jim Mischel

Answer 2

遍历字符串，将所有一元减运算符替换为0-，并用括号将结果括起来。例如，给定-20 + (-2 * 50)，将其转换为(0-20) + ((0-2) * 50)。

- Michael Jordan

---

这在例如“--20”上失败。通过在前面加零进行预处理可得到“0-0-20”。这将导致后缀“0 0 - 20 -”。这将计算为-20，这可能不是我们从“--20”想要的结果。 - A. I. Breveleri

如果你也加上括号，那么它会被计算为(0-(0-20))，这是正确的。 - Balázs Kovacsics