Hi all

I'm trying to write a script that parses recursively simple newick binary trees. For example, having:

(A,(B,C))
[download]

I want to obtain a data structure that represents the binary tree, like:

$VAR1 = {
          'LEFT' => {
                      'VALUE' => 'A'
                    },
          'RIGHT' => {
                       'LEFT' => {
                                   'VALUE' => 'B'
                                 },
                       'RIGHT' => {
                                    'VALUE' => 'C'
                                  }
                     }
        };
[download]

I end up with this small script:

#!/usr/bin/perl

use strict;
use warnings;
use Data::Dumper;

my $leaf = qr/([A-Z]+)/;
my $node = qr/(\(.+\))/;
my $leaf_leaf = qr/^\($leaf,$leaf\)$/;
my $node_leaf = qr/^\($node,$leaf\)$/;
my $leaf_node = qr/^\($leaf,$node\)$/;
my $node_node = qr/^\($node,$node\)$/;

my $nt = "((A,(B,((C,(D,E)),(F,G)))),H)";
my $tree = newick ($nt,undef);
print Dumper $tree;

sub newick {
  my ($t,$tree) = @_;
  if ($t =~ /$leaf_node/){
    my ($leaf,$node) = ($1,$2);
    ins_Leaf_Node ($tree,$leaf, newick ($node,$tree));
  } elsif ($t =~ /$node_leaf/){
    my ($node,$leaf) = ($1,$2);
    ins_Node_Leaf ($tree,newick ($node,$tree),$leaf);
  } elsif ($t =~ /$node_node/){
    my ($node1,$node2) = ($1,$2);
    ins_Node_Node ($tree,newick ($node1,$tree), newick ($node2,$tree))
+;
  } elsif ($t =~ /$leaf_leaf/){
    my ($leaf1,$leaf2) = ($1,$2);
    ins_Leaf_Leaf ($tree,$leaf1,$leaf2);
  } else {
    die "Unrecognized tree branch $t\n";
  }
}

sub create_leaf {
  my ($value) = @_;
  return {
      'VALUE' => $value,
     };
}

sub ins_Node_Node {
  my ($tree,$left,$right) = @_;
  $tree->{LEFT} = $left;
  $tree->{RIGHT} = $right;
  return $tree;
}

sub ins_Node_Leaf {
  my ($tree,$left,$right) = @_;
  $tree->{LEFT} = $left;
  $tree->{RIGHT} = create_leaf ($right);
  return $tree;
}

sub ins_Leaf_Node {
  my ($tree,$left,$right) = @_;
  $tree->{LEFT} = create_leaf ($left);
  $tree->{RIGHT} = $right;
  return $tree;
}

sub ins_Leaf_Leaf {
  my ($tree,$left,$right) = @_;
  my $nodeR = create_leaf ($right);
  my $nodeL = create_leaf ($left);
  $tree->{LEFT}  = $nodeL;
  $tree->{RIGHT} = $nodeR;
  return $tree;
}
[download]

But I have the intuition that there must be a simpler way (or at least less verbose) to solve this.

Any further discussion on how to solve this problem would be welcome

citromatik

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.