http://www.perlmonks.org?node_id=82139


in reply to (Golf) Reversing RPN Notation

<body bgcolor="#ffffff"> I tried to implement this even in expanded code, but my grasp of Perl is still a little too loose. Expanding chipmunk's code didn't really help any either (I couldn't seem to expand it properly.. maybe it's just lack of sleep ;). So instead of submitting a golfed answer, I'd like to submit up the reasoning behind what I tried to implement to see if I was even on the right track. And if it was on the right track, maybe someone will benefit from the approach.

The basic idea behind the approach is to only examine three (3) elements of the stack at a time and work solely on those until the entire stack is resolved. Our three element pattern will consist of two numbers, and an operand. So if we test the three elements against the operator hash, 0 0 1 will be the truth values returned. Represented here as:

     

We'll now populate the stack with a test case 3 4 5 / + 2 * and go through converting it to the end string.

i=1: <tr align="center" bgcolor="#ffffff"">
3 4 5 / + 2 *
3 4 X        

The first iteration didn't return a match so move on position along the stack.

i=2: <tr align="center" bgcolor="#ffffff"">
3 4 5 / + 2 *
  4 5 / 2    

Our stack slice has matched its pattern. The 2 after the slice is to show the precedence of the operator, in the first match this doesn't have any bearing.

Having a match we now move it into our answer string. The first thing we do is set the precedence of our current string, which in this case is $precedence = 2; because the / operator has a value of 2 in the hash. We can then flip the operator into it's place between the two numbers and store it as the string "4/5". The last step is to sub the string back into the stack, and restart the iterations. The string will be represented as S in the stack for clarity.

i=1: <tr align="center" bgcolor="#ffffff"">
3 S + 2 *
3 S + 1  

Our stack slice has matched its pattern. This time the precedence of the operator will have to be compared against the current strings precedence. As 1 < 2 we don't need to insert parenthesis around the string. We perform the same operation as before, store the new $precedence = 1 then flip the last two elements (S and +), store it as the string "3+4/5", then sub it back into our now small stack.

i=1: <tr align="center" bgcolor="#ffffff"">
S 2 *
3 S * 2

Our stack slice has matched its pattern. The precedence operator of this stack piece is greater than our strings precedence 2 > 1 so we have to add parenthesis around the string before we move on. Once that's done we can follow the same operations as before, coming out with the string "(3+4/5)*2" which is correct to our defined precedence.

The string gets plugged back into the stack, the outer loop has it's condition fufilled (the stack has less than 3 elements) so exits returning our string.

Theoretically this approach should work for as many operators and levels of precedence a user cares to assign without extraneous parenthesis, as it evaluates them one at a time. Does this make sense? I couldn't get it to work and it's wasn't for lack of trying.

</body>