Solved Problem - Balanced Parentheses Sequence

In this lesson, we'll discuss a popular stack problem.

Problem statement

Given a string sequence consisting of length NN only of opening or closing parentheses ( ) [ ] { }, determine if the sequence is a correct bracket sequence.

For example: If s1s1 and s2s2 are correct bracket sequences, so are the following:

  • (s1)s2(s1)s2
  • (s1s2)(s1 s2)
  • [({s1}s2)][(\{s1\}s2)]

But these are not:

  • )s1s2))s1s2)
  • [s1)s2[s1)s2








Brute force

Obviously, if it’s a balanced sequence, every opening bracket, ( [ {, is matched to exactly one closing bracket, ) ] }, of the same type.

We can parse to look for every closing bracket and try to find its corresponding opening bracket in the string parsed so far.

It would be the first opening bracket to its left that didn’t match up with any bracket yet. So, you keep track of matched brackets as well.

If we are able to match all the brackets, then it’s a balanced sequence, otherwise it’s not. See the illustration below for a better understanding:

Get hands-on with 1200+ tech skills courses.