Check Balanced Parenthesis using Stack 📚

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!