Dealing with nested parenthesis in regex

Question

I would like my regex to match when there is a complete set of nested parenthesis of max depth 5. My current code is working but it has an awful time complexity and takes very long for long sets of parenthesis.

^((\\((\\((\\((\\((\\(\\))*\\)(\\(\\))*)*\\))*\\))*(\\((\\((\\((\\(\\))*\\)(\\(\\))*)*\\))*\\))*\\))*)$

Example:

String s = (()());
System.out.println(s.matches(...));

--> prints True.

String s = ()));
System.out.println(s.matches(...));

--> prints False.

How can I change my current code so that it is not only more efficient but also a bit easier to read? Note that I do want this done in regex and that I know it's very simple to do with for loops. Thanks!

Answer 1

If you are only looking for a maximum depth of 5 then you can use the following regexp

(\((\((\((\((\(\))*\))*\))*\))*\))*

You can preveiw the results here http://regex101.com/r/zN1sZ2/1

As a bonus here is some psuedo code you can use to generate this string

var s = "_", depth = 5;
while(depth > 0) {
    s = s.replace("_", "(\\(_\\))*");
    depth--;
}
s = s.replace("_", "");

Now it as simple as changing one variable (depth) if your needs change and using the string s to perform your regexp

Answer 2

Strict regular expressions ( http://en.wikipedia.org/wiki/Regular_expression ) can't do this. Real life programming languages all have "extended" regular expressions, more or less at cost of performance.

What you need (in terms of math) is a push down automaton ( http://en.wikipedia.org/wiki/Pushdown_automaton ).