This problem is one of the standard use case scenario when learning or practicing Stack as a Data Structure, if we are familiar with the basic operarions with stack like push() and pop(), this problem can be solved very easily. All we need to know is that for every opening bracket there needs to be a closed one.

Example:

Input: (a+b)(a-b)
Output : Balanced 

Input : ((a+b)(a-b) 
Output : Not Balnced 

Solution Approach

The two main operations of a Stack Data Structure i.e Push() and Pop() are used to solve this problem. So, there are a set of brackets but they are balanced only when there are equal no.of opening and closing brackets. First we read the equation, ignooring all other characters and push the opening brackets into the stack using push operation and perform the pop operation for a closing bracket, if there are equal brackets i.e one closing bracket for every opening bracket then in the end we have an empty stack or else the brackets are not balanced.

The best part of the solution is the time complexity as it is O(N), because we iterate through the string only once and by the time we reach the end we have our answer.

Steps

1. Get the string of characters
2. Iterate through each character
3. Ignore all characters other than brackets
4. When we find an open bracket we push() it into the stack
5. For every open braacket perform pop() operation
6. In the end, if the stack is empty equation is balanced
7. Else it is not balanced.

Explanation

• First we need to creat a stack data struture, complete with nodes
• Then important functions to perform Push and Pop operations
• Another function to check whether the brackets are balanced or not
• In the Balance function we push() all open brackets into the stack
• And pop() stack content for every closed bracket we get
• At last if the brackets are equal all are popped out and it is balanced else not balanced
• Except for Brackets(), all other alphanumeric characters are ignored.

Pseudocode

1. Start
2. Initialize the Stack Data Structrue using Node
3. Create the Push() and Pop() operations
4. Now pass the equation to the Balance() function
5. In the balance fucntion iterate through all characters
6. If the character is '(' opening bracket push() it into the stack
7. When we get an closing bracket perform the pop() operation
8. We stop until we reach the end of the string
9. In the end if stack is empty it is balanced else it is not balanced.

Program in C

#include<stdio.h>
#include<stdlib.h>
struct Node 
{
	char data;
	struct Node *next;	
}*top=NULL;

void push(char x)
{
	struct Node *t;
	t=(struct Node*)malloc(sizeof(struct Node));
	if(t==NULL)
		printf("Stack is Full\n");
	else
	{
		t->data=x;
		t->next=top;
		top=t;
	}
}

void pop()
{
	char x=-1;
	if(top==NULL)
		printf("Stack is Empty\n");
	else
	{
		struct Node *t;
		t=top;
		top=top->next;
		x=t->data;
		free(t);
	}
}

int balance(char *exp)
{
	int i;
	
	for(i=0;exp[i]!='\0';i++)
	{
		if(exp[i]=='(')
			push(exp[i]);
		else if(exp[i]==')')
		{
			if(top==NULL)
				return 0;
			pop();
		}
	}
	if(top==NULL)
		return 1;
	else
		return 0;
}

int main()
{
	char *exp="((a+b)*(a-b))";
	if(balance(exp))
	    printf("Balanced");
	else
	    printf("Not Balanced");
	return 0;
}

Example Step by Step Explaination

Start

Input String : ((a+b)*(a-b))

• Initialze the Stack and Top pointer using Node with structure
• Push() and Pop() functions are ready
• Pass the string of equation to the Balance() function
• Now we start iterating till we reach the end of the string
• We ignore all characters except opening and closing brackets
• exp="((a+b)*(a-b))"
• exp[0]="(" => push() => Stack=(
• exp[1]="(" => push() => Stack=((
• exp[2]="a" => ignore=> next char => Stack=((
• exp[3]="+" => ignore=> next char => Stack=((
• exp[4]="b" => ignore=> next char => Stack=((
• exp[5]=")" => pop() =>"(" => Stack=(
• exp[6]="*" => ignore=> next char => Stack=(
• exp[7]="(" => push() => Stack=((
• exp[8]="a" => ignore=> next char => Stack=((
• exp[9]="-" => ignore=> next char => Stack=((
• exp[10]="b" => ignore=> next char => Stack=((
• exp[11]=")" => pop() =>"(" => Stack=(
• exp[12]=")" => pop() =>"(" => Stack
• End of loop exit
• if TOP==NULL i.e stack is empty return 1
• if 1 print("Balanced");
• else print("Not Balanced");

END

Thoughts and different approaches

Here we deal directly with the operations of the stack, the main focus is on entirely push and pop operations sticking to the coditiong to push every open bracket and pop for every closing bracket, there are still many use cases for this use case like consider using different types of brackets.The best part of this problem is we solve this with O(N) time complexity.

With this article at OpenGenus, you must have the complete knowledge of C program to check whether brackets are Balanced in an Equation, Cheers.