在使用C++或C#时，有没有将逆波兰表达式解释为“正常”数学表达式的方法？我在一家工程公司工作，他们偶尔会使用RPN，我们需要一种转换的方法。有什么建议吗？
7个回答
15
是的。想想逆波兰计算器的工作原理。现在，您不是计算值，而是将操作添加到树中。因此，例如，当您到达+时，而不是将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），因为+的优先级低于×。
希望这可以帮助您！
编辑：除了不考虑一元运算之外，还有微妙之处：我假设左关联运算符。对于右关联（例如**），则您会得到不同的结果，对于2 3 4****，您会得到**2**3 4和2 3****4的结果。从树形结构中重建中缀表达式时，两种情况都不需要加括号，但实际上后一种情况需要加括号（2**3**4）。因此，对于右关联运算符，左分支需要更高的优先级（而不是更高或相等）以避免加括号。
另外，进一步思考是，您还需要为-和/运算符的右侧分支添加括号。
- Chris Jester-Young
4
Shunting Yard算法用于将中缀表达式（即代数表达式）转换为逆波兰表达式。这与您想要的相反。
你能给我一个逆波兰表达式输入的例子吗？我是一名资深的HP计算器用户/程序员。我猜测您需要重建表达式树，然后遍历该树以生成中缀表达式。
你能给我一个逆波兰表达式输入的例子吗？我是一名资深的HP计算器用户/程序员。我猜测您需要重建表达式树，然后遍历该树以生成中缀表达式。
- Mike Thompson
1
是的，创建表达式树确实是正确的方法。 :-) 我的方法是先转换为前缀，但也许有直接转换为中缀的方法可用。 - C. K. Young
2
C#没有内置支持解析逆波兰表达式（RPN）的功能。您需要编写自己的解析器或在网上找到一个解析器。
有数十个教程可以将后缀表达式（RPN）转换为中缀表达式（代数方程式）。看一下this，也许您会发现它很有用，并且可以尝试“反向工程”以将后缀表达式转换为中缀形式，记住对于给定的后缀表达式可能有多个中缀符号。实际上，很少有有用的示例讨论将后缀表达式转换为中缀表达式。这是我发现非常有用的两部分入口。它还有一些伪代码：
有数十个教程可以将后缀表达式（RPN）转换为中缀表达式（代数方程式）。看一下this，也许您会发现它很有用，并且可以尝试“反向工程”以将后缀表达式转换为中缀形式，记住对于给定的后缀表达式可能有多个中缀符号。实际上，很少有有用的示例讨论将后缀表达式转换为中缀表达式。这是我发现非常有用的两部分入口。它还有一些伪代码：
- Abbas
2
该链接讨论了如何将中缀表达式转换为后缀表达式，并非反之。 - C. K. Young
我已经更新了我的答案。虽然我没有找到确切的解决方案，但我已经添加了参考资料，应该有助于制定一个解决方案。 - Abbas
0
我刚刚用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#很简单。
- raoulsson
0
如果您有一些源文本（字符串）需要从RPN（后缀表示法）转换为“正常表示法”（中缀表示法），这是完全可能的（而且可能不太困难）。
RPN是为基于堆栈的机器设计的，因为操作的表示方式（“2 + 3” -> “2 3 +”）符合它在硬件上实际执行的方式（将“2”推入堆栈，将“3”推入堆栈，弹出堆栈上的前两个参数并将它们相加，再将结果推回堆栈）。
基本上，您想通过将要操作的2个表达式作为“叶节点”，其后跟的操作本身作为“父节点”，从您的RPN创建一个语法树。这可能是通过递归地查看输入字符串来完成的（如果尚未正确括号化子表达式，则可能需要确保它们正确括号化以获得额外的清晰度）。
一旦您拥有了该语法树，您可以通过对该树进行先序遍历、后序遍历或中序遍历来输出前缀、后缀或中缀表示法（如果需要，可以括号化输出以获得清晰度）。
更多信息可以在此处找到。
- Matt J
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接