Introduction

Bracketolgy is an application I developed to demonstrate how to balance brackets in a string with JavaScript. What this does is make sure each opening bracket has a matching closing bracket, and that the brackets are nested correctly.

Lets take the following string for example:

These brackets are balanced, since each opening bracket has a closing bracket, and they are nested correctly. Nesting refers to the convention where you have an opening and closing bracket within an opening and closing bracket. Think of the inner brackets as a child and the outer brackets as the parent. Here is an example of the above balanced brackets and how they might look formatted as code.

[ Parent
   { child
       ( child )
   }
]

You can see how the nesting works. The next example shows brackets that are not balanced.

There is a mistake in the nesting or order of the brackets, even though each opening bracket has a closing bracket. This will throw an error since the rules of syntax in coding requires the nesting to be correct.

Here is another example:

The above example shows a missing closing bracket " ] ".

So given the original example, how would you write an algorithm to check through the brackets in a string to see if they are balanced? Take a moment to think about how it might be done.

Theory

So this is how the algorithm works in plain english. There are other ways to go about it. This explanation covers one of the more common approaches.

@ Here is the string to test:

We will need an empty bucket to start. We are going to loop through each of the brackets in the string.
If the first bracket is an opening bracket, we are going to take a copy of it and put it in the bucket.
=> bucket: " [ "

The next bracket is also an opener, so add it to the bucket.
=> bucket: " [ { "

And again the next is an opener.
=> bucket: " [ { ( "

The next bracket is a closing bracket. When that happens we will check if this closing bracket will match the opening bracket we just put in the bucket.

Is the " ) " bracket the correct closing bracket for the " ( " bracket which came right before it?
Yes it is. In this case we are going to remove that bracket from the bucket. So the " ( " bracket, which was the most recently added to the bucket, is removed from the bucket.
=> bucket: " [ { "

The keyword "stack" is a data structure that has a Last In First Out (LIFO) structure. The most recent item put into the stack is the first one to take out. If you have a stack of "1,2,3,4", the most recent item put into the stack is the "4". When you take that out, the next most recent is the "3", so that gets taken out next. And so on. This is what we are doing with the bucket.

The next bracket is also a closing bracket. Does it match the opening bracket that is now the most recent in the bucket?
Is the " } " bracket a closing bracket for the " { " bracket?
Yes, so the next most recent opening bracket " { " which was added to the bucket is removed.
=> bucket: " [ "

Now you may see a pattern. When we do the same test for the next bracket in the string " ] ". We can see that it is the correct closing bracket for the most recent bracket in the bucket, so it gets removed.
=> bucket: ""

The empty bucket is the signal that tells you that the brackets in the string are balanced.

@ Let's try an unbalanced example.

First bracket is opener.
=> bucket: " [ "

Second bracket is opener.
=> bucket: " [ { "

Third bracket is closer.
Is the third bracket " ) " the correct opening bracket for the most recent bracket in the bucket?
No. So we aren't going to remove any brackets from the bucket. Now we know the brackets are not balanced. There is no need to keep checking.
=> bucket: " [ { "

@ Let's try one last example.

When looping through the string for opening brackets we end up with this bucket.
=> bucket: " [ { ( "

The next bracket " ) ", a closing bracket, matches the most recent in the bucket so that is removed from the bucket.
=> bucket: " [ { "

We are at the end of the string, there are no more brackets to check. The bucket is not empty, which is our signal to tell us the brackets are not balanced.

Conclusion

This is a very rudimentary explanation of the balance bracket algorithm. There is more to it than that however. There are other things to check for, and there are many ways to code this. Check out my version of the app to see one way of treating this challenge.

Good Luck!