(Golf) Revisiting Reversing RPN Notation

See my previous challenge here on RPN; there were a few flaws in the problem statement that I didn't catch before posting it, so I'm going to simply restate the problem again, and reinvite the golf challenge.

Given a RPN stack as an array. That is, you will be given something like "2 3 4 + *", which represents "( 3 + 4 ) * 2" in what I'll call left-to-right notation (LTR). You are also given a hash; the key of each hash are operators as used the RPN system, the values are an array ref; each array is 2 elements long, the first being the priority of the operator, and the second indicating the associativity ( a op ( b op c ) == ( a op b ) op c defined associativity) of the operation (1 if associative, 0 if not). The hash (this will be given to you, and you should pass it to the sub) may be defined as such:

my %operations = (  '+' =>  [ 1, 1 ],
                    '-' =>  [ 1, 0 ],
                    '*' =>  [ 2, 1 ],
                    '/' =>  [ 2, 0 ] );
[download]

Operations with higher priority will be evaluated first in LTR notiation with the absence of parentheses for grouping. For example, " 3 + 4 * 5 " will do 4*5 before doing 3+(20) in this case. Operations of the same priority will be performed as they are encountered left to right (eg 3 + 4 - 5 would be (3+4)-5, or 2.) Anything in parentheses would be evaluated first.

Note that while typical arithmatic functions are used here, the sub should work with any %operations hash that's structured correctly.

Find the perl golf (minimum number of characters in the subroutine) solution that builds the LTR notation for the RPN stack. The solution should minimize the use of parentheses for grouping.

Some example cases, using the hash above, include:

"2 3 4 * 5 / +"  --> 2 + 3 * 4 / 5
"3 4 * 5 / 2 +"  --> 3 * 4 / 5 + 2
"3 4 5 / * 2 +"  --> 3 * 4 / 5 + 2
"2 3 + 4 * 5 /"  --> (2 + 3) * 4 / 5
"2 3 4 - -"      --> 2 - (3 - 4)
"2 3 - 4 -"      --> (2 - 3) - 4
"2 3 4 + -"      --> 2 - (3 + 4)
"2 3 4 - +"      --> 2 + 3 - 4
[download]

Dr. Michael K. Neylon - mneylon-pm@masemware.com || "You've left the lens cap of your mind on again, Pinky" - The Brain

Comment on (Golf) Revisiting Reversing RPN Notation Select or Download Code

Replies are listed 'Best First'.
Re: (Golf) Revisiting Reversing RPN Notation by no_slogan (Deacon) on May 22, 2001 at 21:25 UTC
Your last example, `"2 3 4 - +" --> 2 + 3 - 4` makes use of the fact that subtraction associates with addition on the left. That is, `2 + (3 - 4) == (2 + 3) - 4` While this is true for addition and subtraction, it's not necessarily true for any arbitrary operators you might define in the hash. In trying to generalize this problem, you're walking a fine line between overgeneralizing (so that we need to write an entire theorem-prover to solve it (which would be NP-complete, BTW)), and undergeneralizng (tying yourself too closely to the familiar case of ordinary arithmetic).	[reply] [d/l] [select]

Replies are listed 'Best First'.

Re: (Golf) Revisiting Reversing RPN Notation
by no_slogan (Deacon) on May 22, 2001 at 21:25 UTC

"2 3 4 - +" --> 2 + 3 - 4

makes use of the fact that subtraction associates with addition on the left. That is,

2 + (3 - 4) == (2 + 3) - 4

While this is true for addition and subtraction, it's not necessarily true for any arbitrary operators you might define in the hash. In trying to generalize this problem, you're walking a fine line between overgeneralizing (so that we need to write an entire theorem-prover to solve it (which would be NP-complete, BTW)), and undergeneralizng (tying yourself too closely to the familiar case of ordinary arithmetic).

[reply]
[d/l]
[select]