Beefy Boxes and Bandwidth Generously Provided by pair Networks
"be consistent"
 
PerlMonks  

Re: a timid approach to parsing arithmetic expressions in perl

by AltBlue (Chaplain)
on Jul 26, 2008 at 17:17 UTC ( [id://700305]=note: print w/replies, xml ) Need Help??


in reply to a timid approach to parsing arithmetic expressions in perl

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

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://700305]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others cooling their heels in the Monastery: (2)
As of 2024-06-15 11:47 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?
    erzuuli‥ 🛈The London Perl and Raku Workshop takes place on 26th Oct 2024. If your company depends on Perl, please consider sponsoring and/or attending.