Beefy Boxes and Bandwidth Generously Provided by pair Networks
good chemistry is complicated,
and a little bit messy -LW

Re: (Golf) Reversing RPN Notation

by Arguile (Hermit)
on May 22, 2001 at 04:07 UTC ( #82139=note: print w/replies, xml ) Need Help??

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.


Replies are listed 'Best First'.
Re: Re: (Golf) Reversing RPN Notation
by MeowChow (Vicar) on May 22, 2001 at 09:38 UTC
    You have the right idea. Perhaps this will help you get started:
    sub rpn_ptree { my@s;$o{$_}?$s[--$#s]=[$_,@s[-2,-1]]:push@s,$_ for@_;@s }
    It's a pretty well-golfed sub that builds a parse tree out of an RPN expression. The only tricky part is the --$#s, which simultaneously pops off the top element of @s (by assigning to $#s), and returns the index of the new end of the array. And here's another way to build a parse tree:
    sub rpn_ptree { my$i;$o{$_[$i]}&&splice@_,$i-=2,3,[@_[$i..$i+2]]while++$i<@_;@_ }
                   s aamecha.s a..a\u$&owag.print

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://82139]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (12)
As of 2017-07-25 09:07 GMT
Find Nodes?
    Voting Booth?
    I came, I saw, I ...

    Results (366 votes). Check out past polls.