Stacks That Carry State
Push pairs to remember a running minimum, and evaluate expressions with a stack.
11 min, 0 of 3 activities solved
View cheatsheetGetting Python ready… examples can run in a moment.
Sometimes the item alone isn't enough: you also want a fact about everything underneath it - the minimum so far, a count, a position. The trick: push a tuple that stores the item and that fact.
Why does it work? While an entry sits on the stack,
nothing below it can change. So a snapshot taken at
push time stays correct until that entry is popped.
Every operation stays O(1): no rescanning with
min(stack).
A stack of (value, min so far) pairs
push 5: nothing is below it, so the min so far is 5 itself.
Each column is one entry (value, min so far); the top of the stack is on the right.
A stack that knows its minimum
Swap min for max and you have a max-stack. The
same idea stores anything "so far": sums, counts,
indices.
What does this print?
Evaluating expressions. In Reverse Polish Notation (postfix) the operator comes after its two operands, so no parentheses are needed:
infix: (3 + 4) * 2
postfix: 3 4 + 2 *
Scan left to right. A number is pushed. An operator pops the right operand first, then the left one, and pushes the result. At the end the answer is the only thing left on the stack.
Evaluating 5 1 2 + 4 * + 3 -
A number: push it.
Postfix evaluation, traced
That's 5 + (1 + 2) * 4 - 3 = 14. Pop order matters
for - and /: swap a and b and "9 2 -"
would give -7 instead of 7.
What does this print?
Simplify a Unix path
Write simplify_path(path) for an absolute Unix
path. Split on /, then for each part:
""or".": skip it"..": go up one folder (if you're not at the root)- anything else: a folder name, go into it
Return "/" followed by the folders joined with
/. Example: "/a/./b/../../c/" -> "/c".