Chapter 3: Stack
Chapter 3: STACK
Topics
• Introduction
• Stack
• Operations on Stack
• Implementation of Stack in Python
• Notations for Arithmetic Expressions
• Conversion From Infix To Postfix Notation
• Evaluation of Postfix Expression
Introduction
A data structure defines a mechanism to store, organize and access data along with operations (processing)
that can be efficiently performed on the data.
For example,
• string is a data structure containing a sequence of elements where each element is a character.
• List is a sequence data structure in which each element may be of different types.
We can perform different operations like several, slicing, counting of element etc., Stack and Queue are two
popular data structure used in programming.
Stack
Stack is a linear data structure, where insertion and deletion of an element takes place at same end
commonly referred to as the top of the stack.
The stack follows the last-in-first-out[LIFO] principle where the element which was inserted last will be the
first one to be taken out from stack.
Real-life applications of stack
a. Pile of clothes in an almirah
b. Multiple chairs in a vertical pile
c. Bangles worn on wrist
d. Pile of boxes of eatables in pantry or on a kitchen shelf.
e. Plates arranged one above the other
Application of stack in programming
a. To reverse a string, it is traversed from the last character to the first, reversing their appearance in
the string, which can be done by placing the characters in a stack.
b. The text/image editor allows user to redo/undo editing, with the most recent editing being
redone/undone using a stack to track changes made.
SUNIL D N | KSVK PU COLLEGE
Chapter 3: Stack
c. While browsing the web, we move from one web page to another by accessing links between them.
In order to go back to the last visited web page, we may use the back button on the browser. In this
case, the history of browsed pages is maintained as stack.
d. Expression evaluation
e. Parenthesis checking
f. Function call
g. Backtracking
h. Delimiter checking etc.,
Operations on Stack
Two fundamental operation performed on the stack they are
• PUSH operation
• POP operation
PUSH operation
a. PUSH operation is also called as insertion operation.
b. PUSH adds a new element at the TOP of the stack.
c. We can add elements to a stack until it is full.
d. When stack is full no more element can be added to it.
e. Trying to add an element to a full stack result in an exception called 'overflow'
POP operations
a. POP operation is also called deletion operation.
b. POP delete the existing element from the TOP of the stack.
c. We can delete an element from a stack until it becomes empty.
d. When stack is empty no more deletion can be done.
e. Trying to delete an element from an empty stack result in an exception called underflow.
SUNIL D N | KSVK PU COLLEGE
Chapter 3: Stack
Implementation of stack in python.
Let us write a program to create a STACK glasses.
a. Insert/delete elements (glasses)
b. Check if the STACK is empty (no glasses in the stack)
c. Find the number of elements (glasses) in the STACK.
d. Read the value of the topmost element (number on the topmost glass) in the STACK.
The program shall define the following functions to perform these operations.
a) Let us create an empty stack named glassStack. We will do so by assigning an empty list to the
identifier named glassStack:
glassStack list()
b) A function named is Empty to check whether the stack glassStack is empty or not. Remember trying to
remove an element from an empty stack would result in 'underflow'. This function returns True if the stack
is empty, else returns False.
def isEmpty (glassStack):
if len (glassStack) = =0:
return True
else:
return False
c) A function named opPush to insert (PUSH) a new element in stack. This function has two parameters the
name of the stack in which the element is to be inserted (glassStack) and the element that needs to be
inserted. We know that insertion of an element is always done at the TOP of the stack. Hence, we shall use
the built-in method append() of list to add an element to the stack that always adds at the end of the list.
As there is no limit on the size of list in Python, the implemented stack will never be full unless there is no
more space available in memory. Hence, we will never face 'overflow' (no space for new element) condition
for stack.
def opPush(glass Stack, element):
glassStack.append(element)
d) A function named size to read the number of elements in the glassStack. We will use the len() function of
list in Python to find the number of elements in the glassStack.
def size(glassStack):
return len(glassStack)
e) A function named top to read the most recent element (TOP) in the glassStack.
SUNIL D N | KSVK PU COLLEGE
Chapter 3: Stack
def top(glassStack):
if isEmpty(glassStack):
print('Stack is empty')
return None
else:
x-len(glassStack)
element glassStack[x-1]
return element
A function named opPop to delete the topmost element from the stack. It takes one parameter - the name
of the stack (glassStack) from which element is to be deleted and returns the value of the deleted element.
The function first checks whether the stack is empty or not. If it is not empty, it removes the topmost
element from it. We shall use the built in method pop() of Python list that removes the element from the
end of the list.
def opPop(glassStack):
if isEmpty(glassStack):
print('underflow')
return None
else:
return(glassStack.pop())
g) A function named display to show the contents of the stack.
def display(glassStack):
x=len(glassStack)
print("Current elements in the stack are: ")
for i in range(x-1,-1,-1):
print(glassStack[i])
Python code to implement a stack of glasses.
glassStack = list() # create empty stack
def isEmpty(glassStack):
if len(glassStack)==0:
return True
else:
return False
def opPush(glassStack,element):
glassStack.append(element)
def size(glassStack):
SUNIL D N | KSVK PU COLLEGE
Chapter 3: Stack
return len(glassStack)
def top(glassStack):
if isEmpty(glassStack):
print('Stack is empty')
return None
else:
x =len(glassStack)
element=glassStack[x-1]
return element
def opPop(glassStack):
if isEmpty(glassStack):
print('underflow')
return None
else:
return(glassStack.pop())
def display(glassStack):
x=len(glassStack)
print("Current elements in the stack are: ")
for i in range(x-1,-1,-1):
print(glassStack[i])
#add elements to stack
element='glass1'
print("Pushing element ",element)
opPush(glassStack,element)
element='glass2'
print("Pushing element ",element)
opPush(glassStack,element)
#display number of elements in stack
print("Current number of elements in stack is",size(glassStack))
#delete an element from the stack
element=opPop(glassStack)
print("Popped element is",element)
#add new element to stack
element='glass3'
SUNIL D N | KSVK PU COLLEGE
Chapter 3: Stack
print("Pushing element ",element)
opPush(glassStack,element)
#display the last element added to the stack
print("top element is",top(glassStack))
#display all elements in the stack
display(glassStack)
#delete all elements from stack
while True:
item=opPop(glassStack)
if item == None:
print("Stack is empty now")
break
else:
print("Popped element is",item)
Output:
Pushing element glass1
Pushing element glass2
Current number of elements in stack is 2
Popped element is glass2
Pushing element glass3
top element is glass3
Current elements in the stack are:
glass3
glass1
Popped element is glass3
Popped element is glass1
underflow
Stack is empty now
Notations for Arithmetic expressions
• Arithmetic expressions: Arithmetic expression are written using operators between operands,
evaluated using parentheses (complex expressions, and followed by infix representation and
BODMAS rule.
• Jan Lukasiewicz (Polish mathematician) introduced the Arithmetic expressions.
• Arithmetic expression is also called as Polish notation.
Types of arithmetic expression.
• Infix expression
SUNIL D N | KSVK PU COLLEGE
Chapter 3: Stack
• Prefix expression
• Postfix expression
Infix expression: Operators are placed in between the operands are called infix expression.
Example: z + xy
Prefix expression: The operators are placed before the corresponding operands are called prefix
expression.
Example: +xy
Postfix expression: It is also known as reverse polish notation.
The operators are placed after the corresponding operands are called postfix expression.
Example: xy+
Conversion from Infix to postfix notation
To convert infix expression to postfix expression, use the stack data structure. Scan the infix expression
from left to right. Whenever we get an operand, add it to the postfix expression and if we get an
operator or parenthesis add it to the stack by maintaining their precedence.
Operator Precedence:
• Highest Precedence: Parentheses () (used for grouping and overriding default precedence)
• Unary Operators: +, - (unary plus and minus), ++, --, !, ~
• Multiplication and Division: *, /, %
• Addition and Subtraction: +, -
• Relational Operators: <, >, <=, >=, ==, !=
• Logical Operators: && (AND), || (OR)
• Assignment Operators: =, +=, -=, *=, /=, %=, etc.
Associativity:
• When operators of the same precedence appear in an expression, associativity determines the
order of evaluation.
• Left-to-right associativity means the operations are performed from left to right (e.g., a - b - c is
evaluated as (a - b) - c).
SUNIL D N | KSVK PU COLLEGE
Chapter 3: Stack
• Right-to-left associativity means the operations are performed from right to left (e.g., a = b = c is
evaluated as a = (b = c)).
Conversion of expression from infix to postfix notation
Step 1: Create an empty string named postExp to store the converted postfix expression.
Step 2: INPUT infix expression in a variable, say inExp
Step 3: For each character in inExp, REPEAT Step 4
Step 4: IF character is a left parenthesis THEN PUSH on the Stack
ELSE IF character is a right parenthesis
THEN POP the elements from the Stack and append to string
postExp until the corresponding left parenthesis is popped
while discarding both left and right parentheses
ELSE IF character is an operator
THEN IF its precedence is lower than that of operator at the top of Stack
THEN POP elements from the Stack till an
operator with precedence less than the current
operator is encountered and append to string
postExp before pushing this operator on the postStack
ELSE PUSH operator on the Stack
ELSE Append the character to postExp
Step 5: Pop elements from the Stack and append to postExp until Stack is empty
Step 6: OUTPUT postExp.
Example
Let us now use this algorithm to convert a given infix expression (x + y)/(z*8) into equivalent postfix
expression using a stack.
SUNIL D N | KSVK PU COLLEGE
Chapter 3: Stack
Evaluation of postfix expression
Stacks can be used to evaluate an expression in postfix notation. For simplification, we are assuming that
operators used in expressions are binary operators.
Algorithm 3.2: Evaluation of postfix expression
Step 1: INPUT postfix expression in a variable, say postExp
Step 2: For each character in postExp, REPEAT Step 3
Step 3: IF character is an operand
THEN PUSH character on the Stack
ELSE POP two elements from the Stack, apply the operator on
the popped elements and PUSH the computed value onto the Stack
Step 4: IF Stack has a single element
THEN POP the element and OUTPUT as the net result
ELSE OUTPUT “Invaild Postfix expression”
SUNIL D N | KSVK PU COLLEGE
Chapter 3: Stack
Example
The step-by-step process of evaluation of the postfix expression 7 8 2 * 4 / + using Algorithm.
SUNIL D N | KSVK PU COLLEGE
