How to solve balanced parentheses problem with regex in ruby

This is one of the classic interview questions that is classically solved with a stack algorithm. Despite regular expressions are not the most efficient way in terms of computation, I’m going to show a solution using subexpression call syntax only to show a different approach.

The problem

Your objective is to create an algorithm to validate whether the parentheses in a given string are balanced on not. For example:

() # balanced
()() # balanced
(())() # balanced
)( # unbalanced

Regex quick reference

Just in case you don’t remember the syntax. These are the instructions considering that there are reserved characters like: “(“, “)”, “.”, that you are going to have to use to escape it using “\” at the beginning. For example, if you want to use a parenthesis you should use: \(

On the other hand, we will use the method match? for simplicity, because it returns true/false depending on the input that we are using with our regular expression.

Basic idea

So, when we try to solve something using regular expressions our knowledge is mainly limited to the classic syntax that we are able to test online. Let's begin with the easiest idea. We want to validate if we have something like: “()”, “()()”, etc.

balanced = /^(\(\))*$/

So far, so good. We can validate cases like the following:

"()".match?(balanced) # true
"()()".match?(balanced) # true

Why does that work?

Let me explain the syntax above.

 balanced = /
  ^            # the regular expression is going to start with the instruction that is after that
    (          # start of the group 1
      \(\)     # means that we are expecting ()
    )*         # end of the group 1, 0 or more times
  $            # the regular expression is going to finish with the instruction that is before that
 /x            # this is used to be able to define a regex with spaces and line breaks

The problem is that we are not able to validate cases like: “(())”, “(())()”, etc.

Why use a subexpression call

Because we can’t validate cases that have parentheses inside parentheses we need to use an instruction to define those scenarios. That said, a subexpression call is necessary because you need to give an instruction like “I need to support an unlimited quantity of parentheses inside parentheses including parentheses outside them”.

Subexpression call syntax

The syntax is the following: \g<0>, \g<1> … \g<n>. The number represents the group, so, if the number is 0 that means that we are considering the entire expression. Just in case it wasn’t clear before, a group is what is inside a parenthesis in the regular expression. For example: /(group1)(group2)/. In that example, we have 2 groups, so, this syntax: /(group1)\g<1>?/ means that we are expecting expressions like: “group1”, “group1group1”, “group1group1group1”, etc.

Using subexpression call in our problem

As you can see, a subexpression call means that we are expecting to match n times the group that we specified, considering that if the group is a regular expression we could expect variations that matches that too. That said, this would be the improved regular expression to solve our balanced parentheses problem:

balanced = /
  ^             # the regular expression is going to start with the instruction that is after that
    (           # start of group 1
      \(        # means we are expecting (
        \g<1>?  # means we are expecting group one n or zero times
      \)        # means we are expecting )
    )*          # end of group 1, 0 or more times (it's part of group 1)
  $             # the regular expression is going to finish with the instruction that is before that
/x      # this is used to be able to define a regex with spaces and line breaks

Conclusion

With the syntax above we can validate cases like “()”, and “()(())” because we are using the subexpression call instruction. On the other hand, you can use a similar syntax to solve the balanced brackets problem that’s basically the same but with (), [], and {}.

📥 Thanks For Reading! 📥

If you have any questions or suggestions please let me know