ITPEC FE Subject B April 2025 Question 8

Stack-based string reversal — fill in push/pop logic to reverse a string using a stack.

The program pushes each character of inputStr onto a stack, then pops them all to build outputStr in reverse order.

push(x): increments sp first, then stores x at stack[sp]. After pushing all characters, sp points to the top element.

Blank A (while loop condition): The loop while (sp ≠ A) must stop when the stack is empty. Since sp starts at 0 and push increments before storing, after popping the last element sp returns to 0. So A = 0.

Blank B (pop body): Since sp points to the current top element (push writes after incrementing), pop must first read stack[sp], then decrement sp:
- retvar ← stack[sp]
- sp ← sp - 1

Answer: (f) — A = 0, B = retvar ← stack[sp] then sp ← sp - 1.

Why not others:
- (a)–(d) A = -1 means the loop continues until sp = -1, causing an access to stack[0] which is undefined — violates the constraint
- (e) pop increments sp (goes upward instead of downward) — infinite loop
- (g) increments sp before reading — reads wrong element and loops infinitely
- (h) decrements sp before reading — skips the top element, losing the first character to reverse

Key rule: In a stack where push does sp++ then write, pop must do read then sp-- — they are mirror operations.

AI-generated — may contain errors