Converting Post-Fix (Reverse Polish) Notation

Date: 02/20/2000 at 21:41:56
From: Scott Francis
Subject: Reverse Polish Notation

How do I convert 

     ABCDE x F / + G - H / x +

to in-fix notation?

Date: 02/21/2000 at 00:47:55
From: Doctor Mike
Subject: Re: Reverse Polish Notation

Hi Scott,  
  
The way to re-write this is to work "from inside outward." This is 
harder to put into words than it would be to show an example, but I 
will try to do a combination.
  
You do the conversion by converting parts of the expression, in 
stages, until you are done. In each stage, you want to find 2 parts of 
the expression that have already been converted, followed by an 
operation,

  "Part already done"  "Another part already done"  "Operation"

You might say, how can I find something already done when I haven't 
done anything yet? Well, each one of the letters A to H makes equal 
sense in either situation. So to start out, scan for 2 letters 
together followed by an operation. I see D and E followed by x. This 
means D and E multiplied together. This is DEx in post-fix notation, 
xDE in pre-fix notation, and DxE in in-fix notation.

The next stage is the same as the first, finding two parts of the 
expression already converted, followed by an operation. The only 
difference is that NOW we have that DEx has been converted to DxE. 
What I find is:

     DxE  F  / 

To write this using in-fix notation, you must use something that is 
not needed in either pre-fix or post-fix notation, namely 
**parentheses**.

     (DxE) / F

To make sure you have the hang of this I'll do one more stage for you, 
and then turn you loose on the rest of the conversion. We have already 
used up the letters D, E, and F, and the converted expression DxE, so 
what is left to consider for the next stage? I see A, B, C, (DxE)/F, 
G, and H. Where is there an instance of the pattern we are looking for 
at each stage, two converted things followed by an operation? I see:

     C  (DxE)/F  +

which becomes:

     C + ((DxE)/F)

I'll give one more hint; Try doing this one stage per line, writing 
the parts you have converted to in-fix right under the post-fix parts 
you converted from, sort of like this:
     
     A  B  C  D  E  x  F  /  +  G  -  H  /  x  +  
     A  B  C (D x E)   F  /  +  G  -  H  /  x  + 
     A  B  C  ((D x E) / F)  +  G  -  H  /  x  +
     A  B [ C + ((D x E) / F) ] G  -  H  /  x  +  
  
Notice that in the 3rd stage I used [ and ] instead of ( and ) to make 
it more clear what was happening. I hope this helps. Good luck. You 
can write back if you really get stuck, and I'll complete the example 
for you. But I think you can do it yourself. 
  
- Doctor Mike, The Math Forum
  http://mathforum.org/dr.math/   

Date: 02/21/2000 at 01:11:51
From: Doctor Mike
Subject: Re: Reverse Polish Notation

Hi again, 
  
Just a quick add-on. Here's a converted example that has some 
different situations from the one of you sent. Verify it to see. Both 
the first stage AND the 2nd stage combine plain letters.

     Post-fix:  AB+CD-/
     In-fix:    (A+B)/(C-D)

Also, another hint about how to practice for experience. Start with 
something familiar expressed as the common In-fix notation. Convert 
that to Post-fix. THEN, using that result, translate back to In-fix. 
This allows you to make up your own problems with different 
challenges. And you have a great way to check your answer: When you 
get back into In-fix notation, you MUST have what you started with. 
Neat, eh?

- Doctor Mike, The Math Forum
  http://mathforum.org/dr.math/   

Date: 02/21/2000 at 11:10:12
From: Scott Francis
Subject: Re: Reverse Polish Notation

Thanks for your help, but I'm still a little confused. I came up with:

     (AxB)/(C+((DxE)/F)-(G+H)

Is this correct?

Date: 02/21/2000 at 18:06:36
From: Doctor Mike
Subject: Re: Reverse Polish Notation


Hi again,

I'll just finish off what I sent to you before, with some more 
comment. This is where we got so far:
  
     A  B  C  D  E  x  F  /  +  G  -  H  /  x  +
     A  B  C (D x E)   F  /  +  G  -  H  /  x  +
     A  B  C  ((D x E) / F)  +  G  -  H  /  x  +
     A  B [ C + ((D x E) / F) ] G  -  H  /  x  +

Remember that what you have to look for are two things that have 
already been converted to In-fix notation, followed IMMEDIATELY by an 
operation.

The only thing I see satisfying that is

     [ C + ((D x E) / F) ]  and  G  and the operation  -

Those become [ C + ((D x E) / F) ] - G, so you have:

     A  B [[ C + ((D x E) / F) ] - G] H  /  x  +

Next you see [[ C + ((D x E) / F) ] - G]  and  H  and  / , so you get:

     A  B {[[ C + ((D x E) / F) ] - G] / H} x  +

Then you see  B  and  {[[ C + ((D x E) / F) ] - G] / H}  and  x  for:

     A  { B x {[[ C + ((D x E) / F) ] - G] / H} } +

and finally:

     A + { B x {[[ C + ((D x E) / F) ] - G] / H} }

I realize that this is exceptionally detailed work, and you have to 
really concentrate at each step. Be VERY careful as you are writing 
down things from the previous line to the next one, and constantly 
keep focused on what you are looking for. Each step you look for:

        Thing 1   Thing 2   Op
   
you replace by:

       (Thing 1   Op   Thing 2)
or     [Thing 1   Op   Thing 2]
or     {Thing 1   Op   Thing 2}
   
and that is the only thing you change.    
  
You may be interested to know that, even though I know this stuff 
COLD, I had to check and re-check the details several times to make 
100% sure I didn't make a typo. I hope I caught them all! One really 
must "sweat the details" here. Good luck.

- Doctor Mike, The Math Forum
  http://mathforum.org/dr.math/