Stacks for Balanced Delimiters and Nested Structure

Brackets, HTML tags, function calls, JSON objects, undo histories: all of them nest, and all nesting follows one rule. Whatever was opened most recently has to be closed first. You can’t close a ( while a [ inside it is still open. That “last opened, first closed” behaviour is precisely a stack’s last-in, first-out order, which is why stacks show up every time an interview problem involves nested structure.

The code below is Python, where a plain list works as a stack: append pushes and pop removes from the end, both O(1).

Checking balanced brackets

Valid Parentheses gives you a string of ()[]{} and asks whether every bracket is closed by the right type, in the right order. Push each opener. When a closer arrives, it must match the opener on top of the stack, the most recent one still unclosed.

PAIRS = {")": "(", "]": "[", "}": "{"}

def is_valid(s):
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif ch in PAIRS:
            if not stack or stack[-1] != PAIRS[ch]:   # nothing open, or the wrong type
                return False
            stack.pop()
    return not stack                                   # anything left was never closed

There are three distinct ways a string can be unbalanced, and a correct checker has to catch all of them. The test inputs are chosen to hit each one:

    '()[]{}': True
  '{[()()]}': True
        '(]': False
      '([)]': False
         ']': False
        '((': False
          '': True

"(]" and "([)]" fail on a type mismatch: in the second, the ) arrives while [ is on top. "]" fails because there’s nothing open to close. In Python, calling stack.pop() on an empty list raises IndexError: pop from empty list, which is why the not stack check comes first. "((" passes every step of the loop and fails only at the end because openers are left over. Forgetting that final check is the single most common bug in this problem; the function then reports "((" as valid. The empty string is balanced.

Time is O(n), one push and at most one pop per character. Space is O(n) in the worst case, a string of all openers. More precisely, it’s the maximum nesting depth, which is often much smaller than n in real input.

Why a counter isn’t enough

If there were only one kind of bracket, you wouldn’t need a stack. A single counter, incremented on ( and decremented on ), never going negative and ending at zero, fully checks balance. It’s tempting to extend that to all three types with one shared counter:

def is_valid_counter(s):
    depth = 0
    for ch in s:
        depth += ch in "([{"
        depth -= ch in ")]}"
        if depth < 0:
            return False
    return depth == 0

counter says '([)]' is True

The counter knows how many brackets are open but not which. "([)]" opens two and closes two, never goes negative, and ends at zero, so it passes. A stack remembers the order, which is the information the problem actually needs. If an interviewer asks why you used a stack instead of a counter, this example is the answer.

Saying where it broke

A real parser, the one in your editor or compiler, doesn’t just say “invalid”. It points at the problem. That’s an easy extension: push each opener together with its index, and report positions when something goes wrong.

def first_error(src):
    stack = []                                         # (character, index) of unclosed openers
    for i, ch in enumerate(src):
        if ch in "([{":
            stack.append((ch, i))
        elif ch in PAIRS:
            if not stack:
                return f"unexpected '{ch}' at index {i}"
            opener, j = stack.pop()
            if opener != PAIRS[ch]:
                return f"'{ch}' at index {i} does not match '{opener}' at index {j}"
    if stack:
        opener, j = stack[-1]
        return f"unclosed '{opener}' at index {j}"
    return "ok"

unclosed '{' at index 15
')' at index 5 does not match '[' at index 3
unexpected ')' at index 15
ok

Those are "if (a[0] == b) {", "f(x[1)]", "total = (a + b))" and "{ items: [1, 2, 3] }". The function skips every other character, so it works on code, not just bracket strings. It also shows a nice property of stacks: the item on top is always the innermost unclosed thing, so that’s the one to blame in an error message. Mentioning an extension like this in an interview, briefly, shows you’re thinking about how the code would be used.

Evaluating Reverse Polish Notation

Stacks don’t only hold delimiters. In Reverse Polish Notation, operators come after their operands, so (2 + 1) * 3 is written 2 1 + 3 *. Evaluating it needs no parentheses and no precedence rules: push numbers, and when you see an operator, pop two operands, apply it, and push the result.

def eval_rpn(tokens, divide):
    stack = []
    for tok in tokens:
        if tok in {"+", "-", "*", "/"}:
            b = stack.pop()              # right operand comes off first
            a = stack.pop()
            if tok == "+": stack.append(a + b)
            elif tok == "-": stack.append(a - b)
            elif tok == "*": stack.append(a * b)
            else: stack.append(divide(a, b))
        else:
            stack.append(int(tok))
    return stack[0]

Two details trip people up. First, the operand order: the top of the stack is the right operand, so for 13 5 / you pop 5 first, then 13, and compute 13 / 5. Swap them and subtraction and division come out wrong.

Second, division. Evaluate Reverse Polish Notation specifies that division truncates toward zero, as it does in C, Java and JavaScript (with Math.trunc). Python’s // floors instead, rounding toward negative infinity. They agree on positive numbers and disagree on negative ones:

9 6
truncate: 22  floor: 12
-7 // 2 = -4   int(-7 / 2) = -3

The first line is 2 1 + 3 * and 4 13 5 / +, which agree either way. The longer expression from the problem’s examples includes 6 / -132. Truncation gives 0 and the correct answer 22; flooring gives -1 and a wrong answer of 12. Writing int(a / b) gets truncation in Python. It goes through a float, which is fine for the 32-bit values the problem promises; for arbitrarily large integers you’d compute the sign and the absolute quotient separately. Time and space are both O(n) for n tokens.

Interview practice: decode a nested string

A string is encoded with the rule k[text], meaning text repeated k times, and encodings can nest. Decode it. For example, "3[a2[c]]" decodes to "accaccacc", and "2[abc]3[cd]ef" to "abcabccdcdcdef". Repeat counts may have more than one digit.

Answer

When you hit [, you’re about to start a new, inner string, but you’ll need to come back to the outer one afterwards. So push the context you’ll need later: the text built so far at this level and the repeat count for the bracket you’re entering. Then start fresh. When you hit ], the inner string is finished: pop the saved context and rebuild the outer string as saved_text + inner * count.

def decode_string(s):
    stack = []                           # (text before the bracket, repeat count)
    current, num = "", 0
    for ch in s:
        if ch.isdigit():
            num = num * 10 + int(ch)     # counts can have several digits
        elif ch == "[":
            stack.append((current, num)) # save the outer context
            current, num = "", 0
        elif ch == "]":
            before, k = stack.pop()
            current = before + current * k
        else:
            current += ch
    return current

for s in ["3[a]2[bc]", "3[a2[c]]", "2[abc]3[cd]ef", "10[a]", "abc"]:
    print(f"{s!r} -> {decode_string(s)!r}")

'3[a]2[bc]' -> 'aaabcbc'
'3[a2[c]]' -> 'accaccacc'
'2[abc]3[cd]ef' -> 'abcabccdcdcdef'
'10[a]' -> 'aaaaaaaaaa'
'abc' -> 'abc'

Walk through "3[a2[c]]". At the first [, push ("", 3) and start fresh. Read a. At the second [, push ("a", 2) and start fresh. Read c. At the first ], pop ("a", 2): the current string becomes "a" + "c" * 2 = "acc". At the second ], pop ("", 3): it becomes "" + "acc" * 3, the answer.

The num * 10 + int(ch) line handles multi-digit counts like 10; reading one digit at a time would produce 1 and then 0, which is wrong. Time is proportional to the length of the output (each character is built into a string as the brackets unwind), and the stack holds one entry per nesting level, so O(depth) extra space beyond the strings themselves.

The general pattern, “push the outer state when entering a nested level, pop it when leaving”, is how recursive-descent parsers work too, except they use the call stack instead of an explicit one. Either is fine to present; the explicit stack avoids recursion limits on deeply nested input. For more practice, Min Stack asks you to augment a stack with an extra piece of state per entry, the same idea in a different form.

Keep reading

• Data Structures and Algorithms interview questions
• DSA multiple-choice questions
• Monotonic Stacks and Nearest Greater Elements, a stack with an ordering rule
• Graph DFS States and Cycle Detection, which replaces recursion with an explicit stack
• MIT 6.006 Introduction to Algorithms (Spring 2020)