STACK

A stack is a LIFO (Last In First Out) or FILO (First In Last Out) data structure in which
items are inserted and deleted from only one end called Top of stack. In other
words, a stack can be defined as a container in which insertion and
deletion can be done from the one end known as the top of the stack.

A stack is used in such a situation when we want to retrieve items in the reverse
order of their storage.

PUSH POP

Standard Stack Operations

The following are some common operations implemented on the stack:

o Push(): When we insert an item into the stack then the operation is known
as a push. If the stack is full then the overflow error occurs.
o Pop(): When we delete an item from the stack, the operation is known as a
pop. If the stack is empty the underflow error occurs.
o isFull(): It determines whether the stack is full or not.
o isEmpty(): It determines whether the stack is empty or not.
o Peek(): It returns the top item of stack without removing it.
o Display(): It prints all the items available in the stack.

Application of Stack

 Reversing a string
  Undo sequence in a text editor
 Balancing of symbols
 Infix-to-postfix conversion
 Evaluation of postfix expression
 Function calling
 Large number arithmetic

PUSH

Algorithm

PUSH(stack,top,item)

Step1: [Is stack already full?]

If top=MAXSIZE-1 then
write “Stack overflow error”
return
[End of if structure]
Step 2: [Increase top by 1]

set top = top+1

Step 3: [Insert item at top of stack]

set stack[top]=item
Step 4: return

POP
Algorithm

POP(stack,top)

Step1: [Is stack already empty?]

If top=-1 then
write “Stack underflow error”
return
[End of if structure]
Step 2: [Store top most item of stack]

set delitem = stack[top]

Step 3: [Decrease top by 1]

 set top = top-1
Step 4: return delitem

/*A PROGRAM TO PERFORM OPERATIONS ON STACK USING ARRAY*/

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 5

int stack[MAXSIZE];
int top=-1;

int isFULL(void)
{
if(top==MAXSIZE-1)
return 1;
return 0;
}

int isEMPTY(void)
{
if(top==-1)
return 1;
return 0;
}

void PUSH(int item)

{
if(isFULL())
printf("Stack overflow error.");
else
{
top=top+1;
stack[top]=item;
printf("\n%d is pushed in stack.",item);
}
}

int POP(void)
{
int delitem;

if(isEMPTY())
{
printf("Stack underflow error.");
return -1;
}
delitem=stack[top];
top=top-1;
 return delitem;
}

int PEEK(void)
{
if(isEMPTY())
{
printf("Stack underflow error.");
return -1;
}

return stack[top];
}

void DISPLAY(void)
{
int i;

if(isEMPTY())
printf("Stack is empty.");
else
{
printf("Items of Stack are\n");
for(i=top;i>=0;i--)
printf("%d\n",stack[i]);
}
}

int main()
{
int item,choice;

while(1)
{

printf("\n\t\t\t_ _ _ _ OPERATIONS ON STACK _ _ _ _\n");

printf("\n\n\t\t\t1. PUSH");
printf("\n\n\t\t\t2. POP");
printf("\n\n\t\t\t3. PEEK");
printf("\n\n\t\t\t4. DISPLAY");
printf("\n\n\t\t\t5. EXIT");
printf("\n\nEnter your choice:");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("\nEnter the item to be pushed:");
scanf("%d",&item);
PUSH(item);
break;
 case 2:
item=POP();
if(item!=-1)
printf("\n%d is popped from stack",item);
break;

case 3:
item=PEEK();
if(item!=-1)
printf("Top item of stack = %d",item);
break;

case 4:
DISPLAY();
break;

case 5:
printf("\n\n\t\t\t_ _ _ Good Bye _ _ _");
exit(0);

default:
printf("\nWrong choice");
}
}
return 0;
}

Representation of arithmetic expression

An arithmetic expression can be represented in one of the following notations-

(i) Infix notation

In an expression, if an operator is in between two operands, the
expression is called an infix expression. The infix expression can be
parenthesized or un-parenthesized.
For example,
a + b is an un-parenthesized infix expression
(a + b) is a parenthesized infix expression

(ii) Prefix notation

In an expression, if an operator precedes the two operands (i.e.,
operator comes before the two operands), the expression is called
prefix expression. No, parenthesis is allowed in prefix expressions.
The prefix expression is always un-parenthesized.
It is also called polish expression.
 For example,
+ab

(iii) Postfix notation

In an expression, if an operator follows the two operands (i.e.,
operator comes after the two operands), the expression is called
postfix expression. No, parenthesis is allowed in postfix
expressions. The postfix expression is always un-parenthesized.
It is also called suffix expression or reverse polish expression.
For example,
ab+

Conversion from infix to postfix

Q. Convert the infix expression A+B*C into postfix expression.

Solution:

Given

A+B*C (Infix)

A+(B*C)

A+(BC*)

A+D Where D = (BC*)

AD+

Now expanding AD+

ABC*+ (Postfix)

Q. Convert the infix expression (A+B)*C into postfix expression.

Solution:

Given

(A+B)*C (Infix)

(AB+)*C

D*C Where D = (AB+)

DC*
Now expanding DC*

AB+C* (Postfix)

Q. Convert the infix expression A*B+C/D into postfix expression.

Solution:
Given
A*B+C/D (Infix)
(A*B)+C/D
(AB*)+C/D
E+C/D Where E=(AB*)
E+(C/D)
E+(CD/)
E+F Where F=(CD/)
EF+
Now expanding EF+
AB*F+
AB*CD/+ (Postfix)

Q. Convert the infix expression (A+B)*C/D+E^F/G into postfix expression.

Solution:
Given
(A+B)*C/D+E^F/G (Infix)
(AB+)*C/D+E^F/G
H*C/D+E^F/G Where H=(AB+)
H*C/D+(E^F)/G
H*C/D+(EF^)/G
H*C/D+I/G Where I=(EF^)
(H*C)/D+I/G
(HC*)/D+I/G
J/D+I/G Where J=(HC*)
(J/D)+I/G
(JD/)+I/G
K+I/G Where K=(JD/)
K+(I/G)
K+(IG/)
K+L Where L=(IG/)
KL+
Now expanding KL+
JD/L+
HC*D/L+
AB+C*D/L+
AB+C*D/IG/+
AB+C*D/EF^G/+ (Postfix)
Q. Convert the infix expression A+(B*C-(D/E^F)*G)*H into postfix expression.

Solution:
Given
A+(B*C-(D/E^F)*G)*H (Infix)
A+(B*C-(D/(E^F))*G)*H
A+(B*C-(D/(EF^))*G)*H
A+(B*C-(D/I)*G)*H Where I=(EF^)
A+(B*C-(DI/)*G)*H
A+(B*C-J*G)*H Where J=(DI/)
A+((B*C)-J*G)*H
A+((BC*)-J*G)*H
A+(K-J*G)*H Where K=(BC*)
A+(K-(J*G))*H
A+(K-(JG*))*H
A+(K-L)*H Where L=(JG*)
A+(KL-)*H
A+M*H Where M=(KL-)
A+(M*H)
A+(MH*)
A+N Where N=(MH*)
AN+
Now expanding AN+
AMH*+
AKL-H*+
ABC*L-H*+
ABC*JG*-H*+
ABC*DI/G*-H*+
ABC*DEF^/G*-H*+ (Postfix)

Converting Infix Expression into Postfix Expression

Algorithm

POLISH(Q,P)

Suppose Q is an arithmetic expression written in infix notation. This

algorithm finds the equivalent postfix expression P.

Step1: Push “(“ onto STACK and add “)” to the end of Q.
Step 2: Scan Q from left to right and repeat Steps 3 to 6 for each element of Q until
the STACK is empty:

Step 3: If an operand is encountered, add it to P.

Step 4: If a left parenthesis is encountered, push it onto STACK.
Step 5: If an operator × is encountered then:
(a) Repeatedly pop from STACK and add to P each operator(on the
top of STACK) which has the same precedence as or higher
precedence than ×.
 (b) Add × to STACK
[End of If structure]
Step 6: If a right parenthesis is encountered then:
(a) Repeatedly pop from STACK and add to P each operator(on the
top of STACK) until a left parenthesis is encountered.
(b) Remove the left parenthesis.
[End of If structure]
[End of Step 2 loop]
Step 7: return

Q. Convert the infix expression A+(B*C-(D/E^F)*G)*H into postfix expression.

Solution: Suppose Q is an arithmetic expression written in infix notation.

Q: A+(B*C-(D/E^F)*G)*H
We add right parenthesis “)” at the end of Q and push left parenthesis “(“ onto
STACK.

Q: A+(B*C-(D/E^F)*G)*H)

Symbol Scanned STACK Expression P

(
A ( A
+ (+ A
( (+( A
B (+( AB
* (+(* AB
C (+(* ABC
- (+(- ABC*
( (+(-( ABC*
D (+(-( ABC*D
/ (+(-(/ ABC*D
E (+(-(/ ABC*DE
^ (+(-(/^ ABC*DE
F (+(-(/^ ABC*DEF
) (+(- ABC*DEF^/
* (+(-* ABC*DEF^/
G (+(-* ABC*DEF^/G
) (+ ABC*DEF^/G*-
* (+* ABC*DEF^/G*-
H (+* ABC*DEF^/G*-H
) ABC*DEF^/G*-H*+

/*A PROGRAM TO INPUT INFIX EXPRESSION AND CONVERT IT INTO POSTFIX

EXPRESSION*/

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXSIZE 20

char stack[MAXSIZE];
int top=-1;

int isFULL(void)
{
if(top==MAXSIZE-1)
return 1;
return 0;
}

int isEMPTY(void)
{
if(top==-1)
return 1;
return 0;
}

void PUSH(char sym)

{
if(isFULL())
{
printf("\nStack overflow error.");
exit(1);
}
top=top+1;
stack[top]=sym;
}

char POP(void)
{
char delitem;
if(isEMPTY())
{
printf("Stack underflow error.");
exit(1);
}
delitem=stack[top];
top=top-1;
return delitem;
}

int PRECED(char ch)

{
if(ch=='+'||ch=='-')
return 1;
if(ch=='*'||ch=='/')
return 2;
 if(ch=='^')
return 3;
return 0;
}

void INFIX_POST(char infix[])

{
char postfix[25];
char symbol,temp;
int i=0,j=0;

while(top!=-1)
{
symbol=infix[i];
switch(symbol)
{
case '(':
PUSH(symbol);
break;

case ')':
temp=POP();
while(temp!='(')
{
postfix[j]=temp;
j++;
temp=POP();
}
break;

case '+':
case '-':
case '*':
case '/':
case '^':
while(PRECED(stack[top])>=PRECED(symbol))
{
temp=POP();
postfix[j]=temp;
j++;
}
PUSH(symbol);
break;

default:
postfix[j]=symbol;
j++;
}
i++;
 }
postfix[j]='\0';
printf("\nPostfix expression = %s",postfix);
}

int main()
{
char infix[25];
int len;

printf("Enter any valid infix expression:");

scanf("%s",infix);
len=strlen(infix);
PUSH('(');
infix[len]=')';
infix[len+1]='\0';
INFIX_POST(infix);
return 0;
}

Evaluation of a Postfix Expression

Algorithm

Suppose P is an arithmetic expression written in postfix notation. This

algorithm finds the value of P.

Step1: Add a right parenthesis “)” at the end of P.

Step 2: Scan P from left to right and repeat Steps 3 and 4 for each element of P
until the sentinel “)” is encountered.

Step 3: If an operand is encountered, put it on STACK.

Step 4: If an operator × is encountered then:
(a) Remove the two top elements of STACK where A is the top element
and B is the next-to-top element.
(b) Evaluate B×A.
(c) Place the result of (b) back on STACK.
[End of If structure]
[End of Step 2 loop]
Step 5: Set VALUE equal to the top element on STACK.

Q. Convert the infix expression 5*(6+2)-12/4 into postfix and evaluate it.

Solution:
Given
5*(6+2)-12/4
5*(6 2 +)-12/4
5*A-12/4 where A = (6 2 +)
(5*A)-12/4
(5A*)-12/4
B-12/4 where B = (5A*)
B-(12/4)
B-(12 4 /)
B-C where C = (12 4 /)
BC-
Now expanding BC-
5A*C-
562+*C–
5 6 2 + * 12 4 / - (Postfix)

Evaluation of Postfix Expression

Suppose P is an arithmetic expression written in infix notation.

P: 5 6 2 + * 12 4 / -
We add right parenthesis “)” at the end of P.

P: 5 6 2 + * 12 4 / -)

Symbol Scanned STACK

5 5
6 5,6
2 5,6,2
+ 5,8
* 40
12 40,12
4 40,12,4
/ 40,3
- 37
)

/*A PROGRAM TO INPUT POSTFIX EXPRESSION AND FIND ITS VALUE*/

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
#include<math.h>
#define MAXSIZE 20

float stack[MAXSIZE];
int top=-1;

int isFULL(void)
{
 if(top==MAXSIZE-1)
return 1;
return 0;
}

int isEMPTY(void)
{
if(top==-1)
return 1;
return 0;
}

void PUSH(float val)

{
if(isFULL())
{
printf("Stack overflow error.");
exit(1);
}
top=top+1;
stack[top]=val;
}

float POP(void)
{
float delitem;

if(isEMPTY())
{
printf("Stack underflow error.");
exit(1);
}
delitem=stack[top];
top=top-1;
return delitem;
}

float POST_EVAL(char postfix[])

{
float value=0;
float A,B,res;
char symbol;
int i=0;
while(postfix[i]!=')')
{
symbol=postfix[i];
switch(symbol)
{
case '+':
case '-':
 case '*':
case '/':
case '^':
A=POP();
B=POP();
if(symbol=='+')
res=B+A;
else if(symbol=='-')
res=B-A;
else if(symbol=='*')
res=B*A;
else if(symbol=='/')
res=(float)B/A;
else
res=pow(B,A);
PUSH(res);
break;
default:
if(isdigit(symbol))
{
do
{
value=value*10+(symbol-48);
i++;
symbol=postfix[i];
}while(symbol!=' ');
PUSH(value);
value=0;
}
}
i++;
}
value=POP();
return value;
}

int main()
{
char postfix[25];
int len;

printf("Enter any valid postfix expression:");

fgets(postfix,25,stdin);
len=strlen(postfix);
postfix[len]=')';
postfix[len+1]='\0';
printf("\nPostfix value = %f",POST_EVAL(postfix));
return 0;
}