Converting Reverse Polish Notation

Question

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?

Answer 1

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)).

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 for 2 3 4 ** ** ⇒ (** 2 (** 3 4)) versus 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.

Also, further thoughts are that you need brackets for the right-hand branch of - and / operators too.

Answer 2

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.

Answer 3

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:

• PostFix to Infix: converting RPN to algebraic expressions
• Postfix to infix, part 2: adding the parentheses

Answer 4

If you can read ruby, you'll find some good solutions to this here

Answer 5

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.

Answer 6

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.

Answer 7

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.