C# 转换反向波兰表示法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/113424/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Converting Reverse Polish Notation
提问by Iwasakabukiman
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?
使用 C++ 或 C# 时，有什么方法可以将逆波兰表示法解释为“正常”数学表示法？我在一家工程公司工作，所以他们偶尔会使用 RPN，我们需要一种方法来转换它。有什么建议？
采纳答案by Chris Jester-Young
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 like 2 (+ 3 4) *at that stage), it becomes (* 2 (+ 3 4)).
是的。想一想 RPN 计算器的工作原理。现在，不是计算值，而是将操作添加到树中。因此，例如，2 3 4 + *当您到达 + 时，您不是将 7 放在堆栈上，而是放在(+ 3 4)堆栈上。同样，当您到达 *（您的堆栈2 (+ 3 4) *在那个阶段看起来像）时，它变成(* 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 *.
这是前缀表示法，然后您必须将其转换为中缀。从左到右遍历树，深度优先。对于每个“内部级别”，如果运算符的优先级较低，则必须将操作放在括号中。在这里，您会说，2 * (3 + 4)因为 + 的优先级低于 *。
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 for 2 3 4 ** **? (** 2 (** 3 4))versus 2 3 ** 4 **? (** (** 2 3) 4).
编辑：有一个微妙之处（除了不考虑上面的一元运算）：我假设左结合运算符。对于右结合（例如，**），那么对于2 3 4 ** **? (** 2 (** 3 4))与2 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.
从树中重构中缀时，两种情况都表明优先级不需要括号，但实际上后一种情况需要括号 ( (2 ** 3) ** 4)。因此，对于右结合运算符，左分支需要更高的优先级（而不是更高或等于）以避免括号。
Also, further thoughts are that you need brackets for the right-hand branch of -and /operators too.
此外，进一步的想法是您也需要为-and/运算符的右侧分支添加括号。
回答by Abbas
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.
C# 没有对解析 Reverse Polish Notation (RPN) 的内置支持。您需要编写自己的解析器，或者在网上找到一个。
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:
有很多教程可以将后缀形式 (RPN) 转换为中缀（代数方程）。看看这个，也许你会发现它很有用，你可以尝试对其进行“逆向工程”以将后缀表达式转换为中缀形式，请记住，给定的后缀可以有多个中缀符号。实际上讨论将后缀转换为中缀的有用示例很少。这是我发现非常有用的 2 部分条目。它还有一些伪代码：
回答by Mike Thompson
The Shunting Yard Algorithm is used to convert Infix (i.e. algebraic) to RPN. This is the opposite of what you want.
Shunting Yard Algorithm 用于将 Infix（即代数）转换为 RPN。这与你想要的相反。
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.
你能给我一个你的 RPN 输入的例子吗？我是一位资深的 HP 计算器用户/程序员。我想你有一个包含所有输入和运算符的堆栈。我猜你需要重建表达式树，然后遍历树来生成中缀形式。
回答by ljs
One approach is to take the example from the second chapter of the dragon bookwhich explains how to write a parser to convert from infix to postfix notation, and reverse it.
一种方法是采用龙书第二章中的例子，它解释了如何编写解析器将中缀符号转换为后缀符号，并将其反转。
回答by Matt J
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).
如果您有一些源文本（字符串/s）要从 RPN（后缀表示法）转换为“普通表示法”（中缀），这当然是可能的（并且可能不太难）。
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).
RPN 是为基于堆栈的机器设计的，因为操作的表示方式（“2 + 3” -> “2 3 +”）适合它在硬件上的实际执行方式（将“2”推入堆栈，推入“3” " 到栈上，从栈顶弹出两个参数并将它们相加，再压回到栈上）。
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).
基本上，您希望通过创建要在“叶节点”上操作的 2 个表达式和操作本身（之后的“父节点”）来从 RPN 创建语法树。这可能是通过递归查看您的输入字符串来完成的（您可能希望确保子表达式正确加上括号以更加清晰，如果它们还没有的话）。
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.
可以在此处找到更多信息。
回答by AShelly
回答by raoulsson
I just wrote a version in Java, it's hereand one in Objective-C, over here.
我刚刚用 Java 写了一个版本，它在这里，一个在 Objective-C 中，在这里。
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.
可能的算法：假设您有一个堆栈，其中的输入为 rpn，因为用户会输入它，例如 8、9、*。您从头到尾遍历数组，并始终删除当前元素。你评估的这个元素。如果它是一个操作数，则将其添加到结果堆栈中。当它是一个运算符时，您为操作数弹出结果堆栈两次（对于二元运算），并将结果字符串写入结果堆栈。
With the example input of "8, 9, +, 2, *" you get these values on the resultstack (square brackets to indicate single elements):
使用“ 8, 9, +, 2, *”的示例输入，您可以在结果堆栈上获得这些值 （方括号表示单个元素）：
step 1: [8]
第 1 步：[8]
step 2: [8], [9]
第 2 步：[8]、[9]
step 3: [(8 + 9)]
第 3 步：[(8 + 9)]
step 4: [(8 + 9)], [2]
第 4 步：[(8 + 9)], [2]
step 5: [(8 + 9) * 2]
第 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 /".)
当输入堆栈为空时，您就完成了，resultStack 的唯一元素就是您的结果。（但请注意，输入可能包含多个条目或没有意义的条目，例如前导操作：“+ 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.
将它移植到 C# 是直接的。
