Braces

sangam1 has asked for the wisdom of the Perl Monks concerning the following question:

$_ = q!0a { 1a { 1.1a } 1b { 1.2a    } 1c { 1.3a 1.3b }  } 0b { 2a { 2
+.1a}  } 0c!;
        
while(m!{[^{]+(({.*?})*)[^{]+}!g){
        $inside = $1; 
        print $&,"\n";
        while($inside =~ m!{[^{]+(({.*?})*)[^{]+}!g){
                print "\t",$&,"\n";
        }
}
[download]

When I run the program:

{ 1a { 1.1a } 1b { 1.2a    } 1c { 1.3a 1.3b }  }
        { 1.1a }
        { 1.2a    }
        { 1.3a 1.3b }
{ 2a { 2.1a}  }
        { 2.1a}

Now you know exactly what I am trying to do... When I change my string to..

$_ = q!0a { 1a { 1.1a } 1b { 1.2a    } 1c { 1.3a { 1.3.1a } 1.3b }  } 
+0b { 2a { 2.1a}  } 0c!;
[download]

I get the output

{ 1a { 1.1a } 1b { 1.2a    } 1c { 1.3a { 1.3.1a } 1.3b }  }
        { 1.1a }
        { 1.2a    }
        { 1.3.1a }
{ 2a { 2.1a}  }
        { 2.1a}

What I want is

{ 1a { 1.1a } 1b { 1.2a    } 1c { 1.3a 1.3b }  }
        { 1.1a }
        { 1.2a    }
        { 1.3a  { 1.3.1a } 1.3b }
                {1.3.1.a}
{ 2a { 2.1a}  }
        { 2.1a}

Thus nested braces upto any level should be taken care..
Any pointers, solutions, hints are appeciated..
Thanks
Sangam..

Comment on Braces Select or Download Code

Replies are listed 'Best First'.
Re: Braces by chipmunk (Parson) on Feb 16, 2001 at 21:18 UTC
Matching nested balanced delimiters with regular expressions is a hard thing to do. Actually, with true regular expressions, it is impossible. Even when backreferences are added, it's still impossible. However, perl5.6 adds experimental features to the regular expression syntax which actually make it possible to match nested delimiters with a single (but complicated :) regular expression. I used the example from perlre from perl5.6 for matching balanced parentheses and came up with this code: `#!/usr/local/bin/perl require 5.006; my $braces; $braces = qr/(\{(?:(?>[^\{\}]+)\|(??{$braces}))\})/; sub extract_braces { my($str, $level) = @_; while ($str =~ m!$braces!g) { my $inside = $1; print "\t" x $level, $inside, "\n"; $inside =~ s/\{(.)\}/$1/; extract_braces($inside, $level + 1); } } my $str = '0a { 1a { 1.1a } 1b { 1.2a } 1c { 1.3a { 1.3.1a } 1.3b } + } 0b { 2a { 2.1a} } 0c'; extract_braces($str, 0); __END__` [download] The experimental regex features used here are `(??{})` for postponed evaluation, and `(?>)` for a non-backtracking match.	[reply] [d/l] [select]
Re: Braces by TheoPetersen (Priest) on Feb 16, 2001 at 21:21 UTC
If you have any books on basic programming, look up recursion. This is the kind of task that computer science profs make up to debate iterative versus recursive programming techniques. To solve this just using loops (iterative technique), you have to build a stack of some sort to keep track of how many levels of braces you've processed. Fortunately Perl makes this trivial by using perlfunc:push and perlfunc:pop. For a recursive technique, take your current while loop and make it a sub. Then call the sub again when you encounter an open brace. Exit the sub when you match the closing brace, and print along the way. You're still using a stack, but it's the call frame stack instead of an array you manipulate yourself.	[reply]
Re (tilly) 1: Braces by tilly (Archbishop) on Feb 16, 2001 at 21:22 UTC
With 5.6 you can solve this with an RE, but you are likely to find it much easier to use Damian's Regexp::Common than figure out how to roll your own.	[reply]
Re: Braces by I0 (Priest) on Feb 17, 2001 at 08:17 UTC
`$_ = q!0a { 1a { 1.1a } 1b { 1.2a } 1c { 1.3a { 1.3.1a } 1.3b } } +0b { 2a { 2.1a} } 0c!; @( = ('(',''); @) = (')',''); ($re=$_)=~s/((\{)\|(\})\|.)/$([!$2]\Q$1\E$)[!$3]/gs; @$ = (eval{/$re/},$@); print join"\n",@$ unless $$[-1]=~/unmatched/;` [download]	[reply] [d/l]