STACK

Introduction
• Stack is a linear data structure which follows a particular order in which
the operations are performed. The order may be LIFO(Last In First Out) or
FILO(First In Last Out).
• There are many real-life examples of a stack. for example – a deck of
cards or a pile of plates, etc.

• Stack ADT allows all data operations at one end only. At any given time,
we can only access the top element of a stack.
Contd…
• Stack principle: LAST IN FIRST OUT = LIFO
• It means: the last element inserted is the first one to be removed.
• It uses a top pointer which will point to the last element inserted.
• Here, the element which is placed (inserted or added) last, is accessed
first. In stack terminology, insertion operation is
called PUSH operation and removal operation is called POP operation.
Stack Representation
• A stack can be implemented by means of Array or Linked List. Stack
can either be a fixed size one or it may have a sense of dynamic
resizing.
• Array will give fixed size stack
• Linked list will give dynamic stack.
Applications of stack:
• Balancing of symbols
• Infix to Postfix/Prefix conversion a+b*c/d*e
• Redo-undo features at many places like editors, photoshop.
• Forward and backward feature in web browsers
• Used in many algorithms like Tower of Hanoi tree traversals, stock span
problem, histogram problem.
• Other applications can be Backtracking, Knight tour problem, rat in a
maze, N queen problem and sudoku solver
• In Graph Algorithms like Topological Sorting and Strongly Connected
Components
Basic Operations

• Stack operations may involve initializing the stack, using it and then
de-initializing it. Apart from these basic stuffs, a stack is used for the
following two primary operations −
• push() − Pushing (storing) an element on the stack.
• pop() − Removing (accessing) an element from the stack.
Push Operation

• The process of putting a new data element onto stack is known as a Push
Operation. Push operation involves a series of steps −
• Step 1 − Checks if the stack is full.
• Step 2 − If the stack is full, produces an error and exit.
• Step 3 − If the stack is not full, increments top to point next empty space.
• Step 4 − Adds data element to the stack location, where top is pointing.
• Step 5 − Returns success.
• *Note:If the linked list is used to implement the stack, then in step 3, we
need to allocate space dynamically.
Last In First Out

E top
top
D D D
C top C C C
B top B B B B
A A A A A
Top
A
PUSH
void push()
{
if(top>=n-1)
{ printf("\n\tSTACK is over flow");
}
else
{
printf(" Enter a value to be pushed:");
scanf("%d",&x);
top=top+1;
stack[top]=x;
}}
Pop Operation
• Accessing the content while removing it from the stack, is known as a Pop Operation. In an
array implementation of pop() operation, the data element is not actually removed,
instead top is decremented to a lower position in the stack to point to the next value. But in
linked-list implementation, pop() actually removes data element and deallocates memory
space.
• A Pop operation may involve the following steps −
• Step 1 − Checks if the stack is empty.
• Step 2 − If the stack is empty, produces an error and exit.
• Step 3 − If the stack is not empty, accesses the data element at which top is pointing.
• Step 4 − Decreases the value of top by 1.
• Step 5 − Returns success.
Pop Operation
void pop()
{
if(top==-1)
{
printf("\n\t Stack is under flow");
}
else
{
X=STACK[TOP]
//printf("\n\t The popped elements is %d",stack[top]);
top--;
}
}
 case 2:
{

Program
#include<stdlib.h>
pop();
break;
#include<stdio.h>
}
int stack[100],choice=1,n,top=-1,x,i; case 3:
void push(void); {
void pop(void); display();
void display(void);
break;
int main()
{ }
case 4:
printf("\n Enter the size of STACK[MAX=100]:"); {
scanf("%d",&n); exit(1);
while(choice) break;
{ printf("\[Link]\n [Link]\n [Link]\n [Link]"); }
printf("\n Enter the Choice:"); default:
scanf("%d",&choice); {
switch(choice)
{ case 1: printf ("\n\t Please Enter a Valid Choice(1/2/3/4)");
{ printf(" Enter a value to be pushed:"); }
scanf("%d",&x);
push(); }
break;
} }
Contd.. else
{
void push() printf("\n\t The popped elements is %d",stack[top]);
{ top--;
if(top>=n-1) }
{
printf("\n\tSTACK is over flow");
}
void display()
} {
else if(top>=0)
{
{
stack[++top]=x; printf("\n The elements in STACK \n");
} for(i=top; i>=0; i--)
} printf("\n%d",stack[i]);
void pop() printf("\n Press Next Choice");
{
if(top<=-1) }
{ else
printf("\n\t Stack is under flow"); {
} printf("\n The STACK is empty");
}

}
Data Structure - Expression Parsing

• The way to write arithmetic expression is known as a notation. An

arithmetic expression can be written in three different but equivalent
notations, i.e., without changing the essence or output of an
expression. These notations are −
• Infix Notation
• Prefix (Polish) Notation
• Postfix (Reverse-Polish) Notation
Infix Notation

• We write expression in infix notation, e.g. a - b + c, where operators

are used in-between operands. It is easy for us humans to read, write,
and speak in infix notation but the same does not go well with
computing devices. An algorithm to process infix notation could be
difficult and costly in terms of time and space consumption.
Prefix Notation

• In this notation, operator is prefixed to operands, i.e. operator is

written ahead of operands. For example, +ab. This is equivalent to its
infix notation a + b. Prefix notation is also known as Polish Notation.
Postfix Notation

• This notation style is known as Reversed Polish Notation. In this

notation style, the operator is postfixed to the operands i.e., the
operator is written after the operands. For example, ab+. This is
equivalent to its infix notation a + b.
 [Link]. Infix Notation Prefix Notation Postfix Notation

1 a+b ab+

2 (a + b) ∗ c ab+c∗

3 a ∗ (b + c) abc+∗

4 a/b+c/d ab/cd/+

5 (a + b) ∗ (c + d) ab+cd+∗

6 ((a + b) ∗ c) - d ab+c∗d-
Parsing Expressions

• As we have discussed, it is not a very efficient way to design an

algorithm or program to parse infix notations. Instead, these infix
notations are first converted into either postfix or prefix notations by
computer and then computed.
• To parse any arithmetic expression, we need to take care of operator
precedence and associativity also.
 Precedence
• When an operand is in between two different operators, which
operator will take the operand first, is decided by the precedence of an
operator over others. For example −

• As multiplication operation has precedence over addition, b * c will be

evaluated first.
•^
• *, /
• +, -
Associativity
• Associativity describes the rule where operators with the same
precedence appear in an expression. For example, in expression
• a + b − c, both + and – have the same precedence, then which part of
the expression will be evaluated first, is determined by associativity of
those operators. Here, both + and − are left associative, so the
expression will be evaluated as (a + b) − c.
• Precedence and associativity determines the order of evaluation of an
expression.
• POWER: RIGHT TO LEFT
• 3^2^4
operator precedence and associativity table
(highest to lowest) −
[Link]. Operator Precedence Associativity

1 Exponentiation ^ Highest Right Associative

2 Multiplication Second Highest Left Associative

( ∗ ) & Division ( /
)

3 Addition ( + ) & Lowest Left Associative

Subtraction ( − )
Algorithm to convert Infix To Postfix
• Let, X is an arithmetic expression written in infix notation. This algorithm finds the
equivalent postfix expression Y.
1. Push “(“onto Stack, and add “)” to the end of X.
2. Scan X from left to right and repeat Step 3 to 6 for each element of X until the Stack is
empty. A+B*C ^
3. If an operand is encountered, add it to Y. *
4. If a left parenthesis is encountered, push it onto Stack. +
5. If an operator is encountered ,then:
I. Repeatedly pop from Stack and add to Y each operator (on the top of Stack) which has the same
precedence as or higher precedence than operator.
II. Add operator to Stack.
[End of If]
6. If a right parenthesis is encountered ,then:
I. Repeatedly pop from Stack and add to Y each operator (on the top of Stack) until a left
parenthesis is encountered.
II. Remove the left Parenthesis.
[End of If]
[End of If]
7. END.
E XAMP
LE
 Let the incoming the Infix expression be:

A * (B + C) – D / E

Stage 1: Stack is empty and we only have the Infix

Expression.
E XAMP
LE

Stage 2

 The first token is Operand A Operands are Appended to the

Output as it is.
E XAMP
LE

Stage 3

 Next token is * Since Stack is empty (top==NULL) it is

pushed into the Stack

E XAMP
LE
Stage 4
 Next token is ( the precedence of open-parenthesis, when it is to go

inside, is maximum.

 But when another operator is to come on the top of „(„ then its

precedence is least.
E XAMP
LE
Stage 5

 Next token, B is an operand which will go to the Output expression

as it is
E XAMP
LE
Stage 6

 Next token, + is operator, We consider the precedence of top

element in the Stack, „(‘. The outgoing precedence of open

parenthesis is the least (refer point 4. Above). So + gets pushed

into the Stack

E XAMP
LE

Stage 7

 Next token, C, is appended to the

output
E XAMP
LE

Stage 8

 Next token ), means that pop all the elements from Stack and

append them to the output expression till we read an

opening parenthesis.
E XAMP
LE
Stage 9

 Next token, -, is an operator. The precedence of operator on the top

of Stack „*‘ is more than that of Minus. So we pop multiply and

append it to output expression. Then push minus in the Stack.

E XAMP
LE
Stage 10

 Next, Operand ‘D‘ gets appended to the output.

E XAMP
LE
Stage 11

 Next, we will insert the division operator into the Stack because its

precedence is more than that of minus.

E XAMP
LE
Stage 12

 The last token, E, is an operand, so we insert it to the output

Expression as it is.
E XAMP
LE
Stage 13

 The input Expression is complete now. So we pop the Stack and

Append it to the Output Expression as we pop it.

InfixStack
to postfix conversion
Infix Expression
(a+b-c)*d–(e+f)

Postfix Expression
InfixStack
to postfix conversion
Infix Expression
a+b-c)*d–(e+f)

Postfix Expression

(
InfixStack
to postfix conversion
Infix Expression
+b-c)*d–(e+f)

Postfix Expression
a

(
InfixStack
to postfix conversion
Infix Expression
b-c)*d–(e+f)

Postfix Expression
a

+
(
InfixStack
to postfix conversion
Infix Expression
-c)*d–(e+f)

Postfix Expression
ab

+
(
InfixStack
to postfix conversion
Infix Expression
c)*d–(e+f)

Postfix Expression
ab+

-
(
InfixStack
to postfix conversion
Infix Expression
)*d–(e+f)

Postfix Expression
ab+c

-
(
InfixStack
to postfix conversion
Infix Expression
*d–(e+f)

Postfix Expression
ab+c-
InfixStack
to postfix conversion
Infix Expression
d–(e+f)

Postfix Expression
ab+c-

*
InfixStack
to postfix conversion
Infix Expression
–(e+f)

Postfix Expression
ab+c-d

*
InfixStack
to postfix conversion
Infix Expression
(e+f)

Postfix Expression
ab+c–d*

-
InfixStack
to postfix conversion
Infix Expression
e+f)

Postfix Expression
ab+c–d*

(
-
InfixStack
to postfix conversion
Infix Expression
+f)

Postfix Expression
ab+c–d*e

(
-
InfixStack
to postfix conversion
Infix Expression
f)

Postfix Expression

+ ab+c–d*e

(
-
InfixStack
to postfix conversion
Infix Expression
)

Postfix Expression

+ ab+c–d*ef

(
-
InfixStack
to postfix conversion
Infix Expression

Postfix Expression
ab+c–d*ef+

-
InfixStack
to postfix conversion
Infix Expression

Postfix Expression
ab+c–d*ef+-
 (4+5)-(2*6/3)*2=1

Y=45+26*3/2*-

Result= 4 +5=9
2* 6=12
12/ 3=4
4 *2=8
8
9-8=1

9
 X=3+6*2^2-10/5^1
• Y=3622^*+1051^/-

Y=3622^*+1051^/-
Output=
2^2=4
6*4=24
2 3+24=27
5^1=5
27
10/5=2
27-2=25
Infix=(a+b*c-d(e*f)/g)

Postfix: abc*+def*g/-
Example 2

• ((A+B)—C*(D/E))+F
•  A B + C D E / * - F +
 Evaluation rule of a Postfix Expression
states:
1. While reading the expression from left to right, push the element in
the stack if it is an operand.
2. Pop the two operands from the stack, if the element is an operator
and then evaluate it.
3. Push back the result of the evaluation. Repeat it till the end of the
expression.
 Advantages of Postfix
Expression:
 (A). Postfix notation is easier to work with. In a
postfix
• expression operators operands appear before the operators, there is no need
of operator precedence and other rules. In postfix expression the topmost
operands are popped off and operator is applied and the result is again
pushed to the stack and thus finally the stack contains a single value at the
end of the process.
 (B). In postfix expression, there are no parentheses and therefore the
order of evaluation will be determined by the positions of the operators
and related operands in the expression.
How to evaluate postfix (manually):Example
43*67+5-+
Going from leto right, if you see an operator, apply it
to the previous two operands (numbers)
Example:
A B C * D / + E F - -
(B*C) (E – F)
((B*C)/D)

(A+(B*C)/D)

((A+(B*C)/D)-(E-F))
Equivalent infix: A+ B * C / D– (E– F)
Infix: 2+3*4/2*3+4-3

Postfix:234*2/3*+4+3-
 else if(*e == '(')

push(*e);

Program: Infix to postfix

else if(*e == ')')

x=pop();
#include<stdio.h>
while(x != '(')
#include<conio.h>
{
#include<ctype.h>
printf("%c", x);
char stack[20];
x=pop();
int top = -1;
}
char pop();
}
int priority(char);
else
void push(char);
{
main()
while(priority(stack[top]) >= priority(*e))
{
printf("%c",pop());
char exp[20],*e, x;

printf("Enter the expression :: ");

push(*e);
scanf("%s",exp);
}
e = exp;
e++;
while(*e)

{
}

if(isalnum(*e)) //The isalphanum() function returns a non-zero integer if an argument (character)

passed to the

printf("%c",*e); //function is an alphanumeric (alphabet and number) character derived in

 Program : evaluate postfix
#include<stdio.h>

#include<ctype.h>
while( (ch=pofx[i++]) != '\0')
int s[30];
{
int top=-1;
if(isdigit(ch))
push(int elem)
push(ch-'0'); //-'0'
{
else
s[++top]=elem;
{
}
op2=pop();
int pop()
op1=pop();
{
switch(ch)
return(s[top--]);
{
}
case '+':push(op1+op2);break;
main()
case '-':push(op1-op2);break;
{
case '*':push(op1*op2);break;
char pofx[50],ch;
case '/':push(op1/op2);break;
int i=0,op1,op2;
}
printf("\n\nRead the Postfix Expression ? ");
}
scanf("%s",pofx);
}

printf(" Result after Evaluation: %d\n",s[top]);