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）。因此，对于右关联运算符，左侧分支需要更高优先级（而不是更高或等于）以避免括号。

-此外，进一步的想法是您也需要和运算符的右手分支的括号/。

Answer 2

调车场算法用于将中缀（即代数）转换为 RPN。这与您想要的相反。

你能给我一个你的RPN输入的例子吗？我是一位资深的惠普计算器用户/程序员。我假设您有一个包含所有输入和运算符的堆栈。我猜你需要重建表达式树，然后遍历树来生成中缀形式。

Answer 3

C# 没有对解析逆波兰表示法 (RPN) 的内置支持。您需要编写自己的解析器，或者在网上找到一个。

有许多教程将后缀形式（RPN）转换为中缀（代数方程）。看看这个，也许你会发现它很有用，你可以尝试“逆向工程”它以将后缀表达式转换为中缀形式，请记住，给定的后缀可以有多个中缀表示法。实际上讨论将后缀转换为中缀的有用示例很少。这是我发现非常有用的两部分条目。它还有一些伪代码：

• PostFix to Infix：将 RPN 转换为代数表达式
• 后缀到中缀，第 2 部分：添加括号

Answer 4

如果你能阅读 ruby​​，你会在这里找到一些很好的解决方案

Answer 5

一种方法是取龙书第二章中的示例，该章解释了如何编写解析器以将中缀表示法转换为后缀表示法，并将其反转。

Answer 6

如果您希望将一些源文本（字符串/s）从 RPN（后缀表示法）转换为“普通表示法”（中缀），这当然是可能的（并且可能不太难）。

RPN 是为基于堆栈的机器设计的，因为操作的表示方式（“2 + 3” -> “2 3 +”）适合它在硬件上的实际执行方式（将“2”推入堆栈，将“3” " 到堆栈上，从堆栈中弹出顶部的两个参数并添加它们，然后推回到堆栈上）。

基本上，您想通过创建要在“叶节点”上操作的 2 个表达式和操作本身（随后是“父节点”）来从 RPN 创建语法树。这可能会通过递归查看您的输入字符串来完成（您可能希望确保子表达式正确括起来以更加清晰，如果它们还没有的话）。

一旦你有了那个语法树，你就可以输出前缀、中缀或后缀表示法，只需对该树进行前序、后序或按序遍历（同样，如果需要，为了清楚起见，将输出括起来）。

更多信息可以在这里找到。

Answer 7

我刚刚用 Java 写了一个版本，它在这里和一个在 Objective-C 中，在这里。

可能的算法：假设您有一个堆栈，其中包含 rpn 中的输入，因为用户将输入它，例如 8、9、*。您从第一个到最后一个迭代数组，并且始终删除当前元素。您评估的这个元素。如果它是一个操作数，则将其添加到结果堆栈中。当它是一个运算符时，您将结果堆栈弹出两次（对于二进制操作），并将结果字符串写入结果堆栈。

使用“ 8, 9, +, 2, * ”的示例输入，您可以在结果堆栈上获得这些值 （方括号表示单个元素）：

第 1 步：[8]

第 2 步：[8]、[9]

第 3 步：[(8 + 9)]

第 4 步：[(8 + 9)]，[2]

第 5 步：[(8 + 9) * 2]

当输入堆栈为空时，您就完成了，resultStack 的唯一元素就是您的结果。（但请注意，输入可能包含多个条目或没有意义的条目，例如前导操作：“+ 2 3 /”。）

链接中的实现故意不使用任何自制类型，例如运算符或操作数，也不应用例如复合模式。它简洁明了，因此可以轻松理解并移植到任何其他语言。

将其移植到 C# 是直截了当的。