Validate parentheses "()" and "[]" are balanced

Question

Firstly I was using regex to get if the number of parentheses in a string is balanced or not, but the performance was quite slow when any large string was passed to the regex. So I created this custom method, which returns whether a string contains balanced parentheses or not. Please review this code and point out any mistakes and improvements.

checkBalancedBrackets(str) {
    var b1 = [];
    var b2 = [];
    for ( var i=0; i < str.length; i++ ) {
        var ch = str.charAt(i);
        if (ch == "(" ) b1.push(ch);
        else if ( ch == "[" ) b2.push(ch);
        else if ( ch == ")" ) {
            if (b1.length < 1) {
                return false;
            } else {
                b1.pop();
            }
        }
        else if ( ch == "]" ) {
            if (b2.length < 1) {
                return false;
            } else {
                b2.pop();
            }
        }
    }
    return b1.length == 0 && b2.length == 0;
}

Answer 1

A short review;

• checkBalancedBrackets("([)]") returns true, not sure that was the intention
• b1 and b2 are not great names, what does the b stand for?
• Using arrays is not needed, all the code does is counting numbers, you can just use numbers
• The inconsistent use of curly braces in your if and else if clauses is not good

Answer 2

You have the right idea, and your function almost works, but your code is only checking that ( is balanced with ), and [ is balanced with ]. So it will handle cases like aaa(bbb[ccc]ddd)eee correctly. But it will also accept aaa(bbb[ccc)ddd]eee, and that is wrong.

You should only have a single stack, and you should push all the opening brackets onto it. When you get a closing bracket, pop off the most recent opening bracket and make sure it matches.

Here I've taken your code and replaced the two stacks with one, which I've given a more meaningful name.

def checkBalancedBrackets(str) {
    var bracketStack = [];
    for (var i=0; i < str.length; i++) {
        var ch = str.charAt(i);
        // For opening brackets, we push the character that will match them
        if      (ch == "(") bracketStack.push(")");
        else if (ch == "[") bracketStack.push("]");
        else if (ch == ")" || ch == "]") {
            if (bracketStack.length < 1) {
                return false;
            } else {
                match = bracketStack.pop();
                if (ch != match) {
                    return false
                }
            }
        }
    }
    return bracketStack.length == 0;
}

Answer 3

The only numbers one should use in coding are 0, 1, and many.

This code implicitly uses 2, the number of special cases, "[]" and "()", for which you wrote code. So right away you know the fundamental design is wrong.

If this were a real program and next week your boss told you to handle "<>" as well, you'd have to write another section of code. Then next year you're asked to handle "«»" too. If it had been written properly, each time you'd only have to add those characters to a table and not make any changes to the actual code. As it is, you'll have to make extensive changes to the code, especially if you've already corrected it to check for proper nesting (e.g. "[(])" is wrong).

The key to writing this is keeping track of what state your string is in at any point: which bracket type is it immediately within. Hint: try stacking the opening characters as you encounter them.