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.