Re: parsing parens in the park

> Actually if all you need to do is test to see if they match or not,
> you can do easier things.  In an iterative language,
>    while (string has parens) {
>        remove all occurrences of "()"
>        if there were none, signal an error
>    }
>    if you get here without error, it's OK.


It would be good to know that this is an O(N^2) algorithm.



-- 
Cheers,
Dimitre Novatchev
---------------------------------------
Truly great madness cannot be achieved without significant intelligence.
---------------------------------------
To invent, you need a good imagination and a pile of junk
-------------------------------------
Never fight an inanimate object
-------------------------------------
You've achieved success in your field when you don't know whether what
you're doing is work or play



On Sun, Sep 28, 2008 at 2:15 PM, Liam Quin <liam@xxxxxx> wrote:
> On Sun, Sep 28, 2008 at 09:15:45PM +0100, David Carlisle wrote:
>> You can not match nested brackets with regular expressions. (That's more
>> or less the defining restriction which is implied by "regular").
>
> Agreed...
>
>> To match brackets you need to use, in addition to regular expressions, a
>> language that can either count or (equivalently) has a unbounded stack.
>> (Eg recursive function calls).
>
> Actually if all you need to do is test to see if they match or not,
> you can do easier things.  In an iterative language,
>    while (string has parens) {
>        remove all occurrences of "()"
>        if there were none, signal an error
>    }
>    if you get here without error, it's OK.
>
> The XSLT implementaion of this would be recursive though.
>
> Perl regexps can mach parens, and there's an example in the
> "perldoc perlre" or, "man perlre" documentation.
>
> Liam
>
> --
> Liam Quin, W3C XML Activity Lead, http://www.w3.org/People/Quin/
> http://www.holoweb.net/~liam/ * http://www.fromoldbooks.org/