Short description of the algorithm:

1. give each operator/operand a priority based on it's depth and on a base priority each has.
2. take the biggest priority operand and the 2 operands adjacent to it
3. evaluate the 3 elements extracted at step 2 and put in the array at the place where they were the result of the calculation and the results's priority is decreased by a depth_bonus because it's paranthesis have disappeared.
4. repeat step 2 until the array has just one element(which is the result of the evaluation)

On the surface, it looks like this algorithm should work, however, it seems like you are doing more work than is necessary, and the algorithm reduces basically to an infix-to-postfix conversion combined to a postfix calculation but with a larger big o complexity.

Since you are able to parse and calculate postfix with a single pass through the data and a stack, and convert from infix to postfix with a single pass and stack, I am not certain what this buys you.

As far as your implementation, for educational purposes, go crazy. On my initial scan, I would have concerns with the element selection routine, but it appears that it should work. For performance, I would be concerned with the repeated sorts.

If this is not for educational reasons, then I would seriously consider looking at the algorithms listed above, a parse tree, and a postorder traversal of that tree, as those are probably able to be implemented with less code and less complexity.

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;
}
[download]

For clarity, I always liked recursive descent. As a simple example here's an evaluator for expressions with integer add, subtract, multiply and divide.

update: Now does unary minus, real numbers and parentheses

I was testing something else, when I discovered an expression that generates tons of warnings:

my $exp = 3-(4+5);
[download]

I'd also be interested in seeing a right-associative operator added.

my $exp = 4**3**2;  # = 4**9 = 262144
[download]

Hi ikegami and thank you very much for the interest in this,

Using minor modifictions I've implemented also POW for this evaluator
I've also added as a test the expression "3**(6-1*4)**2" which should eval to 81.
About the warnings , the compiler already evaluated the expression to -6 and the bug
was caused by the fact that negative numbers were not yet recognised.
Now both of these are fixed.

3**(6-1*4)**2 is a bad test since (3**2)**2 happens to equal 3**(2**2)

When I use the 3**4**2 I had previously mentioned, your code returns 6561 ((3**4)**2) instead of 43046721 (3**(4**2)).

>perl -le"print 3**4**2"
43046721
[download]

hmm,seems that the right associative operator must be parsed in a different way...
the problem about evaluating "3**4**2" still persists ...
however if paranthesis are employed and we re-write like this "3**(4**2)" it will be evaluated correctly.
uhm,the only way I can see this as beeing done is by using a stack and putting all 3,4,2 on it
if the operator ** is found and afterwards start emptying the stack by taking two of them,evaling
putting them back and so on.

I think if you space out your priorities a bit more, right associative operators could be handled by adding a bonus to their weight:

As written:
String:  3 ** 2 ** 4
Weights: 2  9 2  9 2
[download]

Now change the algorith as follows:

• Multiply normal weights by some factor, say 10.
• Multiply level bonus by the same value.
• Add 1 to priority for each occurrence of a right associative operator.
• Swap priorities of parens and POW.

String:   3 **  2 **  4
Weights: 20 80 20 81 20

More complex string:
String:   3 **  (   6   -   1   *   4  ) **  2
Weights: 20 80 90 120 140 120 170 120 90 81 20

String:   3 **  (   6   -   4  ) **  2
Weights: 20 80 90 120 140 120 90 81 20

String:   3 **  (   2  ) **  2
Weights: 20 80 90 120 90 81 20

String:   3 **  2 **  2
Weights: 20 80 20 81 20

String:   3 **  4 
Weights: 20 80 20 

String:  81 
Weights: 20
[download]

Obviously, the weakness of this approach is that if you have too many right associative operators at a level, your priorities collide. You can make "too many" arbitrarily large by using a large multiplier for the original priority scheme.

I'll leave actual implementation up to you.