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,
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'.my %priorities = { '+' => 1, '-' => 1, '*' => 2, '/' => 2 };
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
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 )"
Dr. Michael K. Neylon - mneylon-pm@masemware.com || "You've left the lens cap of your mind on again, Pinky" - The Brain