Subject: Re: [xsl] parsing parens in the park From: Liam Quin <liam@xxxxxx> Date: Sun, 28 Sep 2008 19:39:04 -0400 |
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/
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] parsing parens in the par, Dimitre Novatchev | Thread | Re: [xsl] parsing parens in the par, G. Ken Holman |
Re: [xsl] parsing parens in the par, G. Ken Holman | Date | Re: [xsl] Finding paths in Visio XM, Dimitre Novatchev |
Month |