Balancing Braces

Ben Aston
Ben Aston
Nov 3, 2015 · 4 min read

“Write a function isBalanced that returns true if a set of brackets is balanced.”

Test cases

isBalanced('()'); // true
isBalanced('()[]{}'); // true
isBalanced('([()]{})'); //true
isBalanced('('); // false
isBalanced(')'); // false
isBalanced('(]'); // false
isBalanced('([)]'); // false

Analysis

() // The simplest nest.
({}) // The second simplest nest.
({}[]) // A nest containing two sub-nests.
({}{[]}) // Another nest containing two sub-nests.
({})() // Two nests.
Parsing Location            Stack

({[]}) <empty>
^
({[]}) (
^
({[]}) { TOP
^ ( BOTTOM
({[]}) [ TOP
^ {
( BOTTOM

Solution

const OPEN = /^[\{\[\(]/;
const CLOSE = /^[\}\]\)]/;
const INVERT = {
'}': '{',
']': '[',
')': '(',
};
function isBalanced(str) {
var arr, curr, stack, opener;
arr = str.split('');
stack = []; // LIFO!
while (arr.length) {
curr = arr.shift();
if (OPEN.test(curr)) {
stack.push(curr); // Assume openers OK (until end of `arr`).
} else if (CLOSE.test(curr)) {
if (!(stack.length)) {
return false; // Closer without opener in current nest.
}
// `opener` opened the current pair.
// `pop` reveals the previous opener!
opener = stack.pop(curr);
if (opener !== INVERT[curr]) {
return false; // “Mismatched closer”.
}
}
}
// “Missing closer” if anything
// left on the stack, otherwise,
// balanced.
return !(stack.length);
}

Made in the United Kingdom

Ben Aston

Written by

Ben Aston

London, England