Check for balanced parentheses

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

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

Stack data structure can be used to check whether given parentheses 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 for balanced parentheses are as follows:

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

C++ Program to Check for balanced parentheses is as follows:

/* Program to Check for balanced parentheses  */
#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. Find Most Frequent Character of the String.
14. Check Anagram Strings.
15. Check Whether Given String is Palindromic Anagram or Not.
16. Check Whether Given String is Panagram or Not.
17. Find First Non-Repeating Character of the String.
18. Find Most Frequent Element of the Array.
19. Find Pair in an Array with Given Sum.
20. Find First Repeating Element of an Array.