STUDENT NOTES || CHAPTER 3 STACKS

CHAPTER 3: STACKS

CHAPTER NOTES

3.1 Intro duction

• Data Structures: Ways to store, organize, and access data efficiently.

• Examples: String, List, Set, Tuple, Array, Linked List, Stack, Queue, Trees, Graphs, etc.
• Stack and Queue are not built-in Python structures but can be implemented using lists.

3.2 Stack

• Definition: A linear data structure where elements are added/removed from one end (TOP).
• LIFO Principle: Last In, First Out – the last element added is the first to be removed.
• Analogy: Stack of plates or books – add/remove only from the top.

3 .2 .1 Applications of Stack

Real-life Scenarios

1. Pile of clothes in an almirah – Clothes are added or removed from the top of the pile, following
the LIFO order.
2. Multiple chairs in a vertical pile – Chairs are stacked one on top of the other, and removed in
reverse order.
3. Bangles worn on the wrist – The last bangle worn is the first to be removed.
4. Boxes of eatables in pantry – Boxes are added and removed from the top for convenience.

Programming Applications
1. String Reversal

• Characters are added to a stack and popped in reverse order to reverse the string.

2. Undo/Redo in Editors

• Each edit (text/image) is pushed onto a stack. Undo removes the last change, redo re-applies
it.
STUDENT NOTES || CHAPTER 3 STACKS

3. Back Function in Web Browsers

• Navigated pages are pushed onto a stack. Pressing ‘Back’ pops the last visited page and
returns to the previous one.

4. Parentheses Matching in Expressions

• During program execution, a stack is used to ensure every opening parenthesis has a matching
closing one. It helps identify syntax errors like unmatched or misnested parentheses.

3.3 Op erations on Stack

• PUSH: Add an element to the TOP of the stack.

• POP: Remove the topmost element.
• Overflow: Trying to PUSH to a full stack (not typically an issue in Python).
• Underflow: Trying to POP from an empty stack.

3.4 Implementation of Stack in Python

Functio ns:
# Create an empty stack
glassStack = list()

# Check if stack is empty

def isEmpty(glassStack):
return len(glassStack) == 0

# PUSH operation
def opPush(glassStack, element):
[Link](element)

# POP operation
def opPop(glassStack):
if isEmpty(glassStack):
print("underflow")
return None
else:
STUDENT NOTES || CHAPTER 3 STACKS

return [Link]()

# Return stack size

def size(glassStack):
return len(glassStack)

# Return top element

def top(glassStack):
if isEmpty(glassStack):
print("Stack is empty")
return None
else:
return glassStack[-1]

# Display all elements (from TOP to bottom)

def display(glassStack):
print("Current elements in the stack are:")
for i in range(len(glassStack)-1, -1, -1):
print(glassStack[i])

Sample Program:
glassStack = list() # create empty stack

element = 'glass1'
print("Pushing element", element)
opPush(glassStack, element)

element = 'glass2'
print("Pushing element", element)
opPush(glassStack, element)

print("Current number of elements in stack is", size(glassStack))

element = opPop(glassStack)
print("Popped element is", element)

element = 'glass3'
print("Pushing element", element)
opPush(glassStack, element)

print("Top element is", top(glassStack))

display(glassStack)
STUDENT NOTES || CHAPTER 3 STACKS

# delete all elements

while True:
item = opPop(glassStack)
if item is None:
break
print("Popped element is", item)

print("Stack is empty now")

3.5 Notations for Arithmetic Expressions

Notation Description Example

Infix Operator between operands (x + y) / (z * 5)

Prefix Operator before operands /+xy*z5
Postfix Operator after operands xy+z5*/

• Prefix (Polish) and Postfix (Reverse Polish) do not require parentheses.

• Infix needs BODMAS and parentheses for clarity.

3.6 Conversion from Infix t o Postfix

Why? Computers struggle with operator precedence in infix; postfix avoids this.

Algorithm 3.1: Infix t o Postfix

1. Create empty string postExp and stack stack.

2. For each character in infix expression:

• If ( → PUSH to stack
• If ) → POP and add to postExp until ( is found
• If operator:
– POP higher or equal precedence operators and append to postExp
STUDENT NOTES || CHAPTER 3 STACKS

– PUSH current operator

• If operand → Append to postExp

3. POP remaining operators to postExp.

Example: ( x + y )/( z * 8 ) → x y + z 8 /

3.7 Evaluation of Postfix Expression

Algorithm 3.2:

1. For each character in postfix expression:

• If operand → PUSH to stack

• If operator → POP two operands, apply operation, PUSH result

2. At the end, if one item in stack → Result

3. Else → Invalid expression

Example: 7 8 2 * 4 / + → Result: 11

Summary Points

• Stack = Linear structure, LIFO principle.

• Core ops: PUSH, POP; special cases: Overflow, Underflow.
• Python list + append() and pop() can simulate stack.
• Notations: Infix, Prefix, Postfix
• Stacks are essential in converting and evaluating arithmetic expressions.

MULTIPLE CHOICE QUESTIONS ( M C Qs )

1. What is the principle followed by a Stack?

A. FIFO
B. LILO
STUDENT NOTES || CHAPTER 3 STACKS

C. LIFO
D. FILO
Answer: C. LIFO

2. In Python, which data type is commonly used to implement a stack?

A. Tuple
B. Set
C. List
D. Dictionary
Answer: C. List

3. What will happen if a POP operation is performed on an empty stack?

A. Overflow
B. Underflow
C. Top Element Removed
D. Nothing Happens
Answer: B. Underflow

4. Which of the following is NOT a real-life example of a stack?

A. Bangles worn on wrist
B. Queue at a movie theatre
C. Pile of books
D. Stack of chairs
Answer: B. Queue at a movie theatre

5. Which method in Python list is used to remove the top element in a stack?
A. remove()
B. del()
C. pop()
D. discard()
Answer: C. pop()
STUDENT NOTES || CHAPTER 3 STACKS

6. In infix expressions, where are the operators placed?

A. After operands
B. Before operands
C. Between operands
D. At the end
Answer: C. Between operands

7. What is postfix notation also known as?

A. Forward Polish
B. Prefix
C. Infix
D. Reverse Polish
Answer: D. Reverse Polish

8. Which function checks if a stack is empty?

A. isEmpty()
B. emptyStack()
C. checkEmpty()
D. None
Answer: A. isEmpty()

9. What type of error occurs when trying to push an element into a full stack (in languages with
fixed stack size)?
A. Syntax Error
B. Runtime Error
C. Overflow
D. Underflow
Answer: C. Overflow
STUDENT NOTES || CHAPTER 3 STACKS

10. What would be the result of evaluating the postfix expression: 7 8 2 * 4 / +?

A. 15
B. 11
C. 14
D. 10
Answer: B. 11

11. Which operator has the highest precedence in arithmetic expressions?

A. +
B. -
C. *
D. =
Answer: C. *

12. In the conversion of infix to postfix, where are the operators stored during processing?
A. Queue
B. List
C. Stack
D. Array
Answer: C. Stack

13. Which function is used to read the topmost element from the stack?
A. pop()
B. top()
C. peek()
D. get()
Answer: B. top()

14. What is the output of the top() function when the stack is empty?
A. 0
STUDENT NOTES || CHAPTER 3 STACKS

B. Error
C. None
D. Null
Answer: C. None

15. What is the postfix equivalent of the infix expression (x + y)/(z * 8)?
A. xy+z8/
B. +xyz8/
C. /+xyz8
D. x+yz/8
**Answer: A. xy+z8*/**

16. Which of the following is a valid use of stack in text/image editors?

A. Spell check
B. Redo/Undo
C. Save file
D. Crop image
Answer: B. Redo/Undo

17. Which stack operation returns the number of elements?

A. size()
B. length()
C. count()
D. getSize()
Answer: A. size()

18. During infix to postfix conversion, what happens when a right parenthesis is encountered?
A. It is ignored
B. It is pushed to stack
C. Operators are popped till left parenthesis
D. Nothing happens
Answer: C. Operators are popped till left parenthesis
STUDENT NOTES || CHAPTER 3 STACKS

19. Which one of the following statements is FALSE about stack operations in Python (based on
the chapter)?
A. append() is used to push elements
B. pop() removes the topmost element
C. We declare stack size in Python
D. Stack can be implemented using list
Answer: C. We declare stack size in Python

20. What is the postfix expression equivalent of: A * ((C + D) / E)?

A. ACD+E/*
B. AC+DE/
C. ACD+E/
D. AC+D/E*
Answer: A. ACD+E/
[Link] (A): Stack is a linear data structure that follows Last-In-First-Out (LIFO) order.
Reason (R): In a stack, insertion and deletion happen at the same end known as TOP.
A. Both A and R are true, and R is the correct explanation of A
B. Both A and R are true, but R is not the correct explanation of A
C. A is true, but R is false
D. A is false, but R is true
Answer: A

[Link] (A): The pop() method in Python list implementation of a stack removes the first element.
Reason (R): In stack implementation, elements are always inserted and removed from the beginning of the
list.
A. Both A and R are true, and R is the correct explanation of A
B. Both A and R are true, but R is not the correct explanation of A
C. A is true, but R is false
D. A is false, but R is true
Answer: D
STUDENT NOTES || CHAPTER 3 STACKS

[Link] (A): Stack is a useful data structure for reversing a string.

Reason (R): Stack allows deletion of elements from the bottom, enabling reverse traversal.
A. Both A and R are true, and R is the correct explanation of A
B. Both A and R are true, but R is not the correct explanation of A
C. A is true, but R is false
D. A is false, but R is true
Answer: C

[Link] (A): A stack is used for matching parentheses in expressions.

Reason (R): Stack helps in storing and retrieving nested structures in reverse order.
A. Both A and R are true, and R is the correct explanation of A
B. Both A and R are true, but R is not the correct explanation of A
C. A is true, but R is false
D. A is false, but R is true
Answer: A

[Link] (A): Overflow condition occurs when an element is inserted into a full stack in Python.
Reason (R): Python lists have a fixed size and cannot grow beyond a limit.
A. Both A and R are true, and R is the correct explanation of A
B. Both A and R are true, but R is not the correct explanation of A
C. A is true, but R is false
D. A is false, but R is true
Answer: C

[Link] (A): Infix expressions are easy for humans to read but difficult for machines to evaluate.
Reason (R): Infix expressions require knowledge of operator precedence and parentheses handling.
STUDENT NOTES || CHAPTER 3 STACKS

A. Both A and R are true, and R is the correct explanation of A

B. Both A and R are true, but R is not the correct explanation of A
C. A is true, but R is false
D. A is false, but R is true
Answer: A

[Link] (A): In postfix notation, parentheses are not required.

Reason (R): Postfix notation places operators in a way that respects operator precedence inherently.
A. Both A and R are true, and R is the correct explanation of A
B. Both A and R are true, but R is not the correct explanation of A
C. A is true, but R is false
D. A is false, but R is true
Answer: A

[Link] (A): While converting an infix expression to postfix, operands are pushed onto the stack.
Reason (R): The stack is used to hold operands and not operators.
A. Both A and R are true, and R is the correct explanation of A
B. Both A and R are true, but R is not the correct explanation of A
C. A is true, but R is false
D. A is false, but R is true
Answer: C

[Link] (A): In evaluation of postfix expression, operators are pushed onto the stack.
Reason (R): Stack helps evaluate binary operators from left to right.
A. Both A and R are true, and R is the correct explanation of A
B. Both A and R are true, but R is not the correct explanation of A
C. A is true, but R is false
D. A is false, but R is true
Answer: D
STUDENT NOTES || CHAPTER 3 STACKS

[Link] (A): Stack is a helpful structure in browser history navigation.

Reason (R): The back button uses LIFO mechanism to navigate to the previous pages.

A. Both A and R are true, and R is the correct explanation of A

B. Both A and R are true, but R is not the correct explanation of A
C. A is true, but R is false
D. A is false, but R is true
Answer: A

FILL IN THE BLANKS

1. A ______ is a linear data structure in which insertion and deletion are done from the same end.
Answer: Stack

2. Stack follows the ______ principle, where the last element added is the first one removed.
Answer: LIFO (Last-In-First-Out)

3. In Python, a stack can be implemented using the ______ data type.

Answer: list

4. The operation to insert an element into a stack is called ______.

Answer: PUSH

5. The operation to remove the topmost element from a stack is called ______.
Answer: POP

6. Attempting to remove an element from an empty stack leads to ______ condition.

Answer: Underflow

7. In stack implementation using Python list, elements are added using the ______ method.
Answer: append()

8. The ______ function in stack returns the number of elements present.

Answer: size

9. The ______ function retrieves the most recently added element without removing it.
Answer: top

10. The postfix expression of (x + y)/(z * 8) is ______.

Answer: xy+z8*/
STUDENT NOTES || CHAPTER 3 STACKS

11. Infix notation places operators ______ the operands.

Answer: between

12. Postfix notation is also called ______ notation.

Answer: Reverse Polish

13. During infix to postfix conversion, only ______ are pushed onto the stack.
Answer: operators

14. In evaluation of postfix expression, only ______ are pushed onto the stack.
Answer: operands

15. The isEmpty() function returns ______ if the stack contains no elements.
Answer: True

2 MARKS QUESTIONS

1. Q: Define Stack. Mention the principle it follows.

A:
A stack is a linear data structure where elements are added and removed from the same end, called the
TOP. It follows the LIFO (Last-In-First-Out) principle, meaning the last inserted element is the first
one to be removed.

2. Q: Differentiate between PUSH and POP operations.

A:
- PUSH: Adds a new element at the TOP of the stack (insertion).
- POP: Removes the topmost element from the stack (deletion).
PUSH may lead to overflow if the stack is full, while POP may cause underflow if the stack is empty.

3. Q: Write the syntax and an example of the PUSH operation in Python.

A:
Syntax: [Link](element)
Example:

glassStack = []
[Link]('glass1')

4. Q: What is underflow? When does it occur in stack operations?

A:
Underflow is a condition where an element is attempted to be removed (POP) from an empty stack. It
results in an exception because there are no elements to delete.
STUDENT NOTES || CHAPTER 3 STACKS

5. Q: Differentiate between Infix and Postfix notation with one example each.
A:
- Infix: Operators are placed between operands. Example: (x + y)/(z * 5)
- Postfix: Operators are placed after operands. Example: xy+z5*/

6. Q: Write any two real-life applications of stack.

A:
1. Undo/Redo functionality in text or image editors.
2. Back button in a web browser, which stores visited pages in LIFO order.

7. Q: Write the function in Python to check if a stack is empty.

A:

def isEmpty(glassStack):
if len(glassStack) == 0:
return True
else:
return False

8. Q: Write the postfix expression for (x + y)/(z * 8)

A:
The postfix expression for (x + y)/(z * 8) is: xy+z8*/

9. Q: What are the steps to evaluate a postfix expression using a stack?

A:
- For each character in the postfix expression:
- If operand, PUSH onto stack.
- If operator, POP two elements, apply the operator, and PUSH the result.
- Final result is the only element left in the stack.

10. Q: Distinguish between Overflow and Underflow in the context of stacks.

A:
- Overflow occurs when an element is inserted into a full stack.
- Underflow occurs when an element is removed from an empty stack.
Python’s dynamic lists usually prevent overflow unless memory is exhausted.

3 MARKS QUESTIONS

1. Q: Explain the applications of stack in programming with any three examples.

A:Applications of stack in programming include:
STUDENT NOTES || CHAPTER 3 STACKS

1. Reversing a String: By pushing all characters onto a stack and then popping them, the string is
reversed.
2. Undo/Redo Operations: In text/image editors, changes are pushed onto a stack. Undo pops the
last action, and redo re-applies it.
3. Parentheses Matching: Compilers use stacks to ensure that every opening parenthesis has a match-
ing closing one and is properly nested.

2. Q: Differentiate between Infix, Prefix, and Postfix notation. Provide one example for each.
A:
Infix :- Operator between operands. Example: (x + y) / (z * 5)
Prefix :- Operator before operands (Polish notation) . example: /+xy*z5
Postfix :-Operator after operands (Reverse Polish) . example:-| xy+z5*/

3. Q: Write a Python function to display the elements of a stack from top to bottom. Also, explain
what it does.
A:

def display(glassStack):
x = len(glassStack)
print("Current elements in the stack are: ")
for i in range(x-1, -1, -1):
print(glassStack[i])

Explanation:
The display() function prints the contents of the stack glassStack from the top element to the bot-
tom, using reverse indexing.

4. Q: Explain the steps involved in converting an infix expression to a postfix expression using
stack.
A:
Steps for conversion: 1. Traverse each character in the infix expression.
2. If it’s an operand, append it to the postfix string.
3. If it’s a left parenthesis (, push to the stack.
4. If it’s a right parenthesis ), pop and append operators until a matching ( is found.
5. If it’s an operator, pop higher precedence operators from the stack and append to postfix, then push
the current operator.
6. After processing all characters, pop remaining stack contents to postfix expression.

5. Q: What is the role of a stack in evaluating a postfix expression? Explain the process with steps.
A:
To evaluate a postfix expression using stack:
1. Read the postfix expression left to right.
2. If an operand is encountered, push it onto the stack.
3. If an operator is encountered, pop two elements, apply the operator, and push the result back.
4. After processing, the final result will be the only value remaining in the stack.
STUDENT NOTES || CHAPTER 3 STACKS

6. Q: What will be the output of the following code segment? Explain each step.

answer=[]; output=''
[Link]('T')
[Link]('A')
[Link]('M')
ch=[Link]()
output=output+ch
ch=[Link]()
output=output+ch
ch=[Link]()
output=output+ch
print("Result=",output)

A:
Output: Result=MAT

Explanation: - Stack: T → A → M
- POP 1: ‘M’ → output = “M”
- POP 2: ‘A’ → output = “MA”
- POP 3: ‘T’ → output = “MAT”

7. Q: Write Python functions opPush() and opPop() used in stack operations. Explain how they
work.
A:

def opPush(glassStack, element):

[Link](element)

def opPop(glassStack):
if isEmpty(glassStack):
print("underflow")
return None
else:
return [Link]()

Explanation:
- opPush() uses append() to add elements to the TOP of the stack.
- opPop() checks if the stack is empty before using pop() to remove the top element.

8. Q: Differentiate between overflow and underflow in stack operations. How does Python handle
these conditions?
A:
- Overflow: Occurs when trying to PUSH into a full stack. In Python, this is rare because lists are dynamic.
STUDENT NOTES || CHAPTER 3 STACKS

- Underflow: Occurs when trying to POP from an empty stack. Python raises an error or custom message
when this is handled.
- Python handles underflow using conditional checks (isEmpty()), and overflow is not typical due to
dynamic memory allocation.

5 MARKS QUETIONS

1. Q: What is a stack? Explain its structure, principle, and real-life examples.

A:
A stack is a linear data structure in which insertion and deletion take place at one end, called the TOP.
It follows the Last-In-First-Out (LIFO) principle.
Real-life examples:
- Pile of clothes in an almirah
- Stack of plates or books
- Bangles on the wrist
- Chairs stacked vertically
In all these, the last item placed is the first to be removed.

2. Q: Explain the PUSH and POP operations in a stack. Give Python functions for both.
A:
- PUSH: Adds a new element at the top of the stack . It is an insertion operation.
- POP: Removes the topmost element from the stack. It is a delete operation
Python implementation:

PUSH operation:
def opPush(glassStack, element):
[Link](element)

POP operation:
def opPop(glassStack):
if isEmpty(glassStack):
print("underflow")
return None
else:
return [Link]()

These functions use append() to push and pop() to pop elements from a Python list used as a stack.

3. Q: Differentiate between Infix, Prefix, and Postfix notations. Give one example of each.
A:
Infix :- Operator between operands.
• Infix is commonly used by humans and evaluated using BODMAS rule.
Example:(x + y) / (z * 5)
Prefix :- Operator before operands (Polish)
Example: /+xy*z5
STUDENT NOTES || CHAPTER 3 STACKS

Postfix :- Operator after operands (Reverse Polish)

Example:- xy+z5*/

• Prefix/Postfix eliminate the need for parentheses.

4. Q: Describe five applications of stack in real-life or programming contexts.

A:
1. Undo/Redo in Editors: Recent changes are pushed; undo pops last action.
2. String Reversal: Characters pushed then popped in reverse order.
3. Web Browser Back Button: Maintains history as stack; back pops last page.
4. Matching Parentheses: Stack stores opening brackets; ensures matching.
5. Function Call Management: In compiled languages, stack maintains function calls.
5. Q: Write a Python program to create a stack, push and pop elements, and display the topmost
element.
A:

glassStack = list()

opPush(glassStack, 'glass1')
opPush(glassStack, 'glass2')
print("Top element is:", top(glassStack))

element = opPop(glassStack)
print("Popped element is:", element)

opPush(glassStack, 'glass3')
display(glassStack)

This demonstrates pushing, popping, and reading the topmost element using stack operations.
6. Q: What are overflow and underflow in the context of stacks? How are these handled in Python?
A:
- Overflow: Occurs when trying to push into a full stack (not typical in Python).
- Underflow: Occurs when trying to pop from an empty stack.
Python handles underflow using checks like:

if isEmpty(stack): print("underflow")

Overflow is rare in Python due to dynamic list size.

7. Q: Explain the process of converting an infix expression to a postfix expression. Provide the
algorithm.
A:
Algorithm (In brief): 1. Initialize an empty string postExp and a stack.
2. Traverse each character of infix expression.
3. If operand → append to postExp.
4. If ( → push to stack.
5. If ) → pop
STUDENT NOTES || CHAPTER 3 STACKS

to postExp until ( is found.

6. If operator → pop higher precedence operators to postExp, then push current.
7. After traversal, pop remaining stack contents to postExp.
8. Q: Convert the infix expression (x + y)/(z * 8) into postfix using stack and show steps.
A:
Given infix: (x + y)/(z * 8)
Steps: - Push (
- Append x, then y
- Operator + pushed, then popped after ) → xy+
- Operator / pushed
- Push (, then z, 8
- Operator * pushed, then popped after ) → z8*
- / popped → Final: xy+z8*/
9. Q: Describe the algorithm for evaluating a postfix expression using stack.
A:
Algorithm: 1. Read the postfix expression left to right.
2. If operand → push to stack.
3. If operator → pop two elements, apply operator, push result.
4. Final element in stack = result.
10. Q: Evaluate the postfix expression 7 8 2 * 4 / + using stack and show stack state after each
step.
A:
Expression: 7 8 2 * 4 / +
Steps: - Push 7 → [7]
- Push 8 → [7, 8]
- Push 2 → [7, 8, 2]
- * → 8 * 2 = 16 → [7, 16]
- Push 4 → [7, 16, 4]
- / → 16 / 4 = 4 → [7, 4]
- + → 7 + 4 = 11 → [11]
Result: 11
11. Q: Write the Python function top() to retrieve the topmost element in a stack with empty
check.
A:

def top(glassStack):
if isEmpty(glassStack):
print("Stack is empty")
return None
else:
return glassStack[-1]
STUDENT NOTES || CHAPTER 3 STACKS

It returns the last element in the list, which is the top of the stack.

12. Q: Explain the display() function used to print stack contents in Python. Provide code and
output format.
A:

def display(glassStack):
x = len(glassStack)
print("Current elements in the stack are:")
for i in range(x-1, -1, -1):
print(glassStack[i])

Prints from the top (last inserted) to bottom of stack.

13. Q: Write a program to reverse a string using stack.

A:

def reverseString(s):
stack = []
for char in s:
[Link](char)
rev = ''
while stack:
rev += [Link]()
return rev

print(reverseString("STACK"))

Output: KCATS

14. Q: Convert the infix expression A + B - C * D to postfix and show stack/string at each step.
A:
Steps: - Append A → A
- + → push
- Append B → AB
- - → pop + → AB+, push --
Append C → AB+C
- * → push
- Append D → AB+CD
- Pop * then - → AB+CD*-

Final postfix: AB+CD*-

15. Q: Write a program to store only odd numbers in a stack from user input and display largest
odd number.
STUDENT NOTES || CHAPTER 3 STACKS

A:

stack = []
nums = [1, 2, 9, 4, 7, 10]
for n in nums:
if n % 2 != 0:
[Link](n)

maxOdd = float('-inf')
while stack:
ele = [Link]()
print("Popped:", ele)
if ele > maxOdd:
maxOdd = ele

print("Largest odd number:", maxOdd)

16. Q: Explain the step-by-step use of stack in parentheses matching. Give an example.
A:
In expression: ((2+3)*(4/2))+2
Steps: - Push ( → Stack: [(]
- Push another ( → Stack: [(, (]
- Read 2, +, 3 → skip
- ) → pop one ( → Stack: [(]
- *, then ( → push → Stack: [(, (]
- Read 4, /, 2
- ) → pop ( → Stack: [(]
- ) → pop ( → Stack: []
If stack is empty at end and no mismatches → Valid.

17. Q: Give a step-by-step evaluation of the postfix expression: A B + C * where A=3, B=5, C=1.
A:
- A = 3, B = 5, C = 1
Expression: 3 5 + 1 *
- 3, 5 → push
- + → 3+5 = 8
- push 1
-*→8*1=8
Result: 8
STUDENT NOTES || CHAPTER 3 STACKS

CHAPTER END EXERCISES

1. State TRUE or FALSE for the following cases:

a) Stack is a linear data structure

b) Stack does not follow LIFO rule

c) PUSH operation may result into underflow condition

d) In POSTFIX notation for expression, operators are placed after operands

Answers:
a) True
b) False
c) False
d) True

2. Find the output of the following code:

a)

result = 0
numberList = [10, 20, 30]
[Link](40)
result = result + [Link]()
result = result + [Link]()
print("Result =", result)

Output:

Result = 70

Explanation:
- Stack after append: [10, 20, 30, 40]
- POP 1: 40 → result = 0 + 40 = 40
- POP 2: 30 → result = 40 + 30 = 70

b)

answer = []; output = ''

[Link]('T')
[Link]('A')
[Link]('M')
STUDENT NOTES || CHAPTER 3 STACKS

ch = [Link]()
output = output + ch
ch = [Link]()
output = output + ch
ch = [Link]()
output = output + ch
print("Result =", output)

Output:

Result = MAT

Explanation:
- Stack after pushes: [‘T’, ‘A’, ‘M’]
- Popped characters: ‘M’, ‘A’, ‘T’ → added to output in reverse

3. Write a program to reverse a string using stack.

Answer:

def reverseString(s):
stack = []
for char in s:
[Link](char)
rev = ''
while stack:
rev += [Link]()
return rev

print(reverseString("STACK"))

Output:

KCATS

4. For the following arithmetic expression:

((2 + 3) * (4 / 2)) + 2
Show step-by-step process for matching parentheses using stack.

Answer (Steps): 1. Encounter ( → push

2. Another ( → push
STUDENT NOTES || CHAPTER 3 STACKS

3. Process 2 + 3, then ) → pop (

4. Encounter *, then ( → push
5. Process 4 / 2, then ) → pop (
6. Then outer ) → pop (

Conclusion:
All parentheses matched and stack is empty at end → Parentheses are properly nested and matched.

5. Evaluate following postfix expressions (A=3, B=5, C=1, D=4)

a) A B + C * → 3 5 + 1 *
Answer:

• 3+5=8

• 8*1=8

b) A B * C / D * → 3 5 * 1 / 4 *
Answer:

• 3 * 5 = 15

• 15 / 1 = 15

• 15 * 4 = 60

6. Convert the following infix notations to postfix notations. Show stack and string contents at each
step.

a) A + B - C * D
Postfix: AB+CD*-

b) A * ((C + D)/E)
Postfix: ACD+E/*

7. 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.
Answer:
STUDENT NOTES || CHAPTER 3 STACKS

numbers = [1, 2, 9, 4, 7, 10]

stack = []

for num in numbers:

if num % 2 != 0:
[Link](num)

largest = float('-inf')
print("Odd numbers in stack:")
while stack:
item = [Link]()
print(item)
if item > largest:
largest = item

print("Largest odd number:", largest)

Sample Output:

Odd numbers in stack:

7
9
1
Largest odd number: 9