Re: make a 24(another practical problem)

[Jonathan E. Paton]

> 
> 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