my $par;
my $par_count = 0;
sub parse{
  my ($regex,$input)=@_;
  $input =~ /^__PAREN(\d+)__$/ and return $par->{$1};

  $input=~s/\s//g;
  while( $input =~ /\(([^()]+)\)/ ) {
    my $sub = $1;
    $par->{$par_count} = parse($regex, $sub);
    my $tag = '__PAREN' . $par_count++ . '__';
    $input =~ s/\(([^()]+)\)/$tag/;
  }

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