GitHub Repo with completed solution code and test suite
What is the aim of the Balanced Brackets algorithm challenge?
“Given a string containing brackets, determine if all brackets have a matching counterpart. If all brackets in the string form balanced pairs, return true. If not, return false”
Note: I use the word “brackets” in this case to refer to parentheses, curly braces, square brackets, and angle brackets (‘), {, [, <, >, ], }, )’). Not every challenge might require you to include all four types!
The first time I looked at this problem, my first instinct was to try to just sort the string into substrings based on whether each character was an open or closing bracket and compare the lengths of the substrings.
That approach may work on the occasional simple string, but it breaks down pretty quickly. We need to know not only that there is a closing bracket for each opening bracket, but also that the specific type of opening and closing brackets match each other. Not only that, if we wanted this function to be useful for any sort of IDE syntax highlighting or other practical application, it would need to identify not only that the opening and closing brackets exist in the correct number and type, but also that they are arranged in the correct order — that every opening bracket has a matching closing bracket in the correct place in the string to actually close it.
This is what is meant by saying that brackets are “balanced” — not only do they exist in the correct number of matching pairs, but that those pairs are arranged correctly so that the closing brackets can balance the opening brackets.
My initial idea for sorting out the string into substrings and comparing substring lengths would clearly break down at multiple intervals of the challenge.
I needed another approach.
STACKS
The tool I ultimately used to solve this algorithm was a data structure I hadn’t used before.
I’ve written before about the benefits of using hash tables and recursive trees to break down complicated tasks. I know that data structures can make amazing tools for deconstructing problems that require algorithmic solutions.
But before trying to tackle this particular problem, I hadn’t had many encounters with stacks¹.
In Javascript, I like to think of them as an array with some restrictive rules.
Normally, arrays in Javascript can be manipulated in a really wide variety of ways. That’s what makes them so handy. That’s the reason why I start most algorithmic solutions by making an empty array. We’ll almost always need one as an environment for manipulating or organizing our data.
Stacks in Javascript are utilized by only operating on an array using the push and pop methods. These methods would push a new element onto the top of the stack, or pop it back off the top, respectively.
While the elements of a regular array can be accessed from any direction (unshifted off the front, pushed onto the back, sliced right into or out of the middle, or just edited in place), I think of a stack as being an array that’s been all sealed up so that it’s inaccessible, except for one door. New things can be pushed in through the door, but then only the most recently added thing, the one directly in front of the door, can be accessed or manipulated in any way. If that element is removed using array.pop(), then the element behind it is now available to be changed or removed. However, if it is not removed but instead a new element is pushed in through the door, the previously accessible element becomes inaccessible again.
This approach is called FILO, or First In Last Out.
(This sort of acronym may be familiar to anyone who’s worked in or around kitchens, which are inevitably ruled by the related but opposite law of FIFO, or First In First Out in the attempts to avoid food waste and spoilage.)
Why would we intentionally limit our lovely versatile arrays like this though?
Well, this process preserves a particular order — the elements can only be removed in the order that they were initially added, preserving the original order, or pattern.
Which is exactly what we need to do with our brackets — identify not only the number and type of brackets included in our string, but also their specific order.
So, we know that stacks allow you to manipulate data within an array, while preserving the original ordered patterns of the data, which sounds like what we need to do. Let’s set about actually using this tool in an algorithmic solution to our this challenge.
So, a bit of pseudocode to get us started:
let isBalanced = (input) => {
iterate through input
if the current element is an opening bracket, record the correct closing bracket
if the current element is a closing bracket, check the record to make sure it is the correct closing bracket
if all the opening and closing brackets are matched and in the correct order, return true, otherwise return false
}
I know that using a stack, I can preserve a record of the order of my brackets, which will allow me to check if they are all correctly balanced (all opening and closing brackets have a match, and they are in the correct order to balance each other) or not.
let isBalanced = (input) => {
let brackets = "[]{}()<>"
let stack = []
for(let bracket of input) {
// record order on the stack
// check this record to make sure the brackets are all balanced
}
return true ? true : false
}
First, I’m making a few workhorse variables for myself.
I’m saving a string listing all my potential opening and closing brackets to a variable named brackets.
Note: I am pairing the opening and closing brackets together in this string.
**This is important. **
My particular solution would not work if the bracket string were to be written as “[{(<]})>”, for example.
The brackets can be in any order by type (e.g. “()[]{}<>” and “<>(){}[]” are both perfectly fine), but the opening and closing brackets must be written together.
The next variable I’m creating is just an empty array, which we can call stack, as this will be our stack.
I’ve sketched out an initial loop through our input string, populated only by pseudocode at this point.
Note: this loop is iterating through the elements of input, not the indexes. Personally, I enjoy using for…in / for…of loops, but you can always use a more traditional for loop (e.g. “for (let i = 0; i < input.length, i++)”) and still utilize this solution with minor modifications if you prefer.
Our function’s only remaining job will be to return either true or false upon the loop’s resolution.
Time to actually develop our stack and put it to use!
First, another workhorse variable within the loop itself:
let isBalanced = (input) => {
let brackets = "[]{}()<>"
let stack = []
for(let bracket of input) {
let bracketsIndex = brackets.indexOf(bracket)
// record order on the stack
// check this record to make sure the brackets are all balanced
}
return true ? true : false
}
bracketsIndex: I want to make sure the role of this variable is quite clear before moving forward!
We are iterating through input, the string of brackets that is passed into the function for testing.
bracketsIndex is NOT the index in input of the current bracket.*
bracketsIndex is looking up the index of the current _bracket _in our previously saved brackets variable. So if the first bracket in input were a “(“, its bracketsIndex would be 4. Its index in input is, of course, 0, but the index of “(“ in brackets is 4, so its bracketsIndex is 4.
Remember the bit about how the order of the brackets in the brackets string was important? We’re getting there.
So now, we have a variable, bracketsIndex, that can look up our current bracket in the brackets variable.
Now, we can finally start putting our stack to work.
Because of the way we organized our brackets reference string, we know that opening brackets have even indexes (0, 2, 4, & 6) and closing brackets have odd indexes (1, 3, 5, 7).
So, if our current bracketsIndex is even, we know that the current bracket is an opening bracket.
We can test for this using a modulo operator. Modulo operations, called in Javascript by the modulo operator, i.e. “%” (commonly called the percent sign), divide a first number by a second number, then return the remainder. So, one way to test for even or odd numbers is to run number % 2 === 0. Two will divide evenly into an even number, yielding a remainder of zero (returning true) while it will not into an odd number (returning false).
We can then push the location in brackets of the needed closing bracket onto the stack, by finding the bracket with index bracketsIndex + 1. Again, because of the way that we wrote our brackets string, an opening bracket will always be immediately followed by its matching closing bracket. Thanks to this, we can increment the bracketsIndex of any opening bracket to find the address of its closing match.
let isBalanced = (input) => {
let brackets = "[]{}()<>"
let stack = []
for(let bracket of input) {
let bracketsIndex = brackets.indexOf(bracket)
// if bracket is an opening bracket
if(bracketsIndex % 2 === 0) {
// push the closing bracket onto the stack
stack.push(bracketsIndex + 1)
} else {
//do something
}
}
return true ? true : false
}
Now, as we iterate through our input, our stack will keep a record of the closing brackets needed for the input string to be balanced.
Note: The bracketsIndex, an integer, is what is being pushed onto the stack, not the closing bracket itself.
Example: If our loop had iterated through the elements “(, <, [“, the stack would hold the indexes in brackets of “), >, ]” and thus would be [5, 7, 1].
Our loop will continue this task as long as we keep hitting opening brackets.
That’s cool. What happens when we hit a closing bracket though?
If the current bracket of input is a closing bracket, and therefore has an odd index, then (due to our conditional that runs based on the even/odd test of its bracketsIndex), a new task will run.
Array.pop() removes the most recent addition from our stack, changing the length of the array, and returns that removed element, allowing us to reference that element if needed.
So, If the current bracket is closing, we’ll pop the last element off the stack and compare the two. If our brackets are balanced, they should match.
This is the whole purpose of using the stack — as we iterate through our input string, the needed closing bracket is pushed onto the stack for each opening bracket, then popped off when the matching closing bracket is reached. If something in the stack breaks this pattern, then we know that our input string is not balanced.
let isBalanced = (input) => {
let brackets = "[]{}()<>"
let stack = []
for(let bracket of input) {
let bracketsIndex = brackets.indexOf(bracket)
if(bracketsIndex % 2 === 0) {
stack.push(bracketsIndex + 1)
} else {
if(stack.pop() !== bracketsIndex) {
return false;
}
}
}
// return true or false
}
Example: If our loop had iterated through the elements “(, <, [“, the stack would hold the indexes in brackets of “), >, ]” and thus would be [5, 7, 1].
If the following iteration hit the element “]”, then our expression would check stack.pop() (i.e. 1) against the bracketIndex of the current bracket (the current bracket being ] would have a bracketIndex of 1) and, as they are indeed equal, would return true, allowing it to move on to the next element in input. The stack going forward would be [5, 7], as the execution of stack.pop() permanently removed 1 from the stack array.
We need to check for one more thing though — when this loop resolves, the stack should be empty. If it’s not, that means there’s an extra unbalanced bracket or more left over.
let isBalanced = (input) => {
let brackets = "[]{}()<>"
let stack = []
for(let bracket of input) {
let bracketsIndex = brackets.indexOf(bracket)
if(bracketsIndex % 2 === 0) {
stack.push(bracketsIndex + 1)
} else {
if(stack.pop() !== bracketsIndex) {
return false;
}
}
}
return stack.length === 0
}
So, I check that stack has a length of zero in the final boolean return. The expression stack.length === 0 will return the boolean we need here.
If the whole loop runs without returning false and the stack is empty when it resolves, we know our input string is balanced and the function should return true. Otherwise, our function should return false.
Let’s run this function into the console and see what we get!
let isBalanced = (input) => {
let brackets = "[]{}()<>"
let stack = []
for(let bracket of input) {
let bracketsIndex = brackets.indexOf(bracket)
if(bracketsIndex % 2 === 0) {
stack.push(bracketsIndex + 1)
} else {
if(stack.pop() !== bracketsIndex) {
return false;
}
}
}
return stack.length === 0
}
isBalanced('()')
> true
isBalanced('()[]{}<>')
> true
isBalanced('([{<>}])')
> true
isBalanced('([])[{}]{(())}')
> true
isBalanced('(')
> false
isBalanced('()]')
> false
isBalanced('([])[{}]{(([))}')
> false
isBalanced('({)')
> false
isBalanced('([)]')
> false
isBalanced('([])[{}]{([)]}')
> false
Great! 🌟 I tested the isBalanced() function against a variety of balanced and unbalanced strings² and it returned the correct boolean for each one! Unlike my first idea, this function can successfully check for not only the correct number and types of brackets, but also check their specific order to make sure they match up correctly.
I still want to add one more element of functionality to our function. At the moment, if input contains anything other than pure brackets, our function will break. That’s not going to help us much if we actually wanted to create our own syntax bracket highlighter or other practical application of our function. So, we can add one more conditional into our loop.
let isBalanced = (input) => {
let brackets = "[]{}()<>"
let stack = []
for(let bracket of input) {
let bracketsIndex = brackets.indexOf(bracket)
if (bracketsIndex === -1){
continue
}
if(bracketsIndex % 2 === 0) {
stack.push(bracketsIndex + 1)
} else {
if(stack.pop() !== bracketsIndex) {
return false;
}
}
}
return stack.length === 0
}
If the current element is not in brackets (which will yield an index of -1), we simply direct our loop to move on to the next character in our input string. This one change makes our function much more adaptable!
This algorithm challenge made me really appreciate using a stack, even though that particular data structure had been quite neglected in my previous experience. There are other ways to solve this, but a lot of them involve writing out a lot of repetitive code to test for each individual bracket type, which gave me lots of opportunities to make typos and get bored.
If you’re having a tough time visualizing the operation of the stack, I recommend adding some debuggers or console.log()s to this code, and watching the loop play out in your console.
Not sure where to start? You might try something like this:
let isBalanced = (input) => {
let brackets = "[]{}()<>"
let stack = []
for(let bracket of input) {
let bracketsIndex = brackets.indexOf(bracket)
console.log(`The current element is ${bracket}, which has an index in input of ${input.indexOf(bracket)}, and matches the bracket with index ${bracketsIndex} in brackets`)
if(bracketsIndex % 2 === 0) {
stack.push(bracketsIndex + 1)
console.log(`this is an opening bracket. The address of its matching closing bracket in brackets is ${bracketsIndex + 1}. Adding that index to the stack makes the stack ${stack}`)
} else {
console.log(`this is a closing bracket, so ${stack.pop()} is being popped off the stack`)
if(stack.pop() !== bracketsIndex) {
return false;
}
}
}
return stack.length === 0
}
Hopefully this algorithm challenge gives you the same opportunity it did me — the chance to understand how stacks work, and why they’re such useful tools for problems where a particular order needs to be preserved and checked against.
This article also addresses the queue data structure, which isn’t strictly relevant to this particular challenge but still nice to know about. While the article is not exclusively stack-focused, it’s one of my favorite stack summaries. I also like this one.
These strings are what I use in the test suite included in the GitHub Repo for this post, and the test file includes comments that can give you more info about what each different string is testing the function for.
Top comments (1)
Awesome