If you're just trying to validate, then it's doable, but you'll need to use an advance trick ((??{ ... })) to handle parentheses. I actually used more regexps than necessary in my solution below — all but $expr can be inlined — but it makes it shorter and more readable.

use strict;
use warnings;

sub is_valid_expr {
   use re 'eval';
   local our ($skip, $term, $expr);
   $skip = qr! \s* !x;
   $term = qr! $skip [a-zA-Z]+
             | $skip [1-9][0-9]*
             | $skip \( (??{ $expr }) $skip \) !x;
   $expr = qr! $term (?: $skip [-+*/] $term )* !x;
   return $_[0] =~ / ^ $expr $skip \z /x;
}

foreach (
   '(a + 3)',
   '(3 * 4)+(b + x)',
   '(5 - a)*z',
   '3 + 2',

   '!3 + 2',
   '3 + 2!',

   '3 a',
   '3 3',
   '3 * * 3',

   '2 - 3 * 4',  # Preceedence test.
   '2 - 3 + 4',  # Associativity test.
) {
   print(is_valid_expr($_)
      ? "$_ is valid\n"
      : "$_ is not valid\n"
   );
}
[download]

Writting a parse using this method would be needlessly difficult. May I recommend that you start with Parse::RecDescent?

Update: For the truly insane:

sub is_valid_expr {
   local our $expr;
   $expr = qr!(?:\s*[a-zA-Z]+|\s*[1-9][0-9]*|\s*\((??{$expr})\s*\))(?:
+\s*[-+*/](?:\s*[a-zA-Z]+|\s*[1-9][0-9]*|\s*\((??{$expr})\s*\)))*!;
   return $_[0] =~ /^$expr\s*\z/;
}
[download]

Update: Added ysth and diotalevi's fixes.

You shouldn't ever be using lexicals with (?{...}) or (??{...}) per ysth's note. That is almost always wrong. Also, your expression (??{ $skip }) is needlessly verbose and wasteful of runtime. Just interpolate $skip like qr/ ... $skip ... /x.

Your code can be implemented with proper recursion in 5.10:

{
    my $skip = qr/\s*/;
    my $expr = qr/ (?<EXPR>

                     # term
                     $skip
                     (?<TERM> [a-zA-Z]+
                       | [1-9]\d*
                       | \( (?&EXPR) $skip \) )
                     # term*
                     (?: $skip [-+*/] (?&TERM) )* )
    /x;
    my $re = qr/^ $expr $skip \z/x;
    sub is_valid { shift =~ /$re/o }
}
[download]

⠤⠤ ⠙⠊⠕⠞⠁⠇⠑⠧⠊

Semi-off topic   Pardon me, but... what is the problem with using lexicals in (?{...}} or (??{...})?

   my ($skip, $re, $expr, $term);

   $skip = qr! \s* !x;

   $re   = qr! ^ (??{ $expr }) (??{ $skip }) \z !x;

   $expr = qr! (??{ $term })
               (?:
                  (??{ $skip }) [-+*/] (??{ $term })
               )*
   !x;
[download]

Careful with that axe. http://groups.google.com/groups?selm=20051012003112.GG4432@iabyn.com