Finding broken parenthesis?

Question

Is there an efficient algorithm for finding broken parenthesis in a block of text for the purpose of intellisense error highlighting?

For instance:

function f() {
    var a = [1, 2, 3];
    if ((a[1] < 1) || (a[0] > 2)) {
        console.log((a + 5).toString());
    }
}

Where any (, ), [, ], {, or } character might be dropped or adding in correctly and the correct issue might be highlighted, for instance spotting the specific statement, function, conditional, etc level item causing the issue?

Answer 1

The algorithm is not difficult:

• Have a stack of characters
• For each character in the code:
  • If it's an opening bracket, push it onto the stack
  • If it's a closing bracket, pop one char from the stack, both must match
• At the end the stack must be empty

Then you could maybe highlight the unmatched bracket(s).

Answer 2

I think that one way of approaching your problem is to validate the matching bracket groups. This may be achieved using the regular expression - see: http://blog.stevenlevithan.com/archives/javascript-match-nested of Steven Levithan.