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:
- {{}}, [[]], {{[]}}, (({})) are all balanced parenthesis strings.
- ]][[, }}[[, {]{], (((}}()() are all unbalanced parenthesis strings.
The steps required to Check for balanced parentheses are as follows:
- Create an empty character stack.
- While traversing, push every open parentheses character including ( , { , [ into the stack.
- 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.
- If stack contains, corresponding open parentheses character, then pop it out and continue the string traversal.
- Else, return false as given parentheses string is not balanced.
- 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:
- Next Greater Element
- Find Minimum number of bracket reversals required to make an expression balanced.
- Implement Queue Using Two Stacks.
- Merge Overlapping Intervals using Stacks
- Implement Stack Using Linked List
- Largest Rectangular Area in Histogram
- Length of Longest Valid Substring
- Reverse a String using Stack
- Implement two stacks in a single array
- Print Bracket Number
- Next Greater Frequency Element
- Sort a Stack using Temporary Stack
- Find Most Frequent Character of the String.
- Check Anagram Strings.
- Check Whether Given String is Palindromic Anagram or Not.
- Check Whether Given String is Panagram or Not.
- Find First Non-Repeating Character of the String.
- Find Most Frequent Element of the Array.
- Find Pair in an Array with Given Sum.
- Find First Repeating Element of an Array.