20

20 — Practice solutions

← Questions

These are independently written explanations, not an official marking scheme.

20A

Pop returns 7. Final contents [4, 2, 9], top 2. Another push is disallowed because capacity is 3 and all positions are live.

Reasoning

Record the returned value separately from the stack after removal. Pop7 frees the top position; push2 reuses it and push9 fills the third position. The top is index 2, not the number of items3.

20B

def balanced(text):
    stack = []
    for character in text:
        if character == "(":
            stack.append(character)
        elif character == ")":
            if len(stack) == 0:  # A closing bracket has no matching opener.
                return False
            stack.pop()  # Match this closer with the latest unmatched opener.
    return len(stack) == 0  # Leftover opening brackets also make it invalid.

Empty input leaves no unmatched brackets and returns True. ")(" fails at its first character because no earlier opening bracket exists.

Reasoning

A closing parenthesis needs an earlier unmatched opening parenthesis. Pop pairs them immediately. After traversal, any remaining openings are unmatched, so the stack must also be empty. Checking counts alone would incorrectly accept )(.

20C

Stacks: [10], [10,4], [10,4,2], [10,8], [2]. Result 2. Infix converts to 10 4 2 * -. At subtraction, pop right=8 first, then left=10, and compute 10−8.

Reasoning

Multiplication consumes4 and 2, leaving its result8 above10. Subtraction then consumes right8 before left10. Treating the first pop as the left operand would produce−2, a clear sign that the operand order was reversed.