Check balanced parentheses using stack in C++ with program example.
Problem statement: String of parenthesis is given for example “((())) “ or ({}) etc. and we need to find out if they are balanced. Means, if there are matching pairs or not.
for example, ({}) is balanced parentheses and ((((()) is not a balanced parenthesis.
Algorithm:
- Traverse the expression string
- If the current character is a opening bracket or parenthesis e.g. ‘(‘ or ‘{‘ or ‘[‘ then push in the stack.
- If the current character is a closing bracket e.g ‘)’ or ‘}’ or ‘]’ then pop a character from the stack and check if it is a corresponding parenthesis, if matched then pop it from stack.
- Once, string traversal is complete then check if stack is empty or not. If the stack is empty parenthesis are balanced.
Time Complexity: O(n) – traverse string of n length.
Space complexity O(n) – Due to Stack
Program for bracket matching using stack in C++
This program for parentheses matching using stack in C++ example will handle strings and expressions. Multiple test cases are given after the program.
#include<stack>//Include STL stack
/*
*Program to check balanced parentheses
using stack in C++
*/
#include<iostream>
using namespace std;
class BalancedParenthesisChecker{
public:
bool isParenthesisBalanced(char s[]){
//Char STL stack
stack<char> Stack;
int i=0;
/* Traverse the given string expression
to check matching brackets */
while(s[i])
{
/*If the s[i] is a opening bracket then
push it to Stack*/
if( s[i]=='(' || s[i]=='{' || s[i]=='[' )
{
Stack.push(s[i]);
}
/* If s[i] is a opening bracket then
*get top character from stack and match it
*to the current character if match
*found then pop it from Stack else
*return false*/
if( s[i]==')' || s[i]=='}' || s[i]==']' )
{
if( Stack.empty() || !isEqual(Stack.top(),s[i]) )
{
return false;
}
else
{
//Corresponding brackets matched
//pop it from stack
Stack.pop();
}
}
i++;
}
/*If Stack is empty then parenthesis
are balanced or else not balanced
*/
return Stack.empty();
}
private:
bool isEqual(char c1, char c2){
if( c1=='(' && c2==')' )
return true;
else if(c1=='{' && c2=='}')
return true;
else if(c1=='[' && c2==']')
return true;
else
return false;
}
};
/* Test program */
int main()
{
char str[50];
BalancedParenthesisChecker cheker;
cout<<"Enter parenthesis expression:"<<endl;
cin.getline(str,50);
bool isBalanced = cheker.isParenthesisBalanced(str);
if(isBalanced){
cout<<"Balanced"<<endl;
}else{
cout<<"Not Balanced"<<endl;
}
return 0;
}
Test Cases:
Input: “({})”
Output: Balanced
Input: “(((((((“
Output: Not Balanced
Input: “” // empty string
Output: Balanced
Input: “5x+(2/5+[3/a])”
Output: Balanced
Input: “Hello(world)!!!”
Output: Balanced