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

In reply to (Golf) Revisiting Reversing RPN Notation by Masem

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.