Looking and your code and algorithm description, I got the same impressions as MidLifeXis: the algorithm is simple (yet limited), correct, but slow. This is a classic problem that computer science students meet many times during their classes, each time using a different algorithm / approach to solve it, and the fellow monks already provided you many pointers (CPAN could be another).
Implementation wise, I'm sorry to say that yours looks like a mechanical line-to-line translation from that other language. Here are a few suggestions:
- don't interpolate when it's not necessary,
e.g. print "DEBUG ".Dumper [@terms];
vs. print 'DEBUG '.Dumper [@terms];
- don't concatenate when it's not necessary, just use the list
e.g. print "DEBUG ".Dumper [@terms];
vs. print "DEBUG ",Dumper [@terms];
- don't clone (duplicate data) when it's not necessary, just pass it by reference
e.g. print "DEBUG ".Dumper [@terms];
vs. print "DEBUG ".Dumper \@terms;
- rewriting regular expression in a more readable manner (using /x modifier)
could help you see easier through the code,
e.g. s/^(\d+|\*|\/|\+|\-|\(|\))//
vs. s{ ^ ( \d+ | \* | / | \+ | - | \( | \) ) }{}x
leading to s{ ^ ( \d+ | [ ( ) * / + - ] ) }{}x
- use Perl's built-in functions unless you have a real reason to avoid them,
e.g. sub delete_at {...}
vs. sub delete_at { return splice @terms, $_[0], 1 }
or sub insert_at {...}
vs. sub insert_at { return splice @terms, $_[0], 0, $_[1] }
- don't comment obvious statements, let code express itself
e.g. $depth++ if $type eq 'OPEN_PARA'; # if we encounter an open paranthesis we increase depth
- use the index of the last element of an array when that's what you need
e.g. 0..(@terms-1)
vs 0 .. $#terms
- sort knows how to sort in reversed order, there's not need to clutter your code
e.g. sort { -1 * ( $terms[$a]->{priority} <=> $terms[$b]->{priority} ); }
vs. sort { $terms[$b]->{priority} <=> $terms[$a]->{priority} }
or - if you are following Damian Conway's advices (from Perl Best Practices) - plug a verbose reverse:
reverse sort { $terms[$a]->{priority} <=> $terms[$b]->{priority} }
- avoid misleading your readers/maintainers: in getPrioritary you "needed to" reverse the results
(@selectedTerms), which then you have to reverse them back in your "main" loop to make them usable.
Better keep your workarounds as self contained as possible, i.e.
my @selectedTerms = reverse map { delete_at $_ } ...
(Of course, in that case there was no need for such workaround, a splice would have sufficed)
Finally, here's a possible rewrite of your code:
#!/usr/bin/perl
use strict;
use warnings;
{
my $OP = { # operator => weight
'+' => 4,
'-' => 4,
'*' => 7,
'/' => 7,
'**' => 8,
'(' => 9,
')' => 9,
};
my $depth_bonus = 1 + ( sort { $b <=> $a } values %{$OP} )[0];
my $ops_re = join q{|},
map { quotemeta } sort { length $b <=> length $a } keys %{$OP};
sub eval_expr {
my $expr = "@_";
my @terms;
my $depth = 0;
while ( $expr =~ s{^ \s* ( \d+ | $ops_re ) }{}xo ) {
if ( $1 eq '(' ) {
$depth++;
}
elsif ( $1 eq ')' ) {
$depth--;
}
else {
push @terms,
[
$1, exists $OP->{$1} ? $OP->{$1} + $depth * $depth
+_bonus : 0
];
}
}
while ( @terms > 1 ) {
my ($op_idx) =
sort { $terms[$b]->[1] <=> $terms[$a]->[1] } 0 .. $#term
+s;
my @elems = map { $_->[0] } @terms[ $op_idx - 1 .. $op_idx
+ + 1 ];
splice @terms, $op_idx - 1, 3, [ eval("@elems"), 0 ];
}
return $terms[0]->[0];
}
}
for (
'3 - ( 4 + 5 )',
'1 + 2 * 3',
'( 1 + 2 ) * 3',
' 5 ** 2 - 2 ** 3',
)
{
my $evaled = eval("$_");
my $expred = eval_expr($_);
printf "%40s = %-20s %s\n", $_, $expred, $evaled;
}
As you may notice, while it preserves you original approach / algorithm / didacticism, it also tries to be more flexible and simplifies some steps, observing that operands do not need priority/weight.
'HTH
