If you trust that the data you're getting is well-formed, you can just use eval. Perl's boolean operators and precedence just happens to be exactly what you've defined, so why not let perl do the work? Taking that approach, it's pretty trivial to suck out the variable names from that expression and then make a truth table ..

my $bool_func = "((S0*B)|((!S0)*A))";
(my $perl_expr = $bool_func) =~ s/([a-zA-Z]\w*)/\$val{$1}/g;

print "Using perl expression: $perl_expr\n";

my @vars = do {
    my %seen;
    grep !$seen{$_}++, $bool_func =~ /([a-zA-Z]\w*)/g;
};

for my $assignment ( 0 .. (2**@vars)-1 ) {
    my %val;

    $val{$vars[$_]} = ( $assignment >> $_ ) & 1
        for 0 .. $#vars;

    my $result = eval $perl_expr;

    print join(", ", map { "$_=$val{$_}" } keys %val),
          " ==> $bool_func=$result\n";
}

__END__
Using perl expression: (($val{S0}*$val{B})|((!$val{S0})*$val{A}))
A=0, S0=0, B=0 ==> ((S0*B)|((!S0)*A))=0
A=0, S0=1, B=0 ==> ((S0*B)|((!S0)*A))=0
A=0, S0=0, B=1 ==> ((S0*B)|((!S0)*A))=0
A=0, S0=1, B=1 ==> ((S0*B)|((!S0)*A))=1
A=1, S0=0, B=0 ==> ((S0*B)|((!S0)*A))=1
A=1, S0=1, B=0 ==> ((S0*B)|((!S0)*A))=0
A=1, S0=0, B=1 ==> ((S0*B)|((!S0)*A))=1
A=1, S0=1, B=1 ==> ((S0*B)|((!S0)*A))=1
[download]

I hope it goes without saying that if you aren't this confident about the state of your input, your solution needs to involve parsing (and therefore validating) the input expression -- either explicitly, or by means of an existing modular solution.