Solving Balanced Brackets in Javascript with Stacks
Tags: javascript, algorithms, stack
Published: 2020-02-29 21:31:09

### [GitHub Repo with completed solution code and test suite](https://github.com/noamsauerutley/balanced-brackets)

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”

![](https://cdn-images-1.medium.com/max/2000/1*YC5UpZvSmnWCIBGuicOR7Q.jpeg)

_**Note**: I use the word “[brackets](https://en.wikipedia.org/wiki/Bracket)” 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.

![](https://cdn-images-1.medium.com/max/2032/1*WsOuFrzz-CNoHl5dKiGdSg.png)

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](https://levelup.gitconnected.com/solving-the-ransom-note-algorithm-in-javascript-72ebe8acb268) [before](https://levelup.gitconnected.com/find-all-permutations-of-a-string-in-javascript-af41bfe072d2) about the benefits of using [hash tables](https://en.wikipedia.org/wiki/Hash_table) and [recursive trees](https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)) to break down complicated tasks. I know that [data structures](https://www.geeksforgeeks.org/data-structures/) can make amazing tools for deconstructing problems that require [algorithmic solutions](https://en.wikipedia.org/wiki/Algorithm).

But before trying to tackle this particular problem, I hadn’t had many encounters with [stacks](https://medium.com/@hitherejoe/data-structures-stacks-queues-a3b3591c8cb0)¹. 

In Javascript, I like to think of them as an [array](https://www.geeksforgeeks.org/arrays-in-javascript/) 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](https://www.geeksforgeeks.org/javascript-array-prototype-push-function/)** and **[pop](https://www.geeksforgeeks.org/javascript-array-prototype-pop/)** methods. These methods would push a new element onto the top of the stack, or pop it back off the top, respectively.

![](https://cdn-images-1.medium.com/max/2000/1*gDhgbBYPS9losgQh02BmsQ.png)

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.

![](https://cdn-images-1.medium.com/max/2000/1*A-OSrVHrH5HtIaP2qKXAXg.png)

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](https://alligator.io/js/for-of-for-in-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](https://en.wikipedia.org/wiki/Modulo_operation). 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](https://www.geeksforgeeks.org/debugging-in-javascript/) or [console.log()](https://www.geeksforgeeks.org/javascript-console-log-with-examples/)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.

![](https://cdn-images-1.medium.com/max/2000/1*tOoeIMz9DwPZ52Ewog2W6w.gif)

1. 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](https://medium.com/@_jmoller/javascript-data-structures-stacks-and-queues-ea877d72a5f9).

1. These strings are what I use in the test suite included in the [GitHub Repo](https://github.com/noamsauerutley/balanced-brackets) for this post, and the [test file](https://github.com/noamsauerutley/balanced-brackets/blob/master/test/balancedBrackets.spec.js) includes comments that can give you more info about what each different string is testing the function for.