Program to check balanced parentheses in expression c++

Algorithm

1) Declare a character stack by STL.
2) Now traverse the expression string s.
    a) If the current character is a starting bracket ( ‘(‘ or ‘{‘ or ‘[‘ ) then push it to stack.
    b) If the current character is a closing bracket ( ‘)’ or ‘}’ or ‘]’ ) then pop from stack and match for relevant parenthesis, if match pop it from stack.
3) After complete traversal, if there is some starting bracket left in stack then parenthesis in giver expression or string are “not balanced”.

Program to check balanced parentheses in expression c++

 

#include<iostream>
#include<stdlib.h>
#include<stack>			//Use Standard template library to create Stack data structure 
using namespace std;

/* Driver functions */
bool CheckForBalancedParenthesis(char s[]);
bool Match(char char_1, char char_2);

/* Main Method */
int main()
{
	if(CheckForBalancedParenthesis("www.(firmcodes).com"))
		printf("Parenthesis are balanced \n");
	else
		printf("Parenthesis are NOT balanced \n");
	
	return 0;
}

/* Return 1 Parenthesis has balanced  */
bool CheckForBalancedParenthesis(char s[])
{
	/* Declare an character Stack using STL */
	stack<char> Stack;
	int i=0;
	
	/* Traverse the given string or expresstion to check matching parenthesis */
	while(s[i])
	{
		
		/*If the exp[i] is a starting parenthesis then push it to Stack*/
		if( s[i]=='(' || s[i]=='{' || s[i]=='[' )
		{
			Stack.push(s[i]);
		}
		
		/* If exp[i] is a ending parenthesis then check for empty stack or 
		paranthesis matching then pop it from Stack*/
		if( s[i]==')' || s[i]=='}' || s[i]==']' )
		{
			if( Stack.empty() || !Match(Stack.top(),s[i]) )
			{
				return false;
			}
			else
			{
				Stack.pop();
			}
		}
		i++;
	}
	
	/*If Stack is empty then paranthesis are balanced otherwise NOT */
	return Stack.empty();
}

/* Match for relevent paranthesis */
bool Match(char char_1, char char_2)
{
	if( char_1=='(' && char_2==')' )
		return true;
	else if(char_1=='{' && char_2=='}')
		return true;
	else if(char_1=='[' && char_2==']')
		return true;
	else
		return false;
}

 

Output

Suggested Reading

1. Write a C program to reverse the words in a sentence in place
2. Write your own trim() or squeeze() function to remove the spaces from a string
3. Write a C program which does wildcard pattern matching algorithm