*165*

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.

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

a)

1 2 3 4 5 6 | result=0 numberList=[10,20,30] numberList.append(40) result=result+numberList.pop() result=result+numberList.pop() print(“Result=”,result) |

**The output of the code will be:**

1 | Result= 70 |

b)

1 2 3 4 5 6 7 8 9 10 11 | 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:

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.

1 2 3 4 5 6 7 8 9 10 11 12 | 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:**

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:**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | 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:**

1 | Parentheses are properly matched. |

In Python, you can use the

`eval()`

function to evaluate an arithmetic expression:1 2 3 | expression = "((2+3)*(4/2))+2" result = eval(expression) print("Result:", result) |

**This will output:**

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

1 2 3 4 | 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**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | 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:**

1 2 3 | class Stack: def init(self): self.items = [] |

1 2 3 4 5 6 7 8 | def push(self, item): self.items.append(item) def pop(self): return self.items.pop() def is_empty(self): return self.items == [] |

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | 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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | 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) |