c# - 转换反向波兰表示法

Question

在使用 C++ 或 C# 时，是否有任何方法可以将反向波兰表示法解释为“正常”数学表示法？我在一家工程公司工作，所以他们偶尔会使用 RPN，我们需要一种方法来转换它。有什么建议吗？

Answer 1

是的。想一想 RPN 计算器的工作原理。现在，不是计算值，而是将操作添加到树中。因此，例如，2 3 4 + *，当您到达 + 时，您不是将 7 放入堆栈，而是将 (+ 3 4) 放入堆。同样，当您到达 *(您的堆栈在那个阶段看起来像 2 (+ 3 4) *)时，它变为 (* 2 (+ 3 4)).

这是前缀表示法，您必须将其转换为中缀。从左到右遍历树，深度优先。对于每个“内部级别”，如果运算符的优先级较低，则必须将操作放在括号中。然后，在这里，您会说，2 * (3 + 4)，因为 + 的优先级低于 *。

希望这对您有所帮助!

编辑:有一个微妙之处(除了在上面没有考虑一元运算之外):我假设了左关联运算符。对于右关联(例如，**)，2 3 4 ** ** ⇒ (** 2 (** 3 4)) 与 2 3 ** 4 ** ⇒ (** (** 2 3) 4)。

从树中重建中缀时，两种情况都表明优先级不需要括号，但实际上后一种情况需要括号 ((2 ** 3) ** 4) .因此，对于右结合运算符，左侧分支需要具有更高的优先级(而不是更高或等于)以避免括号。

此外，进一步的想法是您还需要为 - 和 / 运算符的右侧分支添加括号。