Stacks: undo, nesting, matching

A stack is a list used from one end only: append to push, pop() to take the newest item off. Use one whenever the rule is "the most recent thing comes back first".

history = []
history.append("draft 1")
history.append("draft 2")
last = history.pop()      # "draft 2"

Typical jobs:

Undo: push the state before each change; undo pops it back.
Nesting: push when something opens, pop when it closes. The stack length is the current depth.
Matching: a closer must match whatever is on top. Compare before you pop.

Two traps. pop() on an empty list raises an error, so check if stack: first when the input can be odd. And if you save the list itself to remember a moment, save a copy (list(stack)), or later pushes will change your record.

In the visual, watch the list grow on the right and shrink when a < arrives.

See it run

stack = []
for ch in "ab<c":
    if ch == "<":
        stack.pop()
    else:
        stack.append(ch)
print("".join(stack))

Letters are pushed; a < pops the most recent one.

Practice stacks: undo, nesting, matching

Exercise 1

A document is a list of tag tokens. An opening token is a name such as "div"; its closing token is "/" plus the same name, such as "/div". The tokens are always properly nested and balanced (every tag is closed, by its own name, in the right order).

Return the list of tag names that are open at the first moment the nesting is deepest, outermost first. If there are no tokens, return an empty list.

Constraints: 0 ≤ len(tokens) ≤ 10^4.

Example: solution(["a", "b", "/b", "c", "d", "/d", "/c", "/a"]) returns ["a", "c", "d"]: depth 2 is first reached at "b", but depth 3 is only reached at "d", and ["a", "b"] never gets deeper.

Exercise 2

A tiny text editor starts with empty text. Each item of ops is one of:

"CLEAR": the text becomes empty (this counts as a change, even if the text was already empty).
"UNDO": reverses the most recent change that has not been undone yet, restoring the text from before it. If there is nothing to undo, it does nothing. UNDO itself is not a change, so it cannot be undone.
Anything else is a single lowercase letter, which is added to the end of the text (also a change).

Return the final text.

Constraints: 0 ≤ len(ops) ≤ 10^4.

Example: solution(["a", "b", "CLEAR", "UNDO"]) returns "ab". The undo reverses the CLEAR.

Exercise 3

A wiki page is checked for broken tags. tokens lists the tags in order: an opening token is a name like "note", and a closing token is "/" plus a name, like "/note". A closing token is correct only if it names the most recently opened tag that is still open.

Return:

the index (0-based) of the first closing token that is not correct (nothing is open, or it names a different tag); otherwise
the index of the earliest opening token that is never closed; otherwise
-1 if everything matches.

Constraints: 0 ≤ len(tokens) ≤ 10^4. Names are non-empty and have no spaces.

Examples: solution(["a", "b", "/a", "/b"]) returns 2. solution(["a", "b", "c", "/c"]) returns 0 because "a" and "b" are left open and "a" is earlier.

The explanation and tasks are public. Running this lesson requires an account with course access.

Practice

Loading Python…

Loading exercise content…

Visualizer Watch your code run line by line

Run your code, then choose Play to follow its execution.

Memory · names → values

Variables appear here as Python creates them.

Output & plots