Stack

Given: Statements about Stack data structure.

Concept: Recall the fundamental properties of Stack.

a) TRUE — Stack stores elements in a linear (sequential) order; elements are arranged one after another.

b) FALSE — Stack strictly follows the LIFO (Last-In-First-Out) principle, meaning the last inserted element is the first to be removed.

c) FALSE — PUSH operation inserts an element onto the stack. It may result in overflow (when the stack is full), NOT underflow. Underflow occurs during the POP operation when the stack is empty.

d) TRUE — In POSTFIX (Reverse Polish) notation, operators are placed after their operands. For example, $A + B$ in infix becomes $AB+$ in postfix.

Given: Python code using a list as a stack.

Concept: `append()` pushes an element to the top (end) of the list; `pop()` removes and returns the topmost (last) element.

Step-by-step execution:

| Step | Operation | List / Variable State |
|------|-----------|----------------------|
| 1 | `result = 0` | result = 0 |
| 2 | `numberList = [10, 20, 30]` | numberList = [10, 20, 30] |
| 3 | `numberList.append(40)` | numberList = [10, 20, 30, 40] |
| 4 | `numberList.pop()` returns 40 | result = 0 + 40 = 40; numberList = [10, 20, 30] |
| 5 | `numberList.pop()` returns 30 | result = 40 + 30 = 70; numberList = [10, 20] |
| 6 | `print("Result=", result)` | Prints Result= 70 |

Output:
```
Result= 70
```

Given: Python code using a list as a stack of characters.

Concept: `append()` pushes characters onto the stack; `pop()` removes from the top (LIFO order), effectively reversing the order of insertion.

Step-by-step execution:

| Step | Operation | Stack (answer) | output |
|------|-----------|---------------|--------|
| 1 | `answer=[]` | [] | '' |
| 2 | `answer.append('T')` | ['T'] | '' |
| 3 | `answer.append('A')` | ['T','A'] | '' |
| 4 | `answer.append('M')` | ['T','A','M'] | '' |
| 5 | `ch = answer.pop()` → 'M' | ['T','A'] | 'M' |
| 6 | `ch = answer.pop()` → 'A' | ['T'] | 'MA' |
| 7 | `ch = answer.pop()` → 'T' | [] | 'MAT' |
| 8 | `print("Result=", output)` | — | 'MAT' |

Output:
```
Result= MAT
```

Note: The word 'TAM' was pushed letter by letter and popped in reverse order, giving 'MAT'.

Concept: A stack follows LIFO principle. If we push all characters of a string onto a stack one by one and then pop them all, we get the characters in reverse order.

Algorithm:
1. Take the input string.
2. Push each character of the string onto the stack.
3. Pop each character from the stack and concatenate to form the reversed string.
4. Display the reversed string.

Python Program:

```python
# Program to reverse a string using Stack

def reverseString(inputStr):
stack = [] # Stack implemented using list
reversed_str = '' # To store the reversed string

# PUSH each character of the string onto the stack
for ch in inputStr:
stack.append(ch)

# POP each character from the stack to get reversed string
while len(stack) != 0:
reversed_str = reversed_str + stack.pop()

return reversed_str

# Main program
originalStr = input("Enter a string: ")
result = reverseString(originalStr)
print("Original String :", originalStr)
print("Reversed String :", result)
```

Sample Output:
```
Enter a string: HELLO
Original String : HELLO
Reversed String : OLLEH
```

Explanation:
- For input `HELLO`, characters H, E, L, L, O are pushed onto the stack.
- Stack state: `['H','E','L','L','O']` (O is at top).
- Popping gives: O, L, L, E, H → reversed string = `OLLEH`.

Given Expression: $((2+3)*(4/2))+2$

Concept: To check matching parentheses using a stack:
- Scan the expression left to right.
- If an opening parenthesis `(` is encountered → PUSH it onto the stack.
- If a closing parenthesis `)` is encountered → POP from the stack (it should match the opening parenthesis).
- At the end, if the stack is empty → parentheses are balanced/matched.

Step-by-step process:

| Step | Character Scanned | Operation | Stack Contents |
|------|------------------|-----------|----------------|
| 1 | `(` | PUSH `(` | `(` |
| 2 | `(` | PUSH `(` | `( (` |
| 3 | `2` | Ignore (operand) | `( (` |
| 4 | `+` | Ignore (operator) | `( (` |
| 5 | `3` | Ignore (operand) | `( (` |
| 6 | `)` | POP → matches `(` | `(` |
| 7 | `*` | Ignore (operator) | `(` |
| 8 | `(` | PUSH `(` | `( (` |
| 9 | `4` | Ignore (operand) | `( (` |
| 10 | `/` | Ignore (operator) | `( (` |
| 11 | `2` | Ignore (operand) | `( (` |
| 12 | `)` | POP → matches `(` | `(` |
| 13 | `)` | POP → matches `(` | Empty |
| 14 | `+` | Ignore (operator) | Empty |
| 15 | `2` | Ignore (operand) | Empty |

Conclusion: At the end of the scan, the stack is empty. Therefore, all parentheses in the expression $((2+3)*(4/2))+2$ are properly matched and balanced.

Given: Postfix expression: $AB+C*$, where A=3, B=5, C=1

Concept for Postfix Evaluation using Stack:
- Scan expression left to right.
- If the token is an operand → PUSH onto stack.
- If the token is an operator → POP two operands (first pop = operand2, second pop = operand1), apply the operator: result = operand1 op operand2, then PUSH result back.
- Final value remaining in stack is the answer.

Step-by-step evaluation:

| Step | Token | Operation | Stack |
|------|-------|-----------|-------|
| 1 | A (=3) | PUSH 3 | [3] |
| 2 | B (=5) | PUSH 5 | [3, 5] |
| 3 | + | POP 5 (op2), POP 3 (op1); 3+5=8; PUSH 8 | [8] |
| 4 | C (=1) | PUSH 1 | [8, 1] |
| 5 | * | POP 1 (op2), POP 8 (op1); 8×1=8; PUSH 8 | [8] |

Final Result: The value remaining in the stack = $\boxed{8}$

Verification: $AB+C* = (A+B)*C = (3+5)*1 = 8*1 = 8$ ✓

Given: Postfix expression: $AB*C/D*$, where A=3, B=5, C=1, D=4

Concept: Same as above — scan left to right; PUSH operands, on operator POP two operands, compute, PUSH result.

Step-by-step evaluation:

| Step | Token | Operation | Stack |
|------|-------|-----------|-------|
| 1 | A (=3) | PUSH 3 | [3] |
| 2 | B (=5) | PUSH 5 | [3, 5] |
| 3 | * | POP 5 (op2), POP 3 (op1); 3×5=15; PUSH 15 | [15] |
| 4 | C (=1) | PUSH 1 | [15, 1] |
| 5 | / | POP 1 (op2), POP 15 (op1); 15÷1=15; PUSH 15 | [15] |
| 6 | D (=4) | PUSH 4 | [15, 4] |
| 7 | * | POP 4 (op2), POP 15 (op1); 15×4=60; PUSH 60 | [60] |

Final Result: The value remaining in the stack = $\boxed{60}$

Verification: $AB*C/D* = ((A*B)/C)*D = ((3*5)/1)*4 = (15/1)*4 = 15*4 = 60$ ✓

Given: Infix expression: $A + B - C * D$

Concept — Infix to Postfix conversion rules:
- Scan left to right.
- If token is an operand → append directly to output string.
- If token is an operator:
- While stack is not empty AND top of stack has greater or equal precedence than current operator → POP and append to output.
- PUSH current operator onto stack.
- If token is `(` → PUSH onto stack.
- If token is `)` → POP and append until `(` is found; discard `(`.
- At end → POP all remaining operators from stack to output.

Precedence: `*` and `/` have higher precedence (2) than `+` and `-` (1).

Step-by-step conversion:

| Step | Token | Action | Stack | Output (Postfix) |
|------|-------|--------|-------|------------------|
| 1 | A | Operand → append to output | Empty | A |
| 2 | + | Stack empty → PUSH `+` | [+] | A |
| 3 | B | Operand → append to output | [+] | AB |
| 4 | - | Precedence of `-` (1) ≤ precedence of `+` (1) → POP `+`, append; PUSH `-` | [-] | AB+ |
| 5 | C | Operand → append to output | [-] | AB+C |
| 6 | * | Precedence of `*` (2) > precedence of `-` (1) → PUSH `*` | [-, *] | AB+C |
| 7 | D | Operand → append to output | [-, *] | AB+CD |
| 8 | End | POP `*`, append; POP `-`, append | Empty | AB+CD*- |

Postfix Expression: $\boxed{AB+CD*-}$

Verification: $A+B-C*D$ → Postfix: $AB+CD*-$ ✓

Given: Infix expression: $A * ((C + D)/E)$

Concept: Same rules as above. `(` is pushed onto stack; on encountering `)`, pop until matching `(` is found.

Step-by-step conversion:

| Step | Token | Action | Stack | Output (Postfix) |
|------|-------|--------|-------|------------------|
| 1 | A | Operand → append | Empty | A |
| 2 | * | Stack empty → PUSH `*` | [*] | A |
| 3 | ( | PUSH `(` | [*, (] | A |
| 4 | ( | PUSH `(` | [*, (, (] | A |
| 5 | C | Operand → append | [*, (, (] | AC |
| 6 | + | Top is `(` (not an operator with precedence) → PUSH `+` | [*, (, (, +] | AC |
| 7 | D | Operand → append | [*, (, (, +] | ACD |
| 8 | ) | POP until `(`: POP `+` → append; POP `(` → discard | [*, (] | ACD+ |
| 9 | / | Top is `(` → PUSH `/` | [*, (, /] | ACD+ |
| 10 | E | Operand → append | [*, (, /] | ACD+E |
| 11 | ) | POP until `(`: POP `/` → append; POP `(` → discard | [*] | ACD+E/ |
| 12 | End | POP `*` → append | Empty | ACD+E/* |

Postfix Expression: $\boxed{ACD+E/*}$

Verification: $A*((C+D)/E)$ → Postfix: $ACD+E/*$ ✓

Concept:
- Use a Python list as a stack.
- Accept numbers from the user; push only odd numbers onto the stack.
- To find the largest: pop elements one by one, compare each with a variable `largest`, update if current element is greater.
- Since popping empties the stack, store elements in a temporary list to display stack contents.

Python Program:

```python
# Program to store odd numbers in a Stack and find the largest

# Step 1: Create an empty stack
oddStack = []

# Step 2: Accept numbers from user
n = int(input("How many numbers do you want to enter? "))
for i in range(n):
num = int(input("Enter number: "))
if num % 2 != 0: # Check if number is odd
oddStack.append(num) # PUSH odd number onto stack

# Step 3: Display the stack contents
if len(oddStack) == 0:
print("No odd numbers were entered. Stack is empty.")
else:
print("\nStack contents (bottom to top):", oddStack)

# Step 4: Find the largest odd number using stack
# Use a temporary copy to preserve stack for display
tempStack = oddStack.copy()
largest = tempStack.pop() # POP first element as initial largest

while len(tempStack) != 0:
top = tempStack.pop() # POP next element
if top > largest:
largest = top # Update largest if needed

print("Largest odd number in the Stack:", largest)
```

Sample Output:
```
How many numbers do you want to enter? 6
Enter number: 4
Enter number: 7
Enter number: 12
Enter number: 9
Enter number: 3
Enter number: 15

Stack contents (bottom to top): [7, 9, 3, 15]
Largest odd number in the Stack: 15
```

Explanation:
- Numbers 4 and 12 are even, so they are not pushed.
- Odd numbers 7, 9, 3, 15 are pushed onto the stack.
- A copy of the stack is used to find the largest by popping elements one by one.
- The largest element found is 15.