http://qs1969.pair.com?node_id=81969

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

Replies are listed 'Best First'.
Re: (Golf) Reversing RPN Notation
by chipmunk (Parson) on May 21, 2001 at 19:32 UTC
    The tricky part for me was coming up with a good way to determine when parentheses should be used. I decided to save the operator priority of each term, so I could compare it to the priority of the next operator. I'm interested to see how other people tackle this problem.

    118 characters in the body of the sub:

    %o = ('+' => 1, '-' => 1, '*' => 2, '/' => 2, ); sub rpn2ltr { for$i(@r=@_){if($p=$o{$i}){$_=$p>$_->[0]?"($_->[1])":$_->[1] for$r=pop,$l=pop}push@_,[$p||9,$p?"$l $i $r":$i]}$_[-1][1] }
      This problem is trickier than it seems:
      print rpn2ltr qw(2 3 4 + -); # output : 2 - 3 + 4 # should be : 2 - (3 + 4)
         MeowChow                                   
                     s aamecha.s a..a\u$&owag.print
        Ouch, that's a good point. Well, I don't think there's any way to solve that problem with the data that's provided. The operator hash would need to specify which operators are commutative and which aren't.

        In fact, the problem requirements state:

        Operations of the same priority can be considered to be commutative, and can be evaluated in any order.
        [fixed spelling]

        So, I solved the problem as stated, although the problem as stated doesn't quite reflect actual arithmetic.

        Update: Oops, I'm confusing commutative (order doesn't matter) with associative (grouping doesn't matter). Subtraction is neither commutative nor associative, but the problem MeowChow pointed out involves associativity. The operator hash would need to specify which operators are associative. Either way, there's not enough information available for a perfect solution.

        With the hash that I gave, that solution is correct.

        If the hash was, instead

        %o = ( '-' => 1, '+' => 2, '*' => 3, '/' => 3 );
        then the code would produce the second, correct solution. In other words, the code's correct, the givens are just wrong :-)


        Dr. Michael K. Neylon - mneylon-pm@masemware.com || "You've left the lens cap of your mind on again, Pinky" - The Brain
        Both output :   2 - 3 + 4   and   2 - (3 + 4)   are correct but the first one is better because "minimize the use of parentheses". It seems to be good.

        Update: MeowChow points something right !! I was dreaming when I read his post, forget it :)

        BobiOne KenoBi :)

Re: (Golf) Reversing RPN Notation
by chipmunk (Parson) on May 21, 2001 at 22:02 UTC
    Like I said before, figuring out when to use parens is the tricky part. :) MeowChow pointed out that my solution didn't account for operators which aren't associative ("2 3 4 + -" should be "2 - (3 + 4)" instead of "2 - 3 + 4"). Then I noted that this information was missing from the data provided in the original problem.

    I decided to tackle the problem of associativity, and came up with this solution, at 171 characters in the body of the sub:

    %o = ('+' => 1, '-' => 1, '*' => 2, '/' => 2, ); %a = ('-' => 1, '/' => 1, ); sub rpn2ltr { for$i(@r=@_){if($p=$o{$i}){$r=$p>($r=pop)->[0]||($p==$r-> [0]&&$a{$i})?"($r->[1])":$r->[1];$l=$p>($l=pop)->[0]?"($l->[ 1])":$l->[1]}push@_,[$p||9,$p?"$l $i $r":$i]}$_[-1][1] }
    It's pretty ugly. :/ I hope someone will provide a more elegant solution!
Re: (Golf) Reversing RPN Notation
by Arguile (Hermit) on May 22, 2001 at 04:07 UTC
    <body bgcolor="#ffffff"> I tried to implement this even in expanded code, but my grasp of Perl is still a little too loose. Expanding chipmunk's code didn't really help any either (I couldn't seem to expand it properly.. maybe it's just lack of sleep ;). So instead of submitting a golfed answer, I'd like to submit up the reasoning behind what I tried to implement to see if I was even on the right track. And if it was on the right track, maybe someone will benefit from the approach.

    The basic idea behind the approach is to only examine three (3) elements of the stack at a time and work solely on those until the entire stack is resolved. Our three element pattern will consist of two numbers, and an operand. So if we test the three elements against the operator hash, 0 0 1 will be the truth values returned. Represented here as:

         

    We'll now populate the stack with a test case 3 4 5 / + 2 * and go through converting it to the end string.

    i=1: <tr align="center" bgcolor="#ffffff"">
    3 4 5 / + 2 *
    3 4 X        

    The first iteration didn't return a match so move on position along the stack.

      You have the right idea. Perhaps this will help you get started:
      sub rpn_ptree { my@s;$o{$_}?$s[--$#s]=[$_,@s[-2,-1]]:push@s,$_ for@_;@s }
      It's a pretty well-golfed sub that builds a parse tree out of an RPN expression. The only tricky part is the --$#s, which simultaneously pops off the top element of @s (by assigning to $#s), and returns the index of the new end of the array. And here's another way to build a parse tree:
      sub rpn_ptree { my$i;$o{$_[$i]}&&splice@_,$i-=2,3,[@_[$i..$i+2]]while++$i<@_;@_ }
         MeowChow                                   
                     s aamecha.s a..a\u$&owag.print
Re: (Golf) Reversing RPN Notation
by bobione (Pilgrim) on May 22, 2001 at 16:58 UTC
    Well, I made my better but it is not enough. I am happy to solve a part of this problem. Here my small contribution :
    (I use special variable $, $/ and $; to minimize declaration)

    sub LTR { # 116 characters my@a;for(@_){if(/\d/){push@a,$_}else{$/=pop@a; $,=join' ',pop@a,$_,$/;$,=~s/(.*)/($1)/ if((/[+-]/);push@a,$,;$;=$ +_}}@a } print LTR qw(1 2 - 3 4 + 5 * /);

    My solution don't really minimize brackets :( (but seems to be correct most of the time; more brackets are better than less :))

    Another problem is that I don't use %operator because it wasn't really helpful (without last change). So It can't solve Update #2 from Masem (I only see it now).

    This problem is very tricky... When should we use brackets or not ???
    Congratulation to chipmunk and MeowChow for their contributions.

    BobiOne KenoBi ;)