Converting postfix to infix notation

[Georg Waldgreve]

Please help.

I am looking for an algorithm to convert a formula given in postfix
notation to infix notation written in Fortran (or Pascal or
pseudocode). The algorithm should put the proper parentheses. The
examples I found are written in C or C++, which I don’t like and are
unable to understand.

Thank you in advance.

Georg

[Robin Vowels]

On Sep 8, 6:32 pm, Georg Waldgreve <Georg.Waldgr...@gmx-topmail.de>
wrote:

> I am looking for an algorithm to convert a formula given in postfix
> notation to infix notation written in Fortran (or Pascal or
> pseudocode). The algorithm should put the proper parentheses. The
> examples I found are written in C or C++, which I don’t like and are
> unable to understand.

C. L. Hamblin [1962]: Translation to and from Polish notation.
Computer Journal, 5: 210-213

[Postfix is also called "Reverse Polish".]

[Georg Waldgreve]

Am 08.09.2012 12:11, schrieb Robin Vowels:
> On Sep 8, 6:32 pm, Georg Waldgreve <Georg.Waldgr...@gmx-topmail.de>
> wrote:
>
>> I am looking for an algorithm to convert a formula given in postfix
>> notation to infix notation written in Fortran (or Pascal or
>> pseudocode). The algorithm should put the proper parentheses. The

>> examples I found are written in C or C++, which I don�t like and are

>> unable to understand.
>
> C. L. Hamblin [1962]: Translation to and from Polish notation.
> Computer Journal, 5: 210-213
>
> [Postfix is also called "Reverse Polish".]
>

Thank you, but . . .

Sorry, Hamblin's article does not give at translation from RPN to what
he calls 'orthodox notation'.

Georg

[Louis Krupp]

Sounds like a homework problem...

Basically, it works like this:

Scan the reverse Polish expression from left to right, recognizing
operands and operators. When you see an operand, push it on a stack.
When you see a unary operator (like unary "-"), pop one operand off
the stack, apply the operator, and push the result on the stack. When
you see a binary operator (like "-" or "+" or "*" or "/"), pop two
operands off the stack, apply the operator, and push the result.

When you come to the end of the input expression, you should have one
item on the stack, and that's your answer.

If you're doing this symbolically (and it sounds like you are), put
parenthesis around infix expressions as you create them. The result
will be longer than it needs to be -- for example, the parentheses in
"(a * b) + c" are redundant in most languages -- but it will be
mathematically correct.

I hope this helps.

Louis

[Robin Vowels]

On Sep 8, 9:16 pm, Georg Waldgreve <Georg.Waldgr...@gmx-topmail.de>

wrote:
> Am 08.09.2012 12:11, schrieb Robin Vowels:> On Sep 8, 6:32 pm, Georg Waldgreve <Georg.Waldgr...@gmx-topmail.de>
> > wrote:
>
> >> I am looking for an algorithm to convert a formula given in postfix
> >> notation to infix notation written in Fortran (or Pascal or
> >> pseudocode). The algorithm should put the proper parentheses. The

> >> examples I found are written in C or C++, which I don’t like and are

> >> unable to understand.
>
> > C. L. Hamblin [1962]: Translation to and from Polish notation.
> > Computer Journal, 5: 210-213
>
> > [Postfix is also called "Reverse Polish".]
>
> Thank you, but . . .
>
> Sorry, Hamblin's article does not give at translation from RPN to what
> he calls 'orthodox notation'.

Actually he does.
He gives an algorithm to convert forward Polish to orthodox
notation. That is immediately followed by an algorithm to convert RPN
to forward Polish (see page 213, sections III and IV).

[Georg Waldgreve]

Thank you all!

I found the desciption of the algorithm in a Java-like pseudo-language.

Georg

[James J. Weinkam]

If an expression is represented as a tree, it is simple to obtain its prefix, fully parenthesized infix, and postfix
representations by performing preorder, inorder, and postoder traversals respectively. Obtaining the minimally
parenthesized infix representation requires a bit more work but it isn't all that difficult. Converting the postfix
representation of an expression to its tree representation is trivial.

Note that prefix and postfix representations must use distinct symbols for unary and binary usages of the same operation
symbol, whereas in tree representation the usage is implied by the out degree of the node and in infix notation it is
syntactically determined. Note also that there is not a unique minimally parenthesized infix representation because the
precedence and associativity of the operations vary from language to language.

[Terence]

What Luis Krupp just described is what the Forth Language does to solve the
same 'reverse Polish' notation.

[Robin Vowels]

Alternatively, you can do it directly from reverse Polish
to orthodox notation, as Hamblin suggests, using virtually
the same algorithm as from forward Polish to orthodox.