Top String Interview Question -Parentheses Checker

Problem Statement:

Given an expression string x. Examine whether the pairs and the orders of ‘{’ , ‘}’ , ‘(’ , ‘)’ , ‘[’ , ‘]’ are correct in order.
For example, the function should return ‘true’ for exp = “[()]{}{[()()]()}” and ‘false’ for exp = “[(])”.

Example 1:

Input:
{([])}
Output: 
true
Explanation: 
{ ( [ ] ) }. Same colored brackets can form 
balaced pairs, with 0 number of 
unbalanced bracket.

Example 2:

Input: 
()
Output: 
true
Explanation: 
(). Same bracket can form balanced pairs, 
and here only 1 type of bracket is 
present and in balanced way.

Example 3:

Input: 
([]
Output: 
false
Explanation: 
([]. Here square bracket is balanced but 
the small bracket is not balanced and 
Hence , the output will be unbalanced.

The task is to write a function which takes a string as a parameter and returns a boolean value true if brackets are balanced else returns false.

Expected Time Complexity: O(|x|)
Expected Auixilliary Space: O(|x|)

Here, |x| is the length of the given string x.

Asked in the following companies:

Adobe , Amazon, Flipkart, Oracle, OYO Rooms, Snapdeal, Walmart, Yatra.com, Microsoft, Google

Concept:

The primary concept behind this is to check whether the brackets are balanced. Thus, for any bracket that is opening, there must be its closing counterpart and this closing should be in the correct order.

If we consider the following example:

Given string: { ( [ ] ) }

Here, the square brackets: [ ] are the innermost ones, hence it should be closed first. After that, the round brackets: ( ) must be closed, and finally, the outermost curly brackets: { } must be closed.

We can say that the bracket which is opened at last must be closed first. If this order is followed, then we say that the brackets are balanced.

Approach — Using Stack :

There can be three types of brackets: {, [, ( and their respective counterparts: ), ], }. We will use a stack as it is based on Last In First Out principle, which is very similar to our problem.

Basic Operations of Stack:

push: Adding an element at the top of the stack

pop: Deleting the topmost element

peek: Check the value of the topmost element

Step-by-step Solution:

1. If the character is an opening bracket, push it to the stack.
2. If it is a closing bracket, there can be three scenarios:

• If the size of the stack is zero. This indicates that a closing parenthesis is at the beginning of the expression. Such an expression is invalid. Hence, return false.
• If the topmost element is not an opening parenthesis, return false.
• When the current parenthesis is the closing counterpart of the topmost element of the stack, pop the ‘top’ element from the stack. This means we found one balanced pair of brackets.

3. At the end, if stack size is now zero, this means we found all balanced pairs of parantheses in the expression. Return true.

4. If stack size is greater than zero, there are additional opening brackets in the expression. Return false.

Code:

Complexity Analysis:

Time Complexity: O(|x|)
Space Complexity: O(|x|)

|x| is the length of the expression string ‘x’.

If you liked this article, please click the “clap” button 👏 a few times.

Gives me enough motivation to put out more content like this. Please share it with a friend who you think this article might help.

Follow me Varsha Das to receive my weekly articles.

Connect with me — Varsha Das | LinkedIn

Follow my Youtube channel where we discuss Data Structures & Algorithms.

Thanks for reading.

Happy learning! 😁