Check brackets are balanced/matching

Question

I have some MS Word documents which I have transferred the entire contents into a SQL table.

The contents contain a number of square brackets and curly brackets e.g.

[{a} as at [b],] {c,} {d,} etc 

and I need to do a check to make sure that the brackets are balanced/matching, e.g. the below contents should return false:

 - [{a} as at [b], {c,} {d,} 
 - ][{a} as at [b], {c,} {d,} 
 - [{a} as at [b],] {c,} }{d,

What I've done so far is extracted all the brackets and stored their info into a SQL table like below: (paragraph number, bracket type, bracket position, bracket level)

3   [   8   1
3   ]   18  0
3   [   23  1
3   ]   35  0
7   [   97  1
7   ]   109 0
7   [   128 1
7   {   129 2
7   }   165 1
7   [   173 2
7   ]   187 1
7   ]   189 0
7   {   192 1
7   }   214 0
7   {   216 1
7   }   255 0
7   {   257 1
7   }   285 0
7   {   291 1
7   }   326 0
7   {   489 1
7   }   654 0

I am unsure how the algorithm will work to do the check on whether the brackets are balanced in each paragraph, and give an error message when they are not.

Any advice would be appreciated!

EDIT:

Code will need to work for the following scenario too;

(paragraph number, bracket type, bracket position, bracket level)

15  [   543 1
15  {   544 2
15  }   556 1
15  [   560 2
15  ]   580 1
15  ]   581 0
15  [   610 1
15  ]   624 0
15  [   817 1
15  ]   829 0

Answer 1

I'm not sure which tool you have available, but here is a tested JavaScript function which validates that all (possibly nested) square brackets and curly braces are properly matched:

function isBalanced(text) {
    var re = /\[[^[\]{}]*\]|\{[^[\]{}]*\}/g;
    while (text.search(re) !== -1) { text = text.replace(re, ''); }
    return !(/[[\]{}]/.test(text))
}

It works by matching and removing innermost balanced pairs in an iterative manner until there are no more matching pairs left. Once this is complete, a test is made to see if any square bracket or curly braces remain. If any remain, then the function returns false, otherwise it returns true. You should be able to implement this function in just about any language.

Note that this assumes that the square and curly brace pairs are not interleaved like so: [..{..]..}

Hope this helps.

Addendum: Extended version for: (), {}, [] and <>

The above method can be easily extended to handle testing all four matching bracket types: (), {}, [] and <>, like so:

/*#!(?#!js\/g re Rev:20150530_121324)
    # Innermost bracket matching pair from 4 global alternatives:
      \( [^(){}[\]<>]* \)  # Either g1of4. Innermost parentheses.
    | \{ [^(){}[\]<>]* \}  # Or g2of4. Innermost curly braces.
    | \[ [^(){}[\]<>]* \]  # Or g3of4. Innermost square brackets.
    | \< [^(){}[\]<>]* \>  # Or g4of4. Innermost angle brackets.
!#*/
function isBalanced(text) {
    var re = /\([^(){}[\]<>]*\)|\{[^(){}[\]<>]*\}|\[[^(){}[\]<>]*\]|\<[^(){}[\]<>]*\>/g;
    while (text.search(re) !== -1) { text = text.replace(re, ''); }
    return !(/[(){}[\]<>]/.test(text));
}

Note the regex has been documented in an extended mode C comment.

Edit 20150530: Extended to handle a mix of all four matching bracket types: (), {}, [] and <>.

Answer 2

does this have to be on sql server ?

a simple solution would be to use a general purpose language and use a stack.

• Read the string character by character
• if you encounter a opening brace push it to stack.
• if you encounter a closing brace pop.

All brackets are matched if

• after reading the paragraph completely the stack is empty.

UNLESS one of the below happens during the process

• you had to pop an empty stack
• the popped bracket does not match the closing bracket

its not a good idea to use regex to match brackets, they are not meant to be used like that

Answer 3

I agree with user mzzzzb. I've been working on a coding challenge that is somewhat similar and came up with the following solution in JavaScript:

function isBalanced(str) {
  const stack = [];
  const pairs = { ')': '(', ']': '[', '}': '{' };
  return str.split('').reduce((res, e) => {
    // if its opening, put in stack
    if (['(', '{', '['].includes(e)) stack.push(e);
    // if closing, compare thru stack
    else if ([')', '}', ']'].includes(e)) {
      if (stack.pop() !== pairs[e]) return false;
    }
    return res;
    // stack must also be empty
  }, true) && stack.length === 0;
}