#!/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 .. $#terms;
            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;
}