Solving the Balancing Brackets Problem in O(n) Time

How compilers know when you omit brackets and semi-colons

Oluwadamilare Olusakin
Aug 29 · 4 min read
Photo by 青 晨 on Unsplash

Guess what? Compilers aren’t, in fact, psychic beings who can see through your every line of code. I’m about to you give you some insight into how exactly they’re able to call you out every time you mismatch a pair of brackets.

Today we’ll be solving a problem on balancing brackets. I’ll show you the problem statement and a brute force approach and give you a hint before we dive into the solution: to pause a bit and try to think about the problem. I’ve always encouraged people to try stuff on their own as your curiosity will play a vital role in the kind of developer you become.

On a side note, if you haven’t seen my tutorial on stacks and haven’t had any experience with a stack before, or you’d like a refresher, at least, check out the tutorial on “Solving the Min-Stack Problem in O(1) Time.”

So, on with it? Yes!


Balanced Brackets

There are three kinds of brackets: [] {} (). Given a string of characters, check if all the brackets in the string are balanced. A string is balanced if all the start and end brackets are in the correct order so they match each other.

Here are some balanced strings:

  • {}
  • (hello)[world]
  • [({}{}{})([])]

Here are some unbalanced ones:

  • (hello — There’s no ending ).
  • ([)] — The [ is improperly enclosed in the ().
  • )( — There’s an ending ) without a ( before it.

Return true if a line is balanced and false otherwise.

The following are three test cases:

  • puts balanced_brackets?(‘(hello)[world]’)

# => true

  • puts balanced_brackets?(‘([)]’)

# => false

puts balanced_brackets?(‘[({}{}{})([])]’)

# => true

Hint: May the Stack be with you! I encourage you to pause at this point and brainstorm a little bit.

On to the main course!


Solution

I am about to declare some classes and methods, but I will not be taking you through what each one does in this tutorial to avoid repeating myself. If you want some more understanding of the classes and methods, check out my tutorial (mentioned above) on the min-stack problem.

First, since a stack is node-based, we need to set up our node class:

Next, we initialize our stack:

Next, we bring in Major pushFront:

And then popFront it's counterpart:

Next, topFront:

And lastly, is_empty?:

Now, on to the main attraction: how do we make sure a set of brackets is balanced? To the Stackmobile!

I will break this down into three parts:

  • Initialize our stack
  • Loop over our string
  • Return true if we manage to make it to the end of the loop

Let’s take a look at what should happen inside our loop:

  • We want to push the first character in the string to the stack when our stack is empty so we have something to compare subsequent characters to. (Only push the character if it’s a bracket).
  • If a character is an open bracket, we want to push it into the stack.
  • If a character is a closed bracket, we want to check if we just pushed its opening half into the stack, and, if we did, then there is a match. We celebrate this match by removing the opening half from the stack.
  • If we arrive at a closed bracket, and we didn’t just put its opening half into the stack, then we have an unhappy couple. The loop should immediately stop and return false.
  • However, say we have something like this '[()'. Notice that we have an open square bracket without one to close it. What happens then? How do we handle this edge case? We simply check to see if our stack is empty when the loop ends.

Note: After reading some of the code, you may wonder why I didn’t declare an array with all the types of brackets in it and use methods like .include?. Well, the simple answer is methods like those actually have a time complexity of O(n). This means that when you nest them in a loop, your complexity goes from O(n) to O(n²), which is synonymous with poor performance.


Let’s Write Some Code

First, take care of the empty stack problem:

Notice the use of boolean operators in comparing the value of our current index to the value of the three types of opening brackets. This is because comparisons like these are constant time operations O(1) as opposed to something like .include? .

Next, we only want to push a character if it’s an opening bracket:

Now, we need to handle edge cases for the three different types of closing brackets. I have employed the switch statement below to do that:

Each time we encounter a closing bracket, we use topFront to peek at the last bracket we pushed on the stack. If it matches the closing bracket, we pop — remove what is on top of the stack and continue looping till we are at the end of the string.

Now, remember this '[()'? We still need to take care of this, just in case we encounter a worthy adversary who tries to trick our program. Simply add this line on before your return true statement:

return false if s.first.next_node

It checks if our stack is empty when we get to the end of the string. If it isn’t, then we didn’t close all our brackets as we should’ve.


Conclusion

There you have it. This is fundamentally how compilers got their psychic power! As we know, balancing brackets is one of the most important operations a compiler performs.

Be sure to leave some comments in the responses below. I’d love to know your thoughts.

You can find the code for this tutorial on GitHub.

Better Programming

Advice for programmers.

Oluwadamilare Olusakin

Written by

Fullstack Developer with a passion for design.

Better Programming

Advice for programmers.

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