Application of Stacks
Parenthesis checker
It is an algorithm that confirms that the number of closing parenthesis equals opening parenthesis by using stack. If number of closing parenthesis is not equal to the number of opening parenthesis, then it results in an error. Input a string from the user. The user must enter a set of opening and closing parenthesis as follows:
(()(()))
Scan the above input string from first character until NULL is found. If it is an opening parenthesis, then push it in the stack, otherwise, if a closing parenthesis is found, pop the topmost element of the stack. If the string ends and the stack becomes empty, then there is a perfect match, otherwise, you may report error by returning appropriate value to the invoking function.
Program for Parenthesis checker is as follows:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define MAX 20
struct stack
{
int top;
char arr[MAX];
};
void push(struct stack *s,char ch)
{
if(s->top==MAX-1)
{printf(“Stack Overflow.”);
exit(1);
}
s->arr[++(s->top)]=ch;
}
char pop(struct stack *s)
{
if(s->top==-1)
{printf(“Stack Underflow.”);
exit(1);
}
return(s->arr[s->top–]);
}
int parenthesischecker(char str[])
{
struct stack s;
char ch;
int i,flag=0;/*0 for no error, 1 for error*/
s.top=-1;
for(i=0;((str[i]!=”) && (flag==0));i++)
{if(str[i]=='(‘)
push(&s,str[i]);
else
{ch=pop(&s);
if(ch!='(‘)
flag=1;
}
}
if(s.top!=-1)
flag=1;
return flag;
}
void main()
{
char str[MAX],flag;
clrscr();
printf(“nEnter a string of parenthesis?”);
gets(str);
flag=parenthesischecker(str);
if(flag==0)
{printf(“nParenthesis Match O.K.”);
}
else
{printf(“nOpening/Closing Parenthesis do not match.”);
}
getch();
}