Balanced braces

I wanted to write a JavaScript function that checked for balanced braces. I'd be grateful for any feedback on correctness and style.

var invert = {
    '}': '{',
    ']': '[',
    ')': '(',
};

/**
 * Returns `true` if braces are balanced. 
 * `false` otherwise.
 * Usage: `isBalanced('{{[(')`
 */
function isBalanced(str) {
    var arr, count, curr;

    arr = splitAndFilter(str);

    /**
     * For strings containing 
     * no relevant characters, 
     * return true.
     */
    if (!arr.length) {
        return true;
    }

    count = {
        '(': 0,
        '[': 0,
        '{': 0,
    };

    for(;(curr = arr[0]) && curr; arr = rest(arr)) {
        if (isOpening(curr)) {
            count[curr] += 1;
        } else if (isPrematureClosing(curr, count)) {
            count[invert[curr]] -= 1;
            break;
        } else {
            count[invert[curr]] -= 1;
        }
    }

    return Object.keys(count)
        .every(k => count[k] === 0);
}

function splitAndFilter(str) {
    return str.split('')
        .filter(i => isOpening(i) || isClosing(i));
}

function rest(arr) {
    return arr.slice(1);
}

function isPrematureClosing(c, count) {
    return isClosing(c) && (count[invert[c]] === 0);
}

function isOpening(c) {
    return /[\{\[\(]/.test(c);
}

function isClosing(c) {
    return /[\}\]\)]/.test(c);
}

console.log('true: ', isBalanced(''));
console.log('true: ', isBalanced('({[]})'));
console.log('true: ', isBalanced('{}[]()'));
console.log('true: ', isBalanced('{{}}[[{}]]()'));
console.log('true: ', isBalanced('({})[]'));
console.log('false: ', isBalanced('())'));
console.log('false: ', isBalanced('()))'));
console.log('false: ', isBalanced('(()))'));
console.log('false: ', isBalanced('()))('));
console.log('false: ', isBalanced('()))({'));
console.log('false: ', isBalanced('({[})'));
console.log('false: ', isBalanced('({}){'));
console.log('false: ', isBalanced('()}{'));

Now assuming that we just ignore other characters, and just balance braces, then...

The first problem I see is during the parsing of the expression. Your test calls isOpening and isClosing to determine if it's a valid brace. The problem here is that on each call, you create a regular expression. They're potentially heavy, and very slow. An alternative would be to have a string of valid braces, and use indexOf to see if they're in there. There's also that rest function you call on your for loop which is slicing an array. slice creates a new shallow copy of the original array. You don't want to be creating arrays for each iteration.

Next is your algorithm which is... uhm... ok. However, your function parses all the way to the end even when there's an error in the middle. It doesn't bail out. Next is there's no debugging. I will know that it's not balance, but do I know where exactly? A thrown error is good since it makes no sense proceeding if you know it's not balance.

For an alternative solution, the simplest solution for this is using a stack. When you see an opening, you push to the stack. When it's a closing, you pop from the stack. An imbalance would be simply be:

• An empty stack when you still encountered a closing brace (excess closing)

• A non-empty stack when you already parsed everything (lack closing)

• Or a mismatch of popped value and the closing value.

Here's my take on it:



function isBalanced(expression){

// Our "stack" which is just an array.
var stack = [];

// Used to determine the correct closer for the popped opener
var pairs = {
'{': '}',
'[': ']',
'(': ')',
};

// The reason for not filtering is we need the index for error reporting.
expression.split('').forEach(function(brace, index){

// Since index starts with zero, we increment to make sense.
var position = index + 1;

if(!~'({[)}]'.indexOf(brace)){

// If it's not a brace, return early. It doesn't affect anything.
// We just need to take them into account for positioning.
return;

} else if(~'({['.indexOf(brace)){

// If it's an opening, push to the stack
stack.push(brace);

} else if(!stack.length){

// We have exhausted the stack but we have a closer
throw new Error('Syntax Error: Unexpected ' + brace + ' at ' + position);

} else if(~')}]'.indexOf(brace)){

var braceToClose = stack.pop();
var expectedCloser = pairs[braceToClose];

// If there was a mismatch in closing
if(brace !== expectedCloser){
throw new Error('Syntax Error: Expecting ' + braceToClose + ' at ' + position);
}
}
});

// If we still need closing, throw an error with the next brace to close
if(stack.length){
throw Error('Syntax Error: Expecting ' + pairs[stack.pop()] + ' at ' + expression.length);
}

return true;

}

// Check console
console.log('true: ', isBalanced(''));
console.log('true: ', isBalanced('({[]})'));
console.log('true: ', isBalanced('{}[]()'));
console.log('true: ', isBalanced('{{}}[[{}]]()'));
console.log('true: ', isBalanced('({})[]'));
console.log('false: ', isBalanced('())'));
console.log('false: ', isBalanced('()))'));
console.log('false: ', isBalanced('(()))'));
console.log('false: ', isBalanced('()))('));
console.log('false: ', isBalanced('()))({'));
console.log('false: ', isBalanced('({[})'));
console.log('false: ', isBalanced('({}){'));
console.log('false: ', isBalanced('()}{'));

StackExchange Code Review Q#109482, answer score: 4