Seeing Meowchow's golf-like solution to Solving 24 Puzzles, I got another idea for a golf puzzle. Don't worry, this is nowhere close to NP :-)

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, and the values is the priority of that operation. For example,

my %priorities = {  '+' => 1,
                    '-' => 1,
                    '*' => 2,
                    '/' => 2 };
[download]

All operations will be binary. Operations with higher priorities will be evaluated first in LTR notation unless parenthesis are used; the expression in parenthesis are evaluated first. Operations of the same priority can be considered to be communitive, and can be evaulated in any order. So in the case of the above list and the LTR "2 + 3 * 4 / 5", the addition operation will take place after the multiplication and division. (This can be represented by the RPN stack "2 3 4 * 5 / +", "3 4 * 5 / 2 +", or "3 4 5 / * 2 +" for example.). Any item on the RPN stack that is not a key of this hash can be considered to be a 'number' or 'operand'.

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
[download]

Updates: fixed the 3 statement to produce the right order. Also, assume that you are given that priorities hash and may pass it freely to your sub.

Update #2: While the examples I gave try to mimic what we expect for math, the solution should work given an arbitrary set of operations. For example:

my $o = (   ',' => 1,
            'j' => 2 );

"_ just another , perl , hacker , j"  =>  
   "_ j ( just , another , perl , hacker )"
[download]

---

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

---

---

• Are you posting in the right place? Check out Where do I post X? to know for sure.
• Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:

  <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>

• Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
• Want more info? How to link or How to display code and escape characters are good places to start.