Re: parsing parens in the park

On Sun, Sep 28, 2008 at 02:24:05PM -0700, Dimitre Novatchev wrote:
> > 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.

Formally speaking, the complexity of finding an removing () is O(n)
on the number of parens in the string, and we have to do it up to
n/2 times, so yes, N^2.

As usual it's a tradeoff between complexity and memory.  You can
write a program that can handle all possible strings of length L
in O(1) time by precomputing them, but the memory requirements
are rather high as L increases :)

Liam

-- 
Liam Quin, W3C XML Activity Lead, http://www.w3.org/People/Quin/
http://www.holoweb.net/~liam/ * http://www.fromoldbooks.org/