🎓 A1Learner
🔍
0 of 47 lessons completed

Stacks for Matching and Undoing

A stack is a pile where the last item placed is the first item taken. It fits problems where the newest item must be handled first.

Spot the signal

A problem mentions undo or matching pairs. The newest action is the one that must be undone first.

actions = ["a", "b", "undo", "c"]
typed = []
for action in actions:
    if action == "undo":
        typed.pop()
    else:
        typed.append(action)
print("".join(typed))

The template

Push opening brackets and pop on closing brackets. A mismatch means the text is not balanced.

def balanced(text):
    stack = []
    pairs = {")": "(", "]": "[", "}": "{"}
    for char in text:
        if char in "([{":
            stack.append(char)
        elif char in pairs:
            if not stack or stack.pop() != pairs[char]:
                return False
    return not stack
print(balanced("([{}])"))
print(balanced("([)]"))

Worked problem: cancel neighbours

Two equal neighbours cancel each other. A stack keeps only the survivors.

stack = []
for char in "abbaca":
    if stack and stack[-1] == char:
        stack.pop()
    else:
        stack.append(char)
print("".join(stack))

Example

steps = ["docs", "pics", "..", "music"]
path = []
for step in steps:
    if step == "..":
        path.pop()
    else:
        path.append(step)
print("/" + "/".join(path))

Key points

  • Push: place an item on top of the pile.
  • Pop: take the item from the top of the pile.
  • Use a stack when the newest item must be handled before older items.
  • Use a stack to match pairs that close in reverse order.
  • A plain list works as a stack in Python.
  • A stack keeps order by recency, not by size.

The code treats each folder step as a stack action. Going back pops the newest folder. The final pile gives the path.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

Which action removes the newest item from a stack?