regular expression for nested matching braces

[Bengt Richter]

On Thu, 07 Mar 2002 12:13:24 -0500, Tim Peters <tim.one at comcast.net> wrote:

>[Piet van Oostrum]
>> ...
>> In fact python's regular expressions are a little bit stronger than
>> the theoretical ones because of the allowed \n constructs, but still
>> can't count.
>
>If you're into this kind of thing, doing a google search on
>
>    "regular expression" "NP complete"
>
>turns up several linear-time reductions transforming NP-complete problems
>into matching-with-backreferences problems.  IOW, adding backreferences to
>theoretical regexps turns the regexp matching problem from polynomial time
>into "almost certainly" exponential time.  In that sense, backreferences add
>enormous power.  But counting is *really* hard <wink>.
>
With some limitations (use triple quotes for less limitation on input), how about:

 >>> s = "A line of text with {multiple and {nested} braces} to {confuse} re!"
 >>> sl = eval('["'+'"], "'.join('", ["'.join(s.split('{')).split('}'))+'"]')
 >>> sl
 ['A line of text with ', ['multiple and ', ['nested'], ' braces'], ' to ', ['confuse'], ' re!']

then walk the tree as desired.

Regards,
Bengt Richter