Page 155 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes different notations (Prefix, Postfix, Infix) into one another are performed using stacks. Stacks are
widely used inside computer when recursive functions are called. The computer evaluates an
arithmetic expression written in infix notation in two steps. First, it converts the infix expression
to postfix expression and then it evaluates the postfix expression. In each step, stack is used to
accomplish the task.
Some applications of stack are listed below:

9.5.1 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—]);
}

148 LOVELY PROFESSIONAL UNIVERSITY