Regex for matching curly braces

Question

I'm, looking for a regular expression that will match only when all curly braces properly match. Matching braces can be nested.

Ex. Matches

Hello {0}{}
Hello to the following {0}: {{Object1}}, {{Object2}}
Test { {1} { {2} { {3} { {4}}}}}

Non-matches

}{Hello {0}
{{}Hello to the following {0}: {{Object1}}, {{Object2}}
Test { {1} { {2} { {3} { {4}{}

In what language? Most languages don't support nested regex matching, so you need to do this with a set of functions. — wolffer-east, Aug 28 '14 at 15:36
@wolffer-east: I'm doing it in VB. I hoped though that it could be solved using pure Regular Expression syntax. When you say 'most', does that imply that some do? — Jeremy Friesen, Aug 28 '14 at 15:38
possible duplicate of [Can regular expressions be used to match nested patterns?](http://stackoverflow.com/questions/133601/can-regular-expressions-be-used-to-match-nested-patterns) — wolffer-east, Aug 28 '14 at 15:38
Just count all the { and all the } and make sure the count is the same. — Derek, Aug 28 '14 at 15:38
@Derek: The first Non-matching example would pass in that case. Not good. — Jeremy Friesen, Aug 28 '14 at 15:39
@JeremyFriesen looks like .NET might have the ability, though I haven't used it myself: http://www.regular-expressions.info/balancing.html — wolffer-east, Aug 28 '14 at 15:41
Why don't you compare the count of `{` and `}` and then evaluate potentially valid strings with this expression: `/^[^}]*\{?/` (which will look for an optional `{` without any `}` before it). — Sam, Aug 28 '14 at 15:44
I'm thinking you iterate character by character keeping a count of open and closed. If numClosed is ever greater than numOpen return false. At the end return ( numClosed == numOpen ) — Derek, Aug 28 '14 at 15:46
I have used a function that matches until an opening, then matches until another opening or closing bracket, keeping track of the depth. every time it finds an opening item depth goes up one, every time a close it goes down. if depth ever hits -1 it breaks, and if at the end depth is 0 then you have a correctly formatted string — wolffer-east, Aug 28 '14 at 15:48

score 2 · Accepted Answer · answered Aug 28 '14 at 15:47

2

In .NET you can use balancing groups to count, which allows you to solve such problems.

For example make sure { and } are balanced you could use an expression like:

(?x)^
[^{}]*
(?: 
  (?:
    (?'open' \{ )       # open++
    [^{}]*
  )+
  (?:
    (?'close-open' \} ) # open--, only if open > 0
    [^{}]*
  )+
)*
(?(open) (?!) )         # fail if open != 0
$

answered Aug 28 '14 at 15:47

Qtax

33,241
9
83
121

1

Here are a couple of more similar examples: http://stackoverflow.com/questions/15752778/regex-w-balancing-group-that-matches-not-only-the-outmost-matches/15753431#15753431 http://stackoverflow.com/questions/17003667/match-text-surrounded-by-and/17003704#17003704 – Qtax Aug 28 '14 at 15:51
Awesome! thanks, I just tested this against my exampples and it passed with flying colours. Simply amazing. I don't understand one bit of it, so I guess I have some reading to do! – Jeremy Friesen Aug 28 '14 at 16:00

score 2 · Answer 2 · answered Aug 28 '14 at 15:49

2

bool BracesMatch( string s )
{
  int numOpen = 0, numClosed = 0;
  foreach( char c in s.ToCharArray() )
  {
     if ( c == '{' ) numOpen++;
     if ( c == '}' ) numClosed++;
     if ( numClosed > numOpen ) return false;
  }
  return numOpen == numClosed;
}

answered Aug 28 '14 at 15:49

Derek

7,615
5
33
58

Did you see this? "if ( numClosed > numOpen ) return false;" – Derek Aug 28 '14 at 15:55
2

@Tensibai he checks `if ( numClosed > numOpen ) return false` on each character, so your example doesn't pass: http://ideone.com/JUkyLZ – nodakai Aug 28 '14 at 16:19

score 1 · Answer 3 · 2014-08-28T16:17:33.060

This might work using the Dot-Net balanced groups as well.

 # @"^[^{}]*(?:\{(?>[^{}]+|\{(?<Depth>)|\}(?<-Depth>))*(?(Depth)(?!))\}[^{}]*)*[^{}]*$"

 ^ 
 [^{}]*                        # Anything (but only if we're not at the start of { or } )
 (?:
      \{                            # Match opening {
      (?>                           # Then either match (possessively):
           [^{}]+                        #   Anything (but only if we're not at the start of { or } )
        |                              # or
           \{                            #  { (and increase the braces counter)
           (?<Depth> )
        |                              # or
           \}                            #  } (and decrease the braces counter).
           (?<-Depth> )
      )*                            # Repeat as needed.
      (?(Depth)                     # Assert that the braces counter is at zero.
           (?!)                          # Fail this part if depth > 0
      )
      \}                            # Then match a closing }. 
      [^{}]*                        # Anything (but only if we're not at the start of { or } )
 )*                            # Repeat as needed
 [^{}]*                        # Anything (but only if we're not at the start of { or } )
 $

Regex for matching curly braces

3 Answers3

Linked

Related