Check for Balanced Brackets in an Expression (well-formedness) using Stack

Write a program that check the correctness of the pairs and ordering of the characters “{“, “}”, “(“, “)”, “[“, “]” in the expression string exp.

Example:

Checking for balanced parenthesis is one of the most important tasks of a compiler.
int main () {
	for ( int i = 0; i < 10; i ++ ) {
		// Some code
	}
  }
}    <----The Compiler generates an error.

Algorithm:

• Consider a character stack to Sp.
• Go over the exp expression string presently.
• Push the character to the stack if it is a starting bracket (‘(‘ or ‘{‘ or ‘[‘).
• If the currently displayed character is a closing bracket (‘)’ or ‘}’ or ‘]’), pop it from the stack; if it is the corresponding opening bracket, everything is OK; otherwise, the brackets are not balanced.
• If some initial brackets remain in the stack upon traversal, the balance is "not balanced."

The implementation of the aforementioned concept is seen below:

C Program:

#include <stdio.h>
#include <stdlib.h>
#define bool int


struct spNode {
	char data;
	struct spNode* next;
};
void push ( struct spNode** top_ref, int newdata );
int pop ( struct spNode** topref );
bool istheMatchingPair ( char character01, char character02 )
{
	if ( character01 == '(' && character02 == ')')
		return 1;
	else if ( character01 == '{' && character02 == '}' )
		return 1;
	else if ( character01 == '[' && character02 == ']' )
		return 1;
	else
		return 0;
}
bool aretheBracketsBalanced ( char exp [] )
{
	int i = 0;


	struct spNode* stack = NULL;


	while ( exp [i] )
	{
		if ( exp [i] == '{' || exp [i] == '(' || exp [i] == '[' )
			push ( & stack, exp [i] );


		if ( exp [i] == '}' || exp [i] == ')'
			|| exp[i] == ']' ) {


			if ( stack == NULL )
				return 0;


			else if ( !istheMatchingPair ( pop ( & stack ), exp [i] ) )
				return 0;
		}
		i++;
	}
	if ( stack == NULL )
		return 1; // balanced
	else
		return 0; // not balanced
}
int main ()
{
	char exp [100] = "{()}[]";
	if ( aretheBracketsBalanced (exp) )
		printf ("Balanced \n" );
	else
		printf ( "Not Balanced \n" );
	return 0;
}
void push ( struct spNode** topref, int newdata )
{
	struct spNode* newnode
		= ( struct spNode* ) malloc ( sizeof ( struct spNode ) );
	if ( newnode == NULL ) {
		printf ( "Stack overflow n" );
		getchar ();
		exit (0);
	}
	newnode -> data = newdata;
	newnode -> next = ( *topref );
	( *topref ) = newnode;
}
int pop ( struct spNode** topref )
{
	char res;
	struct spNode* top;
	if ( *topref == NULL ) {
		printf ( "Stack overflow n" );
		getchar ();
		exit (0);
	}
	else {
		top = *topref;
		res = top -> data;
		*topref = top -> next;
		free (top);
		return res;
	}
}

C++ Program:

#include <bits/stdc++.h>
using namespace std;


bool aretheBracketsBalanced ( string exp )
{
	stack<char> temp;
		for ( int i = 0; i < exp.length (); i++ )
		{
			if ( temp.empty() )
			{
				temp.push ( exp [i] );
			}
			else if ( ( temp.top() =='('&& exp [i]==')') || ( temp.top ()=='{' && exp [i] =='}') || ( temp.top () =='[' && exp [i]==']' ) )
			{
				temp.pop ();
			}
			else
			{
				temp.push ( exp [i] );
			}
		}
		if ( temp.empty () )
		{
			return true;
		}
		return false;
}
int main ()
{
	string exp = "{()}[]";
	if ( aretheBracketsBalanced (exp) )
		cout << "Balanced";
	else
		cout << "Not Balanced";
	return 0;
}

Output:

Balanced

Time Complexity: O(n)

Space Complexity: O(n) for stack.