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

C# doesn't have built-in support for parsing Polish notation.You'll need to write your own parser, or find one online.

Take a look at this, maybe you'll find it useful.

Answer 2

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 3

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 4

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 5

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 6

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