Parsing is quite possibly not required. Assuming that the variables can be assumed to contain a true value why not just leverage perl.

$str =~ s/\*/&&/g;
$str =~ s/\+/||/g;
# $str =~ s/'/!/g;
$str =~ s/(\w+)'/!$1/g;
$str =~ s/\(([^\)]+)\)'/!($1)/g;
$str =~ s/\w+/1/g;
my $truth = eval $str;
[download]

If the a/b/A/B vars have associated values all that is required is to substitute them in. Perl does the parsing and calculates the truth.

Update

Modified to deal with ' postfix syntax

$str =~ s/'/!/g;
[download]

is not sufficient to convert a postfix operator to a prefix operator. "a'" produces the invalid code "1!".

$str =~ s/(\w+)'/!$1/g;
$str =~ s/\(([^\)]+)\)'/!($1)/g;
[download]

s/(\w+)'/!\1/g

Rule One: Do not act incautiously when confronting a little bald wrinkly smiling man.

or as use warnings; would say...

\1 better written as $1
[download]

and use diagnostics; would elaborate...

    (W syntax) Outside of patterns, backreferences live on as variable
+s.
    The use of backslashes is grandfathered on the right-hand side of 
+a
    substitution, but stylistically it's better to use the variable fo
+rm
    because other Perl programmers will expect it, and it works better
+ if
    there are more than 9 backreferences.
[download]

Is (a+b)' disallowed?