Hi,
I had suggested using RPN for solving this problem, but
forgot to say something important... it gives intermediate
results for free. Coded in C this is very fast, and was
used to solve the countdown number game within those 30
seconds.
For those who haven't met RPN, or are looking for a Perlish
impliementation here is a better (working) one than I
posted earlier:
#!/usr/bin/perl -w
use strict;
my @stack;
# Setup function table and pattern
my %ops = ( '+' => sub { $stack[-2] += pop @stack },
'-' => sub { $stack[-2] -= pop @stack },
'*' => sub { $stack[-2] *= pop @stack },
'/' => sub { $stack[-2] /= pop @stack },
'^' => sub { $stack[-2] ^= pop @stack },
'!' => sub { $stack[-1] = fact($stack[-1]) },
'd' => sub { pop @stack },
'p' => sub { print $stack[-1] },
'P' => sub { print pop @stack },
'r' => sub { return $stack[-1] },
's' => sub { @stack[-2,-1] = @stack[-1,-2] },
'c' => sub { @stack = () }
);
# Create re patterns
my $ops = join("|", map { quotemeta } keys %ops);
my $num = qr/\d+(?:\.\d+)?/;
# RPN Expression Evaluator
sub eval_RPN {
$_=shift;
while (/($ops|$num|\s+|.+)/go) {
my $token = $1;
if (exists $ops{$token}) {
$ops{$token}();
}
elsif ($token =~ /\s+/) {
# Do nothing
}
elsif ($token =~ /^$num$/) {
push @stack, $token;
}
else {
die "Don't know what to do with: $_";
}
}
return pop @stack;
}
sub fact {
my ($x, $e) = (abs int shift, 1);
while ($x>1) { $e*=$x-- }
return $e;
}
### TEST ###
print eval_RPN(join " ", @ARGV);
__END__
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
