The Project | About Us | Contribute | Donations | License
HOME My courses Completed
◄ Previous
◄

Applications of Stacks

Next ►
►

You have the stack implemented and measured. This lesson puts it to work in four real applications, developed with complete code: TaskFlow's definitive undo/redo (with two cooperating stacks), validation of balanced parentheses and brackets (which we will use for TaskFlow's search filters), evaluation of postfix expressions with their conversion from infix notation (an estimates calculator), and Python's call stack, which explains why an overly deep recursion blows up with RecursionError. These are the four classic uses of stacks, the ones you will meet in technical interviews and in production code, and they all share the same mental pattern: "the most recent pending thing gets resolved first". We will use the Stack class from the previous lesson in every example.

Contents

  1. Full undo/redo with two stacks
  2. Balanced parentheses: validating TaskFlow's filters
  3. Postfix expressions: evaluation and conversion from infix
  4. The call stack and recursion

Full undo/redo with two stacks

ActionHistory (lesson 03-03) undoes, but it doesn't forgive: if the user undoes by mistake, the action is lost. Every serious piece of software offers redo (Ctrl+Y / Ctrl+Shift+Z). The classic solution uses two cooperating stacks:

  • The undo stack: the actions performed and currently in effect.
  • The redo stack: the actions the user has undone (and might want to recover).

The rules of the dance are three:

The user... undo stack redo stack
Performs a new action push(action) Gets emptied
Presses Undo pop() → it gets reverted push(action)
Presses Redo push(action) pop() → it gets reapplied

Undo and redo pass actions back and forth, like two hands. The subtle rule — and the most often forgotten — is the first: a new action invalidates redo. If, after undoing "change priority", the user edits the title, "redoing the priority change" no longer makes sense on a state that has diverged: the redo stack must be emptied.

flowchart LR
    U["New action"] -->|push| D["UNDO stack"]
    U -.->|empties| R["REDO stack"]
    D -->|"Undo: pop"| R
    R -->|"Redo: pop"| D

The implementation, on top of the Stack from 03-03 and the actions {"type", "task", "prev_data"}. What's new is that each action now also stores new_data, because redo needs to reapply the new value (undo restores the previous one; redo restores the new one):

class UndoRedoManager:
    """TaskFlow's undo/redo with two cooperating stacks."""

    def __init__(self, tasks):
        self._tasks = tasks              # the board: dict of tasks by id
        self._undo = Stack()
        self._redo = Stack()

    def execute(self, action_type, task_id, new_data):
        """Records and applies a new user action."""
        task = self._tasks[task_id]
        # 1. Capture the previous values BEFORE modifying (the 03-03 pattern)
        prev_data = {field: task[field] for field in new_data}
        # 2. Apply the change
        task.update(new_data)
        # 3. Record the complete action (with the previous AND the new values)
        self._undo.push({"type": action_type, "task": task_id,
                         "prev_data": prev_data,
                         "new_data": new_data})
        # 4. A new action invalidates the entire redo
        self._redo = Stack()

    def undo(self):
        if self._undo.is_empty():
            return "Nothing to undo"
        action = self._undo.pop()
        self._tasks[action["task"]].update(action["prev_data"])
        self._redo.push(action)          # the action moves to the other stack
        return f"Undone: {action['type']} (task {action['task']})"

    def redo(self):
        if self._redo.is_empty():
            return "Nothing to redo"
        action = self._redo.pop()
        self._tasks[action["task"]].update(action["new_data"])
        self._undo.push(action)          # and back to the undo stack it goes
        return f"Redone: {action['type']} (task {action['task']})"

A full session on task 7:

tasks = {7: {"id": 7, "title": "Review budget", "priority": 2,
             "status": "pending"}}
manager = UndoRedoManager(tasks)

manager.execute("change_priority", 7, {"priority": 1})
manager.execute("change_status", 7, {"status": "in_progress"})
print(tasks[7]["priority"], tasks[7]["status"])   # 1 in_progress

print(manager.undo())             # Undone: change_status (task 7)
print(tasks[7]["status"])         # pending

print(manager.redo())             # Redone: change_status (task 7)
print(tasks[7]["status"])         # in_progress

manager.undo()                    # undoes the status again
manager.execute("assign", 7, {"assigned_to": "anna"})   # new action!
print(manager.redo())             # Nothing to redo  <- redo was invalidated

Look at the last line: there was an action waiting in redo, but the assignment to Anna invalidated it. That is rule 1 in action, and it is exactly how your text editor behaves.

Does it remind you of anything? In module 2, TaskHistory solved "back/forward" with a doubly linked list and a cursor. They are two solutions to the same bidirectional-navigation problem: the doubly linked list keeps the whole history and moves a cursor (ideal when moving forward invalidates nothing, like visiting tasks); the two stacks discard the future when the present changes (ideal for editing, where dead branches must not survive). Choosing between them is choosing the right semantics, not the "better" structure.

Balanced parentheses: validating TaskFlow's filters

TaskFlow wants to allow advanced, user-written search filters:

(priority:1 OR priority:2) AND [status:pending OR {assigned_to:anna}]

Before interpreting a filter, we must validate that its parentheses (), brackets [] and braces {} are balanced: every opener has its closer, of the right type and in the right order. (a[b)c] is wrong even though there are as many closers as openers: they cross.

Why a stack? Because when a closer appears, it must match the most recent pending opener: pure LIFO.

The algorithm:

  1. Walk the string character by character.
  2. If it is an opener ((, [, {) → push.
  3. If it is a closer (), ], }) → the stack cannot be empty, and its top must be the matching opener; pop and check.
  4. When finished, the stack must be empty (no orphaned openers).
PAIRS = {")": "(", "]": "[", "}": "{"}

def is_balanced_filter(filter_text):
    """Checks that the filter's (), [] and {} are properly balanced."""
    stack = Stack()
    for char in filter_text:
        if char in "([{":
            stack.push(char)                     # opener: left pending
        elif char in ")]}":
            if stack.is_empty():
                return False                     # closer with no pending opener
            if stack.pop() != PAIRS[char]:
                return False                     # closer of the wrong type
        # any other character (letters, spaces, ':') doesn't affect the balance
    return stack.is_empty()                      # no unclosed openers

Explanation of the three failure modes, with the trace of the crossed example (a[b)c]:

Character Action Stack (top on the right) Result
( push (
a ignore (
[ push (, [
b ignore (, [
) pop → [ comes out, expected ( False: wrong closer
  • Closer with an empty stack ("task)"): a ) with no pending ( at all.
  • Closer of the wrong type ("(a[b)c]"): the most interesting one — there are pending openers, but the most recent one is not the match.
  • Non-empty stack at the end ("(pending"): openers that were never closed.
print(is_balanced_filter("(priority:1 OR priority:2) AND [status:pending]"))  # True
print(is_balanced_filter("(a[b)c]"))     # False
print(is_balanced_filter("(pending"))    # False
print(is_balanced_filter(""))            # True (nothing to balance)

Cost: O(n) in time (one pass over the string, with O(1) stack operations) and O(n) in space in the worst case (all openers). This algorithm, as is, is the one editors and IDEs use to highlight your unmatched parenthesis in red.

Postfix expressions: evaluation and conversion from infix

TaskFlow wants a mini estimates calculator: the user types (3 + 5) * 2 (the hours of three subtasks...) and the application evaluates it. Evaluating infix notation (the operator between its operands) is awkward: it requires precedence (* before +) and parentheses. Compilers solve it in two phases, both with stacks:

  1. Convert the infix expression to postfix (reverse Polish notation: the operator after its operands): (3 + 5) * 2 → 3 5 + 2 *.
  2. Evaluate the postfix, which no longer needs precedence or parentheses.

Evaluating postfix (one operand stack)

Rule: walk the tokens; if it is a number, push; if it is an operator, pop two operands, operate, and push the result. At the end exactly one value remains: the result.

def eval_postfix(expression):
    """Evaluates a postfix expression with space-separated tokens."""
    stack = Stack()
    for token in expression.split():
        if token in "+-*/":
            b = stack.pop()                  # watch the order!
            a = stack.pop()                  # a arrived before b
            if token == "+":   stack.push(a + b)
            elif token == "-": stack.push(a - b)
            elif token == "*": stack.push(a * b)
            elif token == "/": stack.push(a / b)
        else:
            stack.push(float(token))         # operand: onto the stack
    return stack.pop()                       # the single remaining value

print(eval_postfix("3 5 + 2 *"))    # 16.0  ==  (3 + 5) * 2
print(eval_postfix("3 5 2 * +"))    # 13.0  ==  3 + 5 * 2

Trace of 3 5 + 2 *:

Token Action Stack (top on the right)
3 push 3 3
5 push 5 3, 5
+ pop 5 and 3 → push 8 8
2 push 2 8, 2
* pop 2 and 8 → push 16 16

The detail that causes 90% of the bugs: the order of the pops. The first pop returns the right-hand operand (b), the second the left-hand one (a). With + and * it doesn't matter (they are commutative); with - and / it changes your result: 6 2 / must be 6 / 2 = 3, not 2 / 6.

Converting infix → postfix (one operator stack)

Dijkstra's shunting-yard algorithm, in its essential version. Numbers go straight to the output; operators wait on a stack until one of lower or equal precedence (or a closing parenthesis) arrives and forces them out:

PRECEDENCE = {"+": 1, "-": 1, "*": 2, "/": 2}

def infix_to_postfix(expression):
    output = []
    stack = Stack()                          # stack of waiting operators
    for token in expression.split():
        if token in PRECEDENCE:              # it is an operator
            # Evict operators of higher or equal precedence: they go first
            while (not stack.is_empty() and stack.peek() != "("
                   and PRECEDENCE.get(stack.peek(), 0) >= PRECEDENCE[token]):
                output.append(stack.pop())
            stack.push(token)
        elif token == "(":
            stack.push(token)                # marks the start of a group
        elif token == ")":
            while stack.peek() != "(":       # evict up to the opener
                output.append(stack.pop())
            stack.pop()                      # discard the '(' (it doesn't go out)
        else:
            output.append(token)             # operand: straight to the output
    while not stack.is_empty():
        output.append(stack.pop())           # evict whatever is left
    return " ".join(output)

print(infix_to_postfix("( 3 + 5 ) * 2"))   # 3 5 + 2 *
print(infix_to_postfix("3 + 5 * 2"))       # 3 5 2 * +
print(eval_postfix(infix_to_postfix("( 3 + 5 ) * 2")))  # 16.0

Notice the use of peek we announced in 03-02: the eviction while reads the top to decide whether to pop — look before you leap. And in the second example, watch how the stack holds on to the + while it processes 5 * 2: operator precedence sorts itself out thanks to LIFO order. (Our version requires space-separated tokens and doesn't handle unary operators or exponents: enough for TaskFlow's estimates; the full algorithm is a direct extension.)

The call stack and recursion

The most important stack of all is one you didn't create: the call stack. Every time Python enters a function, it pushes a frame with its local variables and the return point; when the function returns, it pops it. Watch it live:

def a():
    print("entering a")
    b()
    print("leaving a")      # runs AFTER b finishes

def b():
    print("  entering b")
    c()
    print("  leaving b")

def c():
    print("    entering c")
    print("    leaving c")

a()
entering a
  entering b
    entering c
    leaving c
  leaving b
leaving a

The entries happen in order a→b→c, but the exits in reverse order c→b→a: the last function in is the first one out. Pure LIFO; that is why the structure holding it up is a stack. When an error goes uncaught, Python prints that stack for you — the traceback is, literally, a dump of the call stack, from the bottom (a) to the top (c).

Why deep recursion blows up

A recursive function pushes itself once per level. Summing the ids of a chain of linked tasks, recursively:

def sum_ids(node):
    if node is None:                 # base case: chain exhausted
        return 0
    return node.data["id"] + sum_ids(node.next)   # one frame per node

With 100 tasks, perfect: 100 frames pushed and popped. With 100,000 tasks:

RecursionError: maximum recursion depth exceeded

The call stack has a limit (by default, about 1000 frames in CPython — check it with sys.getrecursionlimit()): it protects the process's memory from runaway recursions. The practical conclusion:

  • Recursion: elegant for small or bounded depths (balanced trees, divide and conquer).
  • Iteration with an explicit stack: when the depth can be large, replace the call stack (limited, implicit) with a Stack of your own (as large as your memory, explicit). Every recursion can be rewritten this way, and it is a central exercise of the next lesson.

This recursion/explicit-stack duo will return in force: tree traversals (module 6) and depth-first search (DFS) on graphs (module 7) are exactly this — in fact, "iterative DFS" is nothing more than swapping the call stack for an explicit stack. Consider it announced.

Common Mistakes and Tips

  • Forgetting to empty the redo stack when a new action executes: the classic undo/redo bug; it produces "redos" that apply changes to a state that no longer exists, corrupting data. The rule is non-negotiable.
  • Storing only prev_data when there is a redo: undo needs the previous values, redo needs the new ones. Without new_data, redo doesn't know what to reapply.
  • In balance checking, checking only the counts: "three openers and three closers" is not enough ()a( or (a[b)c] fail). Type and order must match: that is why you need the stack and not a counter.
  • Forgetting the final or initial is_empty() in balance checking: without the final check, "(pending" would pass; without the initial one before a closer, ")" would raise IndexError instead of returning False.
  • Swapping the operands in - and /: the first pop is the right-hand operand. Engrave it: b = pop(); a = pop(); a - b.
  • "Fixing" a RecursionError by raising the limit with sys.setrecursionlimit: it is almost always hiding the problem (and risking taking the whole process down). The robust solution is iterating with an explicit stack.

Exercises

Exercise 1: multiple undo

Add to UndoRedoManager a method undo_many(n) that undoes up to n actions in one go (TaskFlow's interface will have an "undo the last 5" menu). It must return the list of messages from each effective undo and stop without error if the history runs out first. Extra question: after undo_many(3), what must the redo stack contain, and in what order, so that three consecutive redo() calls restore everything correctly?

Exercise 2: balance checking with the error position

Improve is_balanced_filter so that, instead of False, it returns the position (index) of the character that breaks the balance, or -1 if the filter is valid. For unclosed openers, return the position of the innermost orphaned opener (hint: push tuples (char, index)).

Exercise 3: evaluating a complete infix estimate

Combine the two functions from section 3 into estimate(infix_expression), which first validates the parenthesis balance (with is_balanced_filter), raises ValueError("unbalanced expression") if it fails, and otherwise converts and evaluates. Test it with "( 3 + 5 ) * 2" and "( 3 + 5 * 2".

Solutions

Solution 1:

def undo_many(self, n):
    messages = []
    for _ in range(n):
        if self._undo.is_empty():            # history exhausted: stop without error
            break
        messages.append(self.undo())         # reuses all the existing logic
    return messages

Reusing self.undo() guarantees that each step moves the action onto the redo stack. Extra question: if actions A3, A2, A1 are undone (in that order, from most recent to oldest), the redo stack ends up with A1 on top and A3 at the bottom. So the first redo() reapplies A1, then A2, then A3: exactly the original chronological order. The two stacks reverse the order twice, and two reversals restore the order — a pattern that reappears in the reversing exercise of 03-05.

Solution 2:

def balanced_filter_pos(filter_text):
    stack = Stack()                          # we push (char, index)
    for i, char in enumerate(filter_text):
        if char in "([{":
            stack.push((char, i))
        elif char in ")]}":
            if stack.is_empty():
                return i                     # closer with no opener: culprit here
            opener, _ = stack.pop()
            if opener != PAIRS[char]:
                return i                     # closer of the wrong type
    if not stack.is_empty():
        _, index = stack.pop()               # the innermost orphaned opener
        return index
    return -1

print(balanced_filter_pos("(a[b)c]"))     # 4  (the ')' that doesn't match)
print(balanced_filter_pos("(pending"))    # 0  (the '(' never closed)
print(balanced_filter_pos("(ok)[yes]"))   # -1

The key is enriching what gets pushed: instead of the character alone, a tuple with its index. The structure of the algorithm doesn't change — another advantage of reasoning with the contract: the stack doesn't require its elements to be of any particular type.

Solution 3:

def estimate(infix_expression):
    if not is_balanced_filter(infix_expression):
        raise ValueError("unbalanced expression")
    postfix = infix_to_postfix(infix_expression)
    return eval_postfix(postfix)

print(estimate("( 3 + 5 ) * 2"))   # 16.0
print(estimate("( 3 + 5 * 2"))     # ValueError: unbalanced expression

Validating before converting prevents infix_to_postfix from failing with a cryptic IndexError while looking for a ( that doesn't exist: the TaskFlow user gets an understandable domain error, not a traceback from an internal structure. Three stack algorithms chained in five lines.

Conclusion

You have seen the stack deployed in its four starring roles: two cooperating stacks give TaskFlow a professional undo/redo (with the golden rule of invalidating redo on new actions, and its contrast with module 2's doubly-linked-list TaskHistory); a stack of pending openers validates the balance of the search filters by matching each closer with the most recent opener; an operand stack and an operator stack evaluate and translate arithmetic expressions, resolving precedence through sheer LIFO order; and Python's call stack holds up every function you run, with its depth limit as the cause of RecursionError — and the explicit stack as the cure, which in modules 6 and 7 will become tree traversals and DFS. The common pattern: the most recent pending thing gets resolved first. All that remains is consolidation: the next lesson is entirely exercises, where you will reverse sequences, build a min-tracking stack in O(1), validate operation sequences, and turn recursions into iterations. No new theory: pure practice.

◄ Previous
◄
Next ►
►
The Project | About Us | Contribute | Donations | License
© Copyright 2026. All rights reserved