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.

Related Posts:

  1. Next Greater Element
  2. Find Minimum number of bracket reversals required to make an expression balanced.
  3. Implement Queue Using Two Stacks.
  4. Merge Overlapping Intervals using Stacks
  5. Implement Stack Using Linked List
  6. Largest Rectangular Area in Histogram
  7. Length of Longest Valid Substring
  8. Reverse a String using Stack
  9. Implement two stacks in a single array
  10. Print Bracket Number
  11. Next Greater Frequency Element
  12. Sort a Stack using Temporary Stack
  13. Infix to Postfix Conversion
  14. Infix to Prefix Conversion
  15. Prefix to Infix Conversion
  16. Prefix to Postfix Conversion
  17. Postfix to Infix Conversion
  18. Postfix to Prefix Conversion
  19. Program to check Palindromic Anagram.
  20. Program to print all the Palindromic Substring of the String.

You may also like...

Leave a Reply

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