转换逆波兰表示法
使用 C++ 或 C# 时，有什么方法可以将逆波兰表示法解释为“正常”数学表示法吗？ 我在一家工程公司工作，所以他们偶尔会使用 RPN，我们需要一种方法来转换它。 有什么建议么？
Is there any way to interpret Reverse Polish Notation into "normal" mathematical notation when using either C++ or C#? I work for an engineering firm, so they use RPN occasionally and we need a way to convert it. Any suggestions?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（7）
是的。 想一想 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）。 因此，对于右结合运算符，左侧分支需要具有更高的优先级（而不是更高或等于）以避免括号。另外，进一步的想法是，
-和/运算符的右侧分支也需要括号。Yes. Think of how a RPN calculator works. Now, instead of calculating the value, instead you add the operation to the tree. So, for example,
2 3 4 + *, when you get to the +, then rather than putting 7 on the stack, you put(+ 3 4)on the stack. And similarly when you get to the * (your stack will look like2 (+ 3 4) *at that stage), it becomes(* 2 (+ 3 4)).This is prefix notation, which you then have to convert to infix. Traverse the tree left-to-right, depth first. For each "inner level", if the precedence of the operator is lower, you will have to place the operation in brackets. Here, then, you will say,
2 * (3 + 4), because the + has lower precedence than *.Hope this helps!
Edit: There's a subtlety (apart from not considering unary operations in the above): I assumed left-associative operators. For right-associative (e.g.,
**), then you get different results for2 3 4 ** **⇒(** 2 (** 3 4))versus2 3 ** 4 **⇒(** (** 2 3) 4).When reconstructing infix from the tree, both cases show that the precedence doesn't require bracketing, but in reality the latter case needs to be bracketed (
(2 ** 3) ** 4). So, for right-associative operators, the left-hand branch needs to be higher-precedence (instead of higher-or-equal) to avoid bracketing.Also, further thoughts are that you need brackets for the right-hand branch of
-and/operators too.调车场算法用于将 Infix（即代数）转换为 RPN。 这与您想要的相反。
你能给我一个 RPN 输入的例子吗？ 我是一位资深的惠普计算器用户/程序员。 我假设你有一个包含所有输入和内容的堆栈。 运营商。 我猜你需要重建表达式树，然后遍历树以生成中缀形式。
The Shunting Yard Algorithm is used to convert Infix (i.e. algebraic) to RPN. This is the opposite of what you want.
Can you give me an example of your RPN input? I am a veteran HP calculator user/programmer. I presume you have a stack containing all the inputs & operators. I would guess that you need to reconstruct the expression tree and then traverse the tree to generate the infix form.
C# 没有内置对解析逆波兰表示法 (RPN) 的支持。您需要编写自己的解析器，或者在网上找到一个。
有许多将后缀形式（RPN）转换为中缀形式（代数方程）的教程。 看看这个，也许你会发现它很有用，你可以尝试对它进行“逆向工程”，将后缀表达式转换为中缀形式，请记住，给定的后缀表达式可以有多个中缀表示法。 实际讨论将后缀转换为中缀的有用示例非常少。 这是一个由两部分组成的条目，我发现它非常有用。 它还有一些伪代码：
C# doesn't have built-in support for parsing Reverse Polish Notation (RPN).You'll need to write your own parser, or find one online.
There are dozens of tutorials for converting postfix form (RPN) to infix (Algebraic Equation). Take a look at this, maybe you'll find it useful and you can try to ‘reverse engineer’ it to convert postfix expressions to infix form, keeping in mind that there can be multiple infix notations for a given postfix one. There are very few useful examples that actually discuss converting postfix to infix. Here’s a 2-part entry that I found very useful. It also has some pseudo code:
如果您能读懂 ruby，您会在 这里找到一些很好的解决方案< /a>
If you can read ruby, you'll find some good solutions to this here
一种方法是采用 dragon book 的第二章中的示例解释如何编写解析器以将中缀表示法转换为后缀表示法，并将其反转。
One approach is to take the example from the second chapter of the dragon book which explains how to write a parser to convert from infix to postfix notation, and reverse it.
如果您希望将一些源文本（字符串）从 RPN（后缀表示法）转换为“正常表示法”（中缀），这当然是可能的（并且可能不太困难）。
RPN 是为基于堆栈的机器设计的，因为操作的表示方式（“2 + 3” -> “2 3 +”）适合它在硬件上实际执行的方式（将“2”推入堆栈，将“push”） 3”进入堆栈，将顶部的两个参数从堆栈中弹出并添加它们，推回堆栈）。
基本上，您希望通过创建要在“叶节点”上操作的 2 个表达式以及操作本身（随后出现的“父节点”）来从 RPN 中创建语法树。 这可能通过递归地查看输入字符串来完成（为了更加清晰，您可能需要确保子表达式正确地加上括号，如果它们还没有）。
一旦有了该语法树，您就可以通过对该树进行前序、后序或中序遍历来输出前缀、中缀或后缀表示法（为了清楚起见，如果需要，请再次将输出放在括号中）。
可以在此处找到更多信息。
If you have some source text (string/s) that you're looking to convert from RPN (postfix notation) to "normal notation" (infix), this is certainly possible (and likely not too difficult).
RPN was designed for stack-based machines, as the way the operation was represented ("2 + 3" -> "2 3 +") fit how it was actually executed on the hardware (push "2" onto stack, push "3" onto stack, pop top two arguments off stack and add them, push back onto stack).
Basically, you want to create a syntax tree out of your RPN by making the 2 expressions you want to operate on "leaf nodes" and the operation itself, which comes afterward, the "parent node". This will probably be done by recursively looking at your input string (you'll probably want to make sure that subexpressions are correctly parenthesized for extra clarity, if they aren't already).
Once you have that syntax tree, you can output prefix, infix, or postfix notation simply by doing a pre-order, post-order, or in-order traversal of that tree (again, parenthesizing your output for clarity if desired).
Some more info can be found here.
我刚刚用Java编写了一个版本，它是 这里和 Objective-C 中的一个，在
可能的算法：假设您有一个堆栈，其中包含用户输入的 rpn 中的输入，例如 8、9、*。 从第一个到最后一个迭代数组，并且总是删除当前元素。 您评估这个元素。 如果它是操作数，则将其添加到结果堆栈中。 当它是一个运算符时，您将操作数弹出结果堆栈两次（对于二进制运算），并将结果字符串写入结果堆栈。
通过示例输入“8, 9, +, 2, *”，您将在结果堆栈上获得这些值（方括号表示单个元素）：
步骤 1：< strong>[8]
步骤 2：[8]、[9]
步骤 3：[(8 + 9)]
步骤 4：[ (8 + 9)], [2]
步骤 5: [(8 + 9) * 2]
当输入堆栈为空时，您就完成了，resultStack 的唯一元素是您的结果。 （但请注意，输入可能包含多个条目或没有意义的条目，例如前导操作：“+ 2 3 /”。）
链接中的实现故意不使用任何自制类型，例如运算符或操作数它也不适用例如复合图案。 它干净简单，因此可以轻松理解并移植到任何其他语言。
将其移植到 C# 非常简单。
I just wrote a version in Java, it's here and one in Objective-C, over here.
Possible algorithm: Given you have a stack with the input in rpn as the user would enter it, e.g. 8, 9, *. You iterate over the array from first to last and you always remove the current element. This element you evaluate. If it is an operand, you add it on a result stack. When it is an operator you pop the result stack twice (for binary operations) for the operands and write the result string on the result stack.
With the example input of "8, 9, +, 2, *" you get these values on the resultstack (square brackets to indicate single elements):
step 1: [8]
step 2: [8], [9]
step 3: [(8 + 9)]
step 4: [(8 + 9)], [2]
step 5: [(8 + 9) * 2]
When the input stack is empty, you are finished and the resultStack's only element is your result. (Note however that the input could contain multiple entries or such that don't make sense, like a leading operation: "+ 2 3 /".)
The implementations in the links deliberately don't use any selfmade types for e.g. operators or operands nor does it apply e.g. composite pattern. It's just clean and simple so it can be easily understood and ported to any other language.
Porting it to C# is straight forward.