This is really quick and dirty. Basically, if we can assume that the format is very strict (values don't have any quoting, and commas and parentheses are always in sane places), you can just do some replacements on the input and then eval out a result.

use Data::Dumper;

my $tree_in = '(A,(B,C))';
#my $tree_in = "((A,(B,((C,(D,E)),(F,G)))),H)";

$tree_in =~ s/([^,()]+)/\{VALUE=>"$1"\}/g;
$tree_in =~ s/\(/\{LEFT=>/g;
$tree_in =~ s/,/,RIGHT=>/g;
$tree_in =~ s/\)/\}/g;

print $tree_in, "\n";
my $tref = eval $tree_in;
print Dumper $tref;
__END__
{LEFT=>{VALUE=>"A"},RIGHT=>{LEFT=>{VALUE=>"B"},RIGHT=>{VALUE=>"C"}}}
$VAR1 = { 
          'LEFT' => { 
                      'VALUE' => 'A'
                    },
          'RIGHT' => { 
                       'LEFT' => { 
                                   'VALUE' => 'B'
                                 },
                       'RIGHT' => { 
                                    'VALUE' => 'C'
                                  }
                     }
        };
[download]

As I say, it's quick and dirty, there's no input validation, and the door's wide open to hostile inputs (think, "run arbitrary Perl code"). It wouldn't be too hard to put some rules on the front end to make some of these problems go away, but in the end you may be happier with a more complete parsing solution.

Cool - We get a chance to use the "seldom used" ForceContent=>1 and ContentKey=>'keyname' options of XMLin. :-)

use XML::Simple;

sub parse_newick {
    local $_ = shift;
    s<[(]>[<LEFT>]g; s<[,]>[</LEFT><RIGHT>]g; s<[)]>[</RIGHT>]g;
    XMLin "<opt>$_</opt>", ForceContent => 1, ContentKey => 'VALUE';
}

use Data::Dumper;
print Dumper parse_newick( '(A,(B,C))' );
[download]

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]

Rather than doing all the substr's, couldn't you just do

$in = s/^\((.*)\)$/$1/;
my @splat = split(/,/, $in);
my ( $depth, $left );
while ( my $c = shift @splat ) {
     $left .= ( $left ? ',' : '' ) . $c;
     ++$depth if index($c, '(') >= $[;
     --$depth if index($c, ')') >= $[;
     last if $depth == 0;
}
my $right = join(',', @splat);
[download]

and then recurse on $left and $right? (Maybe searching each time for the parentheses is as hard as substr'ing, though.)

UPDATE: Per BrowserUK's response, the answer seems to be “Yes, but why?” I always thought that substr's were very expensive, but apparently not. Hurrah for premature optimisation!

Rather than doing all the substr's,

What's wrong with substr? You can do dozens (if not hundreds) of substrs in the time it takes to start the regex engine.

---

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

"Too many [] have been sedated by an oppressive environment of political correctness and risk aversion."

Cheers,

Brent

Try http://evolution.genetics.washington.edu/phylip/newicktree.html ...
A user level that continues to overstate my experience :-))

Well, thanks for the tip. I have done this search before. The modules you (and I) found in CPAN are part of the Bioperl suite, and surely because of that, the code you can find there is far more obfuscated (well, maybe this is not exactly the word) than mine.

citromatik

I think the phrase (instead of 'obfuscated') you want is 'general, debugged, maintained, comprehensive and written by someone else so I don't need to bother'.

Probably Bio::Phylo::IO (the module you would actually use) doesn't use exactly the structure you currently use (or think you would like to use) for the internal representation of the trees. But it is likely that the structure the module uses is more generally useful and that the work you want to perform on the structure is already supported among the Bioperl modules.

Update: It is true I've not used Bioperl modules. I looked at the docs for a few before I answered and on the face of it they seemed at reasonably documented. I was reacting to what appeared to me to be a "modules are too complicated" and NIH attitude in the OP's node. My apologies.

---

Perl reduces RSI - it saves typing

$ perl -wde 0
main::(-e:1):   0
DB<1> use Parse::Eyapp::Node
DB<2> x Parse::Eyapp::Node->new('A(B,C)')
0  A=HASH(0x860b980)
   'children' => ARRAY(0x861c874)
      0  B=HASH(0x8628568)
         'children' => ARRAY(0x83284ec)
              empty array
      1  C=HASH(0x861c928)
         'children' => ARRAY(0x852d8a8)
              empty array
1  B=HASH(0x8628568)
   -> REUSED_ADDRESS
2  C=HASH(0x861c928)
   -> REUSED_ADDRESS
[download]