Check whether Parenthesis string is balanced or not

Check whether Parenthesis string is balanced or not” is one of an ideal application of stack data structure. Here, we have given a parenthesis string and our aim is to check whether the given string is balanced parenthesis string or not. 

Balanced parenthesis strings are those strings who have closing parenthesis like }, ], ) for each opening parenthesis like {, [, ( and in respective order.

Stack data structure can be used to check whether given parenthesis string is balanced string or not. 

The types of parenthesis are: (, ),  {, },  [, ] .

Example:

  1. {{}}, [[]], {{[]}}, (({})) are all balanced parenthesis strings.
  2. ]][[, }}[[, {]{], (((}}()() are all unbalanced parenthesis strings.

The steps required to check whether the parenthesis string is balances or not is as follows:

  1. Create an empty character stack.
  2. While traversing, push every open parenthesis character including ( , { , [  into the stack.
  3. If at any time, Closing parenthesis character including ), }, ] appears, then check whether the top of the stack contains the corresponding open parenthesis character or not.
  4. If stack contains, open parenthesis character, then pop it out and continue the string traversal.
  5. Else, return false as given parenthesis string is not balanced.
  6. After complete traversal, if stack is empty, then return true, which means given parenthesis string is balanced.

C++ Program to check whether parenthesis string is balanced or not:


#include<bits/stdc++.h>
using namespace std;
bool checkBalanced(string str)
{
    stack<char>st;
    for(int i = 0 ; i < str.length() ; i++)
    {
        if(str[i]=='{' || str[i]=='[' || str[i]=='(')
        st.push(str[i]);
        else
        {
        // If stack is empty, return false.
            if(st.size() == 0)
            return false;
            else if(str[i]=='}' && st.top()!='{')
            return false;
            else if(str[i]==']' && st.top()!='[')
            return false;
            else if(str[i]==')' && st.top()!='(')
            return false;
        // Else, pop the stack
            else
            st.pop();
        }
    }
    // If stack is empty, return true.
    if(st.empty())
    return true;
    return false;
}
int main()
{
    string str;
    cout<<"Enter Parenthesis string: ";
    cin>>str;
    bool res = checkBalanced(str);
    if(res)
    cout<<"\nThe given string is Balanced";
    else
    cout<<"\nThe given string is not Balanced";
}


OUTPUT:
Enter Parenthesis string: {{[]}}
The given string is balanced.

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *