Beefy Boxes and Bandwidth Generously Provided by pair Networks Frank
Just another Perl shrine
 
PerlMonks  

Re: Re: (Golf) Reversing RPN Notation

by MeowChow (Vicar)
on May 21, 2001 at 20:33 UTC ( #82004=note: print w/ replies, xml ) Need Help??


in reply to Re: (Golf) Reversing RPN Notation
in thread (Golf) Reversing RPN Notation

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


Comment on Re: Re: (Golf) Reversing RPN Notation
Download Code
Re: Re: Re: (Golf) Reversing RPN Notation
by bobione (Pilgrim) on May 21, 2001 at 20:46 UTC
    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 :)

      Uh, no, addition and subtraction are left-to-right associative, which means that:
      2 - 3 + 4 = -1 + 4 = 3 while 2 - (3 + 4) = 2 - 7 = -5
         MeowChow                                   
                     s aamecha.s a..a\u$&owag.print
Re: Re: Re: (Golf) Reversing RPN Notation
by chipmunk (Parson) on May 21, 2001 at 20:56 UTC
    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.

      The purpose of associativity is to resolve ambiguities between operators of equal precedence. Associativity isn't specified on a "yes/no" basis, but on left-to-right, or right-to-left basis. All trivial arithmetic operators excluding exponentiation are left-to-right.
         MeowChow                                   
                     s aamecha.s a..a\u$&owag.print
Re: Re: Re: (Golf) Reversing RPN Notation
by Masem (Monsignor) on May 21, 2001 at 22:04 UTC
    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
      A few problems with this:
      • qw(2 3 4 * /) : you forgot to set '/' to 4
      • qw(2 3 4 - -) : this is the biggie
         MeowChow                                   
                     s aamecha.s a..a\u$&owag.print
        Ok, it's probably going to depend on how you decide to pop off the stack. Given "N1 N2 o" in RPN where N1 and N2 are the numbers and o the operation, the LTR should be "N1 o N2".

        Yes, '/' would need to be 4. And yes, the second one poses the problem if there's no indication of order being important on an operation ("a op b" not being equal to "b op a"). Chipmunk's got part of the problem with associtivity in his 171 char solution, but I might need to restate the problem to handle this concept; at the time, I was only aiming for a general solution assuming that order didn't matter.


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

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://82004]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (13)
As of 2014-04-17 14:38 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    April first is:







    Results (450 votes), past polls