5

Possible Duplicate:
Can regular expressions be used to match nested patterns?

How do I use regular expressions to search for a pair of opening and closing brackets with arbitrary number of nested brackets inside it e.g.

(...(...(...(...) ...) ...) ...)

Each opening bracket must be matched by a closing bracket. And the number of nested opening-closing pair is arbitrary. Other alphanumeric characters may appear inside the brackets.

Community
  • 1
  • 1
JavaMan
  • 4,954
  • 4
  • 41
  • 69
  • What are you trying to achieve? (Do you just want to make sure there are an equal number of open and close parenthesis?) – John Parker Dec 31 '10 at 09:41
  • 7
    Regular expressions aren't always the answer - you can simply scan through the string and use a stack to verify the proper nesting of brackets. – asdfjklqwer Dec 31 '10 at 09:43
  • 4
    You can't. Arbitrarily-nested parentheses are a classical example of a non-regular context-free language, i.e. a classical regexp simply isn't expressive enough. – Ulrich Schwarz Dec 31 '10 at 09:50
  • This is possible and even quite easy with most modern flavors of regex engines - though a loop and a counter are even simpler. What language are you using? And what are you doing - are you validating an expression, or trying to capture something? – Kobi Dec 31 '10 at 10:48
  • @Kobi: If they can do a proper arbitrarily-nested brackets test *without an enclosing loop*, they're not RE engines. Instead, they're in the next complexity class up, which is what can be matched by a NFA with a counter. (For reference, with an NFA and two counters that can handle arbitrarily big numbers, you've got a Turing Machine.) – Donal Fellows Dec 31 '10 at 15:38
  • @Donal - It is safe to assume most modern engines can accept non regular languages (`(.+)\1`, for one). "Regex" is used anyway, as a term: http://en.wikipedia.org/wiki/Regex#Patterns_for_non-regular_languages – Kobi Dec 31 '10 at 15:48
  • 1
    @Kobi: Nonetheless, you still can't tackle the nested-parens problem with a regex unless the engine either supports a counter or you've got some kind of outer loop. – Donal Fellows Dec 31 '10 at 16:06
  • @Donal - Something like `\\((?R)*\\)|[^()]+` in most flavors. Not that bad.. – Kobi Dec 31 '10 at 23:22
  • @Kobi: Actually, that's a feature of the Perl engine and the (widely used) PCRE engine. Those engines expose their implementation details quite a lot (which lets them do those features) at a cost of having some really nasty performance cases and general potential for trouble with stack consumption. The automata-theoretic engines don't (indeed, *cannot*) do recursive matching and have a more complex compilation strategy, but do have much more predictable resource consumption when doing the actual matching. – Donal Fellows Jan 01 '11 at 00:40

1 Answers1

1

If you really want to use RegEx to do it(i'm not sure it's the good way), you can loop until this regex \([^\(\)]*\) returns nothing, and for each times you get something you have to remove the result in the initial and loop again...

SeeSoft
  • 91
  • 3