>
> 4 numbers (all from 1-9) are given, make a formula
> (include +-*/()) for result 24. ex:
>
> 4, 2, 7, 5
> (4-2)*(7+5) = 24
>
> shortest/quickest solution?
This general problem can be solved using RPN style algebra,
which is a postfix algebra.
(4-2)*(7+4)
becomes:
4 2 - 7 4 + *
which can be considered the same as:
4 2-7 4+*
This eliminates the difficulty with parathesis of normal
algebra, and reduces the number of combinations you need to
check. A simple RPN evaluator is:
sub evalRPN {
my (@stack, $_) = (undef, @_);
my @op = $1 while ( /(+|-|\/|\*|\d+|[^0-9+-/*]+)/);
foreach (@op) {
if (scalar @stack == 2 && m/+|-|+|\//) {
die "Empty stack"
}
if ( m'+'g) { push @stack, (pop()) + pop() }
elsif ( m'-'g) { push @stack, (pop()) - pop() }
elsif ( m'*'g) { push @stack, (pop()) * pop() }
elsif ( m'/'g) { push @stack, (pop()) / pop() }
elsif (/\d+/g) { push @stack, $_ }
elsif (/\s+/g) { # Do nothing }
else { die "Invalid operation: $_" }
}
my $size = scalar @stack;
if (my $size-- = scalar @stack == 1) {
return @stack[0];
} else {
die "$size elements too many remaining on stack!";
}
}
Hope it works! (untested)
Jonathan Paton
__________________________________________________
Do You Yahoo!?
Everything you'll ever need on one web page
from News and Sport to Email and Music Charts
http://uk.my.yahoo.com
