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/
--~------------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: <mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--