Algorithm:
1) Now traverse the expression string exp.
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 if the popped character is the matching starting bracket then fine else parenthesis are not balanced.
2) After complete traversal, if there is some starting bracket left in stack then “not balanced”
Implementation :
/* Author :- Mufaddal Kagda */
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
struct node
{
int info;
struct node *link;
};
typedef struct node SNODE;
int push(SNODE **,int);
int display(SNODE *);
bool areParenthesisBalanced(char exp[]);
bool isMatchingPair(char character1, char character2);
int pop(SNODE **);
int main()
{
SNODE *pnew,*ptop;
int rv,ch,k,val;
system("CLS");
ptop=NULL;
char exp[100];
while(1)
{
system("CLS");
printf("\n1.Insert an expression.");
printf("\n2.exit");
printf("\nEnter your choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\nEnter an Expression to check : ");
scanf("%s",exp);
if(areParenthesisBalanced(exp))
printf("\n Balanced ");
else
printf("\n Not Balanced ");
break;
default:
exit(0);
}
getch();
}
return 0;
}
int push(SNODE **aptop,int val)
{
SNODE *pnew;
pnew=(SNODE *)malloc(sizeof(SNODE));
pnew->info=val;
pnew->link=*aptop;
*aptop=pnew;
return 0;
}
int display(SNODE *pcurr)
{
while(pcurr !=NULL)
{
printf(" %d",pcurr->info);
pcurr=pcurr->link;
}
return 0;
}
int pop(SNODE **ptop)
{
SNODE *pdel;
int ret;
if(*ptop==NULL)
return -1;
pdel=*ptop;
(*ptop)=(*ptop)->link;
ret=pdel->info;
free(pdel);
return ret;
}
bool isMatchingPair(char character1, char character2)
{
if(character1 == '(' && character2 == ')')
return 1;
else if(character1 == '{' && character2 == '}')
return 1;
else if(character1 == '[' && character2 == ']')
return 1;
else
return 0;
}
bool areParenthesisBalanced(char exp[])
{
int i = 0;
SNODE *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 ( !isMatchingPair(pop(&stack), exp[i]) )
return 0;
}
i++;
}
if(stack == NULL)
return 1; /*balanced*/
else
return 0; /*not balanced*/
}
