Python Stack: Understanding the LIFO Data Structure and its Implementation in Python

In computer science, a stack is an abstract data type that serves as a collection of elements, with two main operations: push and pop. The push operation adds an element to the top of the stack, while the pop operation removes the element from the top of the stack. The elements are stored in a Last-In-First-Out (LIFO) manner, meaning that the last element added to the stack is the first one to be removed.

In Python, a list can be used to implement a stack by using append to simulate the push operation and pop to simulate the pop operation.

Table of Contents

The (CBSE) NCERT Computer Science Python Class XII Chapter 2: Stack provides a comprehensive understanding of the Stack data structure and its implementation in Python. The chapter covers various important concepts such as infix and postfix expressions, evaluation of postfix expressions using Stack, and implementation of Stack to store only odd numbers.

It includes a wide range of questions, answers, and solutions to help students grasp the concepts effectively and apply them in real-life situations. The chapter is designed to provide hands-on experience and a strong foundation in the Stack data structure, making it an important resource for students preparing for their exams.

State TRUE or FALSE for the following cases:

Stack is a linear data structure: TRUE
Stack does not follow LIFO rule: FALSE
PUSH operation may result into underflow condition: TRUE
In POSTFIX notation for expression, operators are placed after operands: TRUE

Find the output of the following code

result=0
numberList=[10,20,30]
numberList.append(40)
result=result+numberList.pop()
result=result+numberList.pop()
print(“Result=”,result)

result=0

numberList=[10,20,30]

numberList.append(40)

result=result+numberList.pop()

print(“Result=”,result)

The output of the code will be:

Result= 70

1	Result= 70

answer=[]; output=''
answer.append('T')
answer.append('A')
answer.append('M')
ch=answer.pop()
output=output+ch
ch=answer.pop()
output=output+ch
ch=answer.pop()
output=output+ch
print(“Result=”,output)

answer=[]; output=''

answer.append('T')

answer.append('A')

answer.append('M')

ch=answer.pop()

output=output+ch

ch=answer.pop()

output=output+ch

ch=answer.pop()

output=output+ch

print(“Result=”,output)

The output of the code will be:

Result= MAT

1	Result= MAT

Write a program to reverse a string using stack

The code creates an empty stack, pushes each character from the input string onto the stack, and then pops each character from the stack to form the reversed string.

def reverse_string(input_string):
    stack = []
    for char in input_string:
        stack.append(char)
    output = ""
    while stack:
        output += stack.pop()
    return output

input_string = "Hello, World!"
print("Original string:", input_string)
print("Reversed string:", reverse_string(input_string))

def reverse_string(input_string):

stack = []

for char in input_string:

stack.append(char)

output = ""

while stack:

output += stack.pop()

return output

input_string = "Hello, World!"

print("Original string:", input_string)

print("Reversed string:", reverse_string(input_string))

This code will produce the following output:

Original string: Hello, World!
Reversed string: !dlroW ,olleH

1 2	Original string: Hello, World! Reversed string: !dlroW ,olleH

For the following arithmetic expression: ((2+3)*(4/2))+2

Here’s a step-by-step process to match parentheses using a stack data structure in Python:

Initialize an empty stack.
Iterate through the expression, character by character.
For each opening parenthesis, push it onto the stack.
For each closing parenthesis, pop the top element from the stack. If the popped element is not the corresponding opening parenthesis, there is a mismatch, and the expression is invalid.
If the stack is not empty after processing all the characters, there is a mismatch, and the expression is invalid.
If the stack is empty, the parentheses in the expression are properly matched.

Here’s an implementation in Python:

def match_parentheses(expression):
    stack = []
    for char in expression:
        if char == '(':
            stack.append(char)
        elif char == ')':
            if not stack:
                return False
            if stack[-1] != '(':
                return False
            stack.pop()
    return not stack

expression = "((2+3)*(4/2))+2"
result = match_parentheses(expression)
if result:
    print("Parentheses are properly matched.")
else:
    print("Parentheses are NOT properly matched.")

def match_parentheses(expression):

stack = []

for char in expression:

if char == '(':

stack.append(char)

elif char == ')':

if not stack:

return False

if stack[-1] != '(':

return False

stack.pop()

return not stack

expression = "((2+3)*(4/2))+2"

result = match_parentheses(expression)

if result:

print("Parentheses are properly matched.")

else:

print("Parentheses are NOT properly matched.")

This code outputs:

Parentheses are properly matched.

1	Parentheses are properly matched.

In Python, you can use the eval() function to evaluate an arithmetic expression:

expression = "((2+3)*(4/2))+2"
result = eval(expression)
print("Result:", result)

expression = "((2+3)*(4/2))+2"

result = eval(expression)

print("Result:", result)

This will output:

Result: 12.0

1	Result: 12.0

Whereas, in Mathematics this expression can be evaluated as follows:

Perform the operation inside the innermost parentheses first: 4/2 = 2.
Replace the expression (4/2) with its result, 2: ((2+3)*2)+2.
Perform the next set of parentheses: (2+3) = 5.
Replace the expression (2+3) with its result, 5: (5*2)+2.
Perform the next operation: 5*2 = 10.
Replace the expression (5*2) with its result, 10: 10+2.
Perform the final operation: 10+2 = 12.

So the expression ((2+3)*(4/2))+2 evaluates to 12.

Evaluate following postfix expressions while showing status of stack after each operation given

A=3, B=5,
C=1, D=4
a) A B + C *
b) A B * C / D *

A=3, B=5,

C=1, D=4

a) A B + C *

b) A B * C / D *

Postfix expressions while showing status of stack after each operation

a) A B + C *
Step 1: Push 3 onto the stack (stack = [3])
Step 2: Push 5 onto the stack (stack = [3, 5])
Step 3: Perform the operation +, pop two operands (5 and 3) from the stack, add them and push the result (8) back onto the stack (stack = [8])
Step 4: Push 1 onto the stack (stack = [8, 1])
Step 5: Perform the operation *, pop two operands (1 and 8) from the stack, multiply them and push the result (8) back onto the stack (stack = [8])
Result: The final value in the stack is 8, which is the answer.

b) A B * C / D *
Step 1: Push 3 onto the stack (stack = [3])
Step 2: Push 5 onto the stack (stack = [3, 5])
Step 3: Perform the operation *, pop two operands (5 and 3) from the stack, multiply them and push the result (15) back onto the stack (stack = [15])
Step 4: Push 1 onto the stack (stack = [15, 1])
Step 5: Push 4 onto the stack (stack = [15, 1, 4])
Step 6: Perform the operation /, pop two operands (4 and 1) from the stack, divide them and push the result (4) back onto the stack (stack = [15, 4])
Step 7: Perform the operation *, pop two operands (4 and 15) from the stack, multiply them and push the result (60) back onto the stack (stack = [60])
Result: The final value in the stack is 60, which is the answer.

a) A B + C *

Step 1: Push 3 onto the stack (stack = [3])

Step 2: Push 5 onto the stack (stack = [3, 5])

Step 3: Perform the operation +, pop two operands (5 and 3) from the stack, add them and push the result (8) back onto the stack (stack = [8])

Step 4: Push 1 onto the stack (stack = [8, 1])

Step 5: Perform the operation *, pop two operands (1 and 8) from the stack, multiply them and push the result (8) back onto the stack (stack = [8])

Result: The final value in the stack is 8, which is the answer.

b) A B * C / D *

Step 1: Push 3 onto the stack (stack = [3])

Step 2: Push 5 onto the stack (stack = [3, 5])

Step 3: Perform the operation *, pop two operands (5 and 3) from the stack, multiply them and push the result (15) back onto the stack (stack = [15])

Step 4: Push 1 onto the stack (stack = [15, 1])

Step 5: Push 4 onto the stack (stack = [15, 1, 4])

Step 6: Perform the operation /, pop two operands (4 and 1) from the stack, divide them and push the result (4) back onto the stack (stack = [15, 4])

Step 7: Perform the operation *, pop two operands (4 and 15) from the stack, multiply them and push the result (60) back onto the stack (stack = [60])

Result: The final value in the stack is 60, which is the answer.

Here is the implementation in Python:

class Stack:
def init(self):
self.items = []

class Stack:

def init(self):

self.items = []

def push(self, item):
    self.items.append(item)

def pop(self):
    return self.items.pop()

def is_empty(self):
    return self.items == []

def push(self, item):

self.items.append(item)

def pop(self):

return self.items.pop()

def is_empty(self):

return self.items == []

def postfix_eval(expression):
stack = Stack()
for char in expression:
if char in '0123456789':
stack.push(int(char))
else:
operand2 = stack.pop()
operand1 = stack.pop()
if char == '+':
result = operand1 + operand2
elif char == '-':
result = operand1 - operand2
elif char == '*':
result = operand1 * operand2
elif char == '/':
result = operand1 / operand2
stack.push(result)
return stack.pop()

A = 3
B = 5
C = 1
D = 4

expression1 = 'AB+C*'
expression2 = 'ABC/D'

print(postfix_eval(expression1))
print(postfix_eval(expression2))

def postfix_eval(expression):

stack = Stack()

for char in expression:

if char in '0123456789':

stack.push(int(char))

else:

operand2 = stack.pop()

operand1 = stack.pop()

if char == '+':

result = operand1 + operand2

elif char == '-':

result = operand1 - operand2

elif char == '*':

result = operand1 * operand2

elif char == '/':

result = operand1 / operand2

stack.push(result)

return stack.pop()

A = 3

B = 5

C = 1

D = 4

expression1 = 'AB+C*'

expression2 = 'ABC/D'

print(postfix_eval(expression1))

print(postfix_eval(expression2))

Convert the following infix notations to postfix notations, showing stack and string contents at each step.

A + B – C * D
A * (( C + D)/E)

Here is the step-by-step process to convert the following infix notations to postfix notations:

a) A + B – C * D

Step 1: Initialize an empty stack and empty string. Stack: [ ] String: [ ]
Step 2: Scan the infix expression from left to right.
Step 3: If the character is an operand (A, B, C, or D), add it to the string. Stack: [ ] String: [A]
Step 4: If the character is an operator (+), push it onto the stack. Stack: [+] String: [A]
Step 5: If the character is an operand (B), add it to the string. Stack: [+] String: [A B]
Step 6: If the character is an operator (-), push it onto the stack. Stack: [+ -] String: [A B]
Step 7: If the character is an operand (C), add it to the string. Stack: [+ -] String: [A B C]
Step 8: If the character is an operator (*), push it onto the stack. Stack: [+ – *] String: [A B C]
Step 9: If the character is an operand (D), add it to the string. Stack: [+ – *] String: [A B C D]
Step 10: Repeat Steps 3 to 9 until the end of the infix expression.
Step 11: If the stack is not empty, pop the operators from the stack and add them to the string. Stack: [ ] String: [A B C D * – +]
The postfix expression is A B C D * – +

b) A * ((C + D)/E)

Step 1: Initialize an empty stack and empty string. Stack: [ ] String: [ ]
Step 2: Scan the infix expression from left to right.
Step 3: If the character is an operand (A), add it to the string. Stack: [ ] String: [A]
Step 4: If the character is an operator (), push it onto the stack. Stack: [ ] String: [A]
Step 5: If the character is an opening parenthesis, push it onto the stack. Stack: [* ( ] String: [A]
Step 6: If the character is an operand (C), add it to the string. Stack: [* ( ] String: [A C]
Step 7: If the character is an operator (+), push it onto the stack. Stack: [* ( + ] String: [A C]
Step 8: If the character is an operand (D), add it to the string. Stack: [* ( + ] String: [A C D]
Step 9: If the character is a closing parenthesis, pop the operators from the stack and add them to the string until an opening parenthesis is encountered. Stack: [* ( ] String: [A C D +]
Step 10: If the character is an operator (/), push it onto the stack. Stack: [* ( / ] String: [A C D +]
Step 11: If the character is an operand (E), add it to the string. Stack: [* ( / ] String: [A C D + E]
Step 12: Repeat Steps 3

Write a program to create a Stack for storing only odd numbers out of all the numbers entered by the user. Display the content of the Stack along with the largest odd number in the Stack. (Hint. Keep popping out the elements from stack and maintain the largest element retrieved so far in a variable. Repeat till Stack is empty

class Stack:
    def __init__(self):
        self.items = []
    def push(self, item):
        if item % 2 != 0:
            self.items.append(item)
    def pop(self):
        return self.items.pop()
    def is_empty(self):
        return self.items == []
    def display(self):
        return self.items

stack = Stack()
while True:
    num = int(input("Enter a number: "))
    if num == 0:
        break
    stack.push(num)

largest_odd = 0
while not stack.is_empty():
    num = stack.pop()
    if num > largest_odd:
        largest_odd = num
print("Content of the stack: ", stack.display())
print("Largest odd number: ", largest_odd)

class Stack:

def __init__(self):

self.items = []

def push(self, item):

if item % 2 != 0:

self.items.append(item)

def pop(self):

return self.items.pop()

def is_empty(self):

return self.items == []

def display(self):

return self.items

stack = Stack()

while True:

num = int(input("Enter a number: "))

if num == 0:

break

stack.push(num)

largest_odd = 0

while not stack.is_empty():

num = stack.pop()

if num > largest_odd:

largest_odd = num

print("Content of the stack: ", stack.display())

print("Largest odd number: ", largest_odd)

Python Stack: Understanding the LIFO Data Structure and its Implementation in Python

In Python, a stack is a collection of elements with push and pop operations, stored in LIFO order. A list can implement a stack using append and pop.

State TRUE or FALSE for the following cases:

Find the output of the following code

Write a program to reverse a string using stack

For the following arithmetic expression: ((2+3)*(4/2))+2

Evaluate following postfix expressions while showing status of stack after each operation given

Convert the following infix notations to postfix notations, showing stack and string contents at each step.

File Handling in Python

PM Modi Expresses Empathy for Turkey, Recalls 2001 Bhuj Earthquake

You may also like

Leave a Comment