Road To Code

Road To Code

Check Balanced Parenthesis using Stack 📚

Tejal sakore's photo
Tejal sakore

Published on Sep 23, 2021

2 min read

Subscribe to our newsletter and never miss any upcoming articles

Listen to this article

In this article, We are going to solve the Balanced Parenthesis Algorithm.

First things first, let's know something about this algorithm.

What is Balanced Parenthesis Algorithm?

Here, We're given an N sized string expression with only opening and closing brackets of the kinds '(', ')', '{', '}', '[', and ']'. The task is to determine whether the provided expression has balanced parenthesis or not.

The parentheses are balanced if,

  • There is a matching closing bracket for each opening bracket.
  • All brackets are closed in the correct order.

For example :

  1. Input : "{()[]}"

    Output : Balanced

  2. Input : "{[(])}"

    Output : Not Balanced

How to Solve It?

The Stack data structure can be used to overcome this problem. Let's look at the algorithm:

  • Traverse the string.
  • If an opening bracket is in the string, push it onto the stack.
  • Check the top of the stack if there is a closing bracket.
  • Pop and move ahead in the string if the top of the stack has the opening bracket that matches the current closing bracket.
  • The parenthesis are not balanced if the top of the stack does not match the current closing bracket's opening bracket. If that's the case, exit the loop.
  • The parenthesis are not balanced if the stack is empty.
  • If the stack is not empty after traversing, the parentheses are not balanced. Otherwise, print balanced.

Source Code in C++

#include <bits/stdc++.h>
using namespace std;

bool checkBalancedParanthesis(string expr)
{
    stack<char> s;
    int len = expr.length();

    for (int i = 0; i < len; i++)
    {
        char currentSymbol = expr[i];

        if (currentSymbol == '(' || currentSymbol == '[' || currentSymbol == '{')
        {
            s.push(currentSymbol);
            continue;
        }

        if (s.empty())
        {
            return false;
        }

        char topElement;

        switch (currentSymbol)
        {
        case ')':
            topElement = s.top();
            s.pop();
            if (topElement == '[' || topElement == '{')
                return false;
            break;

        case '}':
            topElement = s.top();
            s.pop();
            if (topElement == '[' || topElement == '(')
                return false;
            break;

        case ']':
            topElement = s.top();
            s.pop();
            if (topElement == '{' || topElement == '(')
                return false;
            break;
        }
    }

    if (s.empty())
    {
        return true;
    }
    else
    {
        return false;
    }
}

int main()
{

    string expr = "{()[]}";

    if (checkBalancedParanthesis(expr))
    {
        cout << "Balanced";
    }
    else
    {
        cout << "Not Balanced";
    }

    return 0;
}

Output:

Balanced

Hope you've got satisfied answer of Balanced Parenthesis problem!

For solutions of more such problems, Keep learning with Road to Code...

Thank You!

 
Share this