You can simplify code a little bit by moving $node declaration to the inner loop (and I replaced condition $3 with match result):

sub parse
{
    my ($regex,$input)=@_;
    for(@$regex)
    {
        if($input=~m/(.+)($_)(.+)/)
        {
            my ($before,$op,$after,$node)=($1,$2,$3);
            $node->{$op}=[parse($regex,$before), parse($regex,$after)]
+;
            return $node;
        }
    }
    return $input;
}
[download]

and optimize the code by moving $input=~s/\s//g outside parse sub. It is enough to do this once in while loop after reading input data.