Something like this.

@required = $str =~ /\+(\w+)/g;
@optional = $str =~ /(?<![+-])(\w+)/g;
@absent = $str =~ /-(\w+)/g;

$required = @required ? '(' . join(' AND ', @required) . ')' : '';
$optional = @optional ? '(', join(' OR ', @optional) . ')' : '';
$absent = @absent ? '(' . join(' AND ', map "NOT $_", @absent) . ')' :
+ '';

$expr =
    join ' OR ',
        grep length(),
            join(' AND ', grep length(), $required, $absent),
            $optional;
[download]