in reply to (Golf) Reversing RPN Notation
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@_,[$p9,$p?"$l $i $r":$i]}$_[1][1]
}
Re: Re: (Golf) Reversing RPN Notation by MeowChow (Vicar) on May 21, 2001 at 20:33 UTC 
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  [reply] [d/l] 

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.
 [reply] 

The purpose of associativity is to resolve ambiguities between operators of equal precedence. Associativity isn't specified on a "yes/no" basis, but on lefttoright, or righttoleft basis. All trivial arithmetic operators excluding exponentiation are lefttoright.
MeowChow
s aamecha.s a..a\u$&owag.print  [reply] 

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  mneylonpm@masemware.com

"You've left the lens cap of your mind on again, Pinky"  The Brain
 [reply] [d/l] 

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



 [reply] 

Uh, no, addition and subtraction are lefttoright 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  [reply] [d/l] 

