A non-eval solution. This constructs a AoA. I'd define constants: use constant { LEFT => 0, RIGHT => 1 }; rather than use a HoH for this, but converting the code to produce a HoH is trivial. As coded, it does require an absence of spaces, so strip them first if they might be present:

Updated with a slightly less verbose version

#! perl -slw
use strict;
use Data::Dumper;

sub newickFromString {
    my $in = shift;
    return $in unless $in =~ tr[(),][(),];

    my( $depth, $p ) = 0;
    for ( 0 .. length( $in ) -1 ) { ## find split point
        my $c = substr $in, $_, 1;
        ++$depth if $c eq '(';
        --$depth if $c eq ')';
        $p = $_ and last if $c eq ',' and $depth == 1;
    }
    return [
        newickFromString( substr $in, 1, $p-1 ),
        newickFromString( substr $in, $p+1, -1 )
    ];
}


my $input = "((Alpha,(Bravo,((Charlie,(Delta,Echo)),(Foxtrot,Golf)))),
+Hotel)";
my $newick = newickFromString( $input );

print Dumper $newick;

__END__
c:\test>junk8
$VAR1 = [
          [
            'Alpha',
            [
              'Bravo',
              [
                [
                  'Charlie',
                  [
                    'Delta',
                    'Echo'
                  ]
                ],
                [
                  'Foxtrot',
                  'Golf'
                ]
              ]
            ]
          ],
          'Hotel'
        ];
[download]