in reply to Convert delimited string into nested data structure

You need a stack, but not recursion. For each item, split it on the delimiter. Count the parts. That is your current level. If the current level is the same as the level of the element on top of the stack, pop the stack and push the current item onto it. If the current level is deeper than the top of the stack, push the current item. If the level is smaller (shallower) than the top of the stack, pop until the stack top has a smaller level than the current node, then push the current node.

After popping to the right level, and BEFORE pushing the current node, insert information from the current node into the array owned by the current stack top.

Your nodes are ok, except that I would add level to name and children. Also, add a dummy root node at level 0.

Phil

  • Comment on Re: Convert delimited string into nested data structure

Replies are listed 'Best First'.
Re^2: Convert delimited string into nested data structure
by Anonymous Monk on Feb 19, 2007 at 18:56 UTC
    I followed you all the way up until the fifth sentance:

    "If the current level is the same as the level of the element on top of the stack ..."

    What is the "element" you are talking about? What are you storing in the stack? How can I attach children using this method?

    Thanks.

[reply]
      Perhaps I should show a bit of code... 
      my @stack = { name => 'root', level => 0, children => [] };

foreach my $input ( @inputs ) {
    my @pieces = split /\s+\/\s+/, $input;
    my $level  = scalar @pieces;

    my $new_node = { name => pieces[-1], level => $level };

    if ( $level == $stack[-1]{level} ) {
        pop @stack;
    }
    elsif ( $level < $stack[-1]{level} ) {
        pop @stack while ( $level <= $stack[-1]{level} );
    }
    # else top level must be our parent
    push @stack[-1]{children}, $new_node;

    push @stack, $new_node
}

      [download]
      I wrote this up a few years ago.

      Phil

[reply]
[d/l]
        Hi. Thanks for the code, but it has an awful lot of syntax errors in it. Here is the corrected version: 
        foreach my $input ( @inputs ) {
    my @pieces = split /\s+\/\s+/, $input;
    my $level  = scalar @pieces;

    my $new_node = { name => $pieces[-1], level => $level };

    if ( $level == $stack[-1]->{level} ) {
        pop @stack;
    }
    elsif ( $level < $stack[-1]->{level} ) {
        pop @stack while ( $level <= $stack[-1]->{level} );
    }
    # else top level must be our parent
    push @{ $stack[-1]->{children} }, $new_node;

    push @stack, $new_node;
}

        [download]
        Anyways ... this works like a charm. Thanks a lot. :)
[reply]
[d/l]
        No, I am afraid I spoke too soon. This does not work at all. Your code produces the following: 
        $VAR1 = [
  {
    'level' => 0,
    'name' => 'root',
    'children' => [
      {
        'level' => 1,
        'name' => 'one',
        'children' => [
          {
            'level' => 2,
            'name' => 'bar'
          },
          {
            'level' => 2,
            'name' => 'baz',
            'children' => [
              {
                'level' => 3,
                'name' => 'two'
              },
              {
                'level' => 3,
                'name' => 'three'
              },
              {
                'level' => 3,
                'name' => 'four'
              }
            ]
          }
        ]
      },
      {
        'level' => 1,
        'name' => 'five'
      }
    ]
  },
  $VAR1->[0]{'children'}[1]
];

        [download]
        'one' does not have any children.

        Sorry, but this won't work for me either. Maybe this is a harder problem than I thought it would be.

[reply]
[d/l]

In Section Seekers of Perl Wisdom