Solving Balanced Parentheses Problem Using Regular Expressions

Balanced Parentheses Problem

Since this is such a famous programming problem, the chances are that most of us would have solved this during the CS101 course or somewhere else. Nevertheless, I still insist that we do skim through the problem statement once, before moving to the next sections.

Let’s say that we’ve have got an input string that can only contain brackets [], parentheses (), and braces {}. Then, our input string is said to be balanced when it meets two criteria:

LOFC (Last Opened First Closed) implies that the one that opens last is the first one to close
LOFC takes into consideration that the open and close parentheses belong to the same pair, namely (), [], and {}

Further, if the input string is empty, then we’d say that it’s balanced.

Sample Input Data

Next, let’s take a look at a few sample input strings and find out if they’re balanced or not:

[()[]{}]{} is balanced
[][]() is balanced
() is balanced
))(( is not balanced
{) is not balanced

Biased Minds Have a Small Room for Headspace

Yes, I know some of us would have already created a mental picture of a stack to start solving this problem.

Though, that’s a good thing that you’ve solved this before, or maybe you read this problem for the first time and came up with a stack-based solution in no time. However, I urge you to free up your headspace for now, so that your thoughts are not biased.

Solution using Headspace

The whole point of solving it with regular expressions is that it’s more intuitive to code as we’ll see. Further, by no means do I mean that it’s a better approach in terms of the time complexity of the algorithm!

First, let's revisit the first one in the list of sample inputs from the previous section:

[()[]{}]{}

Now, let’s try to observe our minds while we’re trying to solve it. We can be a genius to solve it fast, but we need to observe this thinking process slowly. Further, we should do everything in mind. That means we must refrain from using a pen and paper.

Although we shouldn’t need more than 3 minutes, nonetheless, we can take as much time as we need to finish this activity with satisfaction.

There’s no point in going further unless we spend some time here. Nobody is judging us if we’re slow — The slower, the better, but we must focus entirely on this activity to complete it in a single stretch.

And, whenever we’re ready, let’s try to answer some questions:

Did we solve it in a single stretch?
Were we able to focus on patterns such as (), {}, and [] in the string?
What did we do when we spotted the balanced patterns, namely (), {}, []?

Let’s pat our mind for giving us a spacious headspace to visualize the complete process of solving it.

Now, everybody could have visualized this differently. For now, let me put forward how I visualized it.

First, I was quickly able to spot the three patterns of (), [], {} inside the wider square bracket, along with the {} pattern on the extreme right side. However, I must mention that I didn’t actually see that there’s a wider bracket that contains the three balanced parentheses.

Then, once I had spotted a few balanced patterns, I tried to focus a bit more by ignoring the already discovered ones from my sight. As a result, I was able to see that there’s one pattern of [] that contained the earlier observed patterns.

Next, I know there were no more new patterns that I could spot, and if I ignore all these patterns, then I had nothing but an empty string.

Of course, I had to focus more as I advanced towards the next step.

As they say, a picture is worth a thousand words, so I tried to sketch this activity later, to portray a better view of the entire process:

Implementation Using sed

Ah! I know. I know. Execution is what excites a lot of us —

We, the developers like action. Seeing code in action thrills us. Isn’t it?

But, sed?
Really, sed? Not Java, Python, Kotlin, Go, Haskell. Not even C?

Yes, sed, it is. 🙂

sed is an excellent tool for pattern matching. In fact, it’s a Turing complete programming language. So, why not!

Anyway, we’re following the headspace approach, and sed will let us formalize our thoughts around patterns in the form of code quite easily:

:combine
s/\(\)//g
s/\{\}//g
s/\[\]//g
t combine

s/^$/balanced/p
t
s/.*/Unbalanced/p

That’s all our code literally. Moreover, it works for an input stream, not just for a single string. Isn’t it wonderful?

As much as I’m in love with this simple solution, I also agree, if you’re not familiar with sed, then these lines could be a bit overwhelming for you. So, let me summarise it for you.

As such, our script uses the concepts of a simple loop and substitution using regex. For substitution, it uses the s, substitution function of sed with the global flag, g to apply the effect at all occurrences:

s/regex/replacement/g

Further, we continue doing the pattern matching and substitutions until we can’t find any of the three patterns. We stay in the loop using the t, test function:

t label

For this, we had earlier defined our label called combine using the : (label) function:

: label

We must note that the t, test function branches out to the label if the last substitution was successful, else the flow continues line-by-line.

Once we’ve come out of the loop, we’ll either have an empty string for balanced cases or a non-empty string for unbalanced ones.

As a result, we again use the s, substitution function with the print, p flag to display a message saying “balanced” or “unbalanced.”

But, wait, at the second last line, we didn’t use any label to do conditional branching using the t, test function:

Without the label, the test function restarts the execution cycle for the next line in the input stream. That also happens when all the commands in the script have finished executing for the current cycle.

Now, let’s take a leap of faith and test this with a few sample input strings.

Does Our code work?

First, let’s take a look at our input strings:

% nl input_parantheses.txt
     1 [()[]{}]{}
     2 [][]()
     3 ()
     4 ))((
     5 {)
     6 (()())
     7 ))
     8 ()
     9 )()(

Finally, let’s execute our script and see the fruit of our labor:

% sed -E -n -f balanced_parantheses.sed input_parantheses.txt | nl
     1 balanced
     2 balanced
     3 balanced
     4 Unbalanced
     5 Unbalanced
     6 balanced
     7 Unbalanced
     8 balanced
     9 Unbalanced

Sigh! We can see that the output for each line of input meets the expected result.

Conclusion

In this tutorial, we relied on our intuitions and headspace to arrive at a good enough solution for the problem of balanced parentheses. Additionally, we tasted a few basic regular expressions while implementing the solution in sed.

References

[1] Leetcode Valid Parentheses Problem
[2] Regular Expressions
[3] sed, Stream Editor
[4] nl, Line Numbering Utility