Understanding Balanced Parentheses

Understanding Balanced Parentheses
Understanding Balanced Parentheses

Introduction

A string is one of the most popular data structures, probably equal to the array, and you will find at least one String question in any programming job interview.

Today we will solve one of the most famous questions on a string- “Balanced Parentheses.” frequently asked in Amazon.

Keep an eye out for the approach, as there will be plenty of hints to help you develop a solution ahead of time. Do try to solve it by yourself before moving on to the approach.

Problem Statement of Balanced Parentheses

You’re given the string ‘STR’ consisting solely of “{“, “}”, “(“, “)”, “[“ and “]”. Determine whether the parentheses are balanced.

Sample Input :
2
[()]{}{[()()]()}
[(])
Sample Output :
Balanced
Not Balanced

Note: An input string is said to be balanced if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.

We advise you to think about how you can solve this problem more thoroughly, champ.

Okay, let me give you some hints before we move on.

Hint 1:

A valid parenthesis expression has the interesting property that a sub-expression of a valid expression must also be a valid expression. (Not all sub-expression).

For example: Consider a string  { [ [ ] { } ] } ( ) ( )

blog banner 1
illustrative_diagram

Hint 2:

What if we simply remove the matching pair of parentheses whenever we come across them in the expression? It would further shorten the expression. 

For example: 

{ { ( { } ) } } //remove matching pair 1
      |_|

{ { (      ) } } //remove matching pair 2
    |______|

{ {          } } //remove matching pair 3
  |__________|

{                } 
|________________|

Above all are VALID EXPRESSIONS!

Hint 3:

When a problem is represented in terms of one or more subproblems, the most used concept that comes to mind is Recursion.

We can’t really process this from the inside out because we don’t know what the overall structure looks like. The stack data structure can come in handy here in representing this recursive structure of the problem.

Without further ado, let’s move on to the actual approach.

Make use of the stack. Traverse the string and push the current character in the stack if it is an opening brace; else pop from the stack. If it is the corresponding starting brace for the current closing brace, then move to the next character of the string; otherwise, return false.

If after complete traversal, if the stack is empty, then the string has balanced parentheses. Else it is not balanced.

Pseudo Code of Balanced Parentheses

  • Declare a character stack.
  • Now traverse the expression string

       1-  If the current character is an opening bracket ( ‘(‘ or ‘{‘ or ‘[‘ ) then push it to 

     stack.

       2-  If the current character is a closing bracket ( ‘)’ or ‘}’ or ‘]’ ) then pop from 

     stack and if the popped character is the matching opening bracket, then fine 

     else parenthesis are not balanced.

  • After complete traversal, if there is some opening bracket left in the stack, then “not balanced”.
  • Otherwise, the string is balanced.

Below C++ code is given for your better understanding:

// CPP program to check for balanced parentheses.
#include <bits/stdc++.h>
using namespace std;
bool isValidParentheses(string expression)
{  
    // Make an inbuilt stack.
    stack<char> s;
    char x;
 
    // Traversing the Expression.
    for (int i = 0; i < expression.length(); i++) 
    {
        if (expression[i] == '(' || expression[i] == '[' || expression[i] == '{') 
        {
            // Push the element in the stack.
            s.push(expression[i]);
            continue;
        }
 
        /* 
            If current current character is not opening 
            bracket, then it must be closing. So stack 
            cannot be empty at this point. 
        */

        if (s.empty())
        {
            return false;
        }
 
        // Store the top element.
        x = s.top();
        s.pop();
       
        // Check for opening braces in the stack of corresponding closing braces.
        switch (expression[i]) {
        case ')':
           
            if (x == '{' || x == '[')
            {
                return false;
            }
            break;
 
        case '}':
 
            if (x == '(' || x == '[')
            {
                return false;
            }
            break;
 
        case ']':
           
            if (x == '(' || x == '{')
            {
                return false;
            }
            break;
        }
    }
 
    // Check Empty Stack.
    return (s.empty());
}
// Driver code
int main()
{
    string expr = "{{()]}";

    // Function call
    if (isValidParentheses(expr))
        cout << "Balanced";
    else
        cout << "Not Balanced";
    return 0;
}

Output for the above code with input string “{{()]}” is as follows:

Not Balanced

Complexity Analysis of Balanced Parentheses

Time Complexity

O(N), Where N is the length of the string. 

Reason: As the traversal of the string or expression is done only once.

Space Complexity

O(N), Where N is the length of the string.

Reason: As the maximum stack size reaches the length of the string.

Let’s go through the visualisation below for a quick recap:

If you’re getting ready for an interview, “Top Coding Questions for Technical Interviews” is a great place to start. Let’s move on to some frequently asked questions.

Frequently Asked Questions

What is a stack?

A stack is an abstract data type that serves as a collection of elements and has two primary operations: Push, which adds an element to the collection, and Pop, which removes the most recently added element that has not yet been removed.

What data structure can be used to check if the syntax has balanced parentheses?

Stack comes in handy to check if the syntax has balanced parentheses.

What is balanced parentheses?

A string of parentheses is intuitively balanced if each left parenthesis has a matching right parenthesis and the matched pairs are well nested.

What is stack pop ()?

Stack pop() removes the most recently added element that has not yet been removed.

Where can I practice more stack problems?

You can use CodeStudio to practise a wide range of DSA questions typically asked in interviews at big MNCs.

Key Takeaways

This article discusses the problem Balanced Parentheses, as well as some essential hints to assist you in coming up with a solution.

The stack data structure comes in handy here to determine whether or not the syntax has balanced parentheses.

It is rigorous practicing which helps us to hone our skills. You can find a wide variety of practice problems, specifically dynamic programming to practically utilise the knowledge you gained here.

Apart from this, you can use CodeStudio to practice a wide range of DSA questions typically asked in interviews at big MNCs. This will assist you in mastering efficient coding techniques and provide you with interview experiences from scholars in large product-based organisations.

By: Aanchal Tiwari