Image for post
Image for post

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);
}

Image for post
Image for post
Made in the United Kingdom

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch

Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore

Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store