Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??
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 };
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

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

In reply to (Golf) 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!
  • 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, 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, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            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.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others rifling through the Monastery: (12)
    As of 2014-09-19 17:35 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      How do you remember the number of days in each month?











      Results (143 votes), past polls