Skip to content
Tutorials Center
My learning

Topics

Lesson 44 of 225 ยท Stacks and Queues

Stack Applications

See what stacks are for: balanced brackets, infix to postfix, evaluating expressions, a min stack with O(1) minimum and browser history, all in Python.

A stack looks too simple to be powerful: push, pop, peek. But whenever a problem contains nesting (something opened must be closed in reverse order), a stack is usually the cleanest solution. This lesson walks through five classic applications: checking balanced brackets, converting an expression from infix to postfix notation, evaluating it, a stack that reports its minimum in O(1), and browser-style history with back and forward.

Each section follows the same plan: the problem, the obvious approach, why a stack is better, working code, a trace and the cost.

Application 1: balanced brackets

Problem. Given a string made of ()[]{} (and possibly other characters), decide whether every opening bracket is closed by the right kind of bracket in the right order. "{[()]}" is valid; "(]", "(()" and "())(" are not.

Brute force. Repeatedly delete adjacent matching pairs (), [], {} from the string until nothing changes. If the string becomes empty, it is balanced. This is correct but each pass scans and rebuilds the string, so it can take O(nยฒ) time.

Stack idea. The most recent unclosed opener is the only one that can be closed next. That is exactly "last in, first out":

  • On an opening bracket, push it.
  • On a closing bracket, the stack must not be empty and its top must be the matching opener; pop it.
  • At the end, the stack must be empty (no unclosed openers).
TEXT
"{[()]}"
 {   push {          stack: {
 [   push [          stack: { [
 (   push (          stack: { [ (
 )   top is (, pop   stack: { [
 ]   top is [, pop   stack: {
 }   top is {, pop   stack: (empty)  -> balanced
Python Balanced brackets: brute force and stack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The stack version makes one pass: O(n) time, and O(n) space in the worst case (a string of only openers). The brute-force version only works when the string contains nothing but brackets, because it never deletes other characters; the stack version simply ignores them.

Application 2: infix to postfix

Humans write infix expressions: 2 + 3 * 4, with operators between operands. To evaluate that correctly you need precedence rules (* before +) and parentheses. Computers find it easier to work with postfix (also called Reverse Polish Notation), where operators come after their operands:

TEXT
infix:    2 + 3 * 4          postfix:  2 3 4 * +
infix:    (2 + 3) * 4        postfix:  2 3 + 4 *

Postfix needs no parentheses and no precedence rules: the order of tokens is the order of evaluation. Converting is done with the shunting-yard algorithm, which uses a stack for operators:

  1. Read tokens left to right.
  2. A number goes straight to the output.
  3. An operator o1: while the operator on top of the stack has higher precedence than o1 (or equal precedence and o1 is left-associative), pop it to the output. Then push o1.
  4. A left parenthesis is pushed.
  5. A right parenthesis pops operators to the output until a left parenthesis is found; discard both parentheses.
  6. At the end, pop everything left on the stack to the output.

Associativity matters for equal precedence: 8 - 3 - 2 means (8 - 3) - 2, so - is left-associative. Exponent 2 ^ 3 ^ 2 means 2 ^ (3 ^ 2), so ^ is right-associative.

Python Shunting-yard: infix to postfix

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each token is pushed and popped at most once, so conversion runs in O(n) time with O(n) stack space.

Application 3: evaluating postfix

Evaluating postfix is delightfully simple with a stack of operands:

  • Number: push it.
  • Operator: pop the right operand, then the left operand, apply the operator, and push the result.
  • At the end, the stack holds exactly one value: the answer.
TEXT
postfix: 2 3 4 * +
2      stack: 2
3      stack: 2 3
4      stack: 2 3 4
*      pop 4, pop 3 -> 12; stack: 2 12
+      pop 12, pop 2 -> 14; stack: 14   -> answer 14

Note the pop order: the first pop is the right operand. This matters for -, / and ^.

Python Evaluate infix by converting to postfix

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The results print as floats because we convert tokens with float. 8 - 3 - 2 = 3.0 proves left associativity, while 2 ^ 3 ^ 2 = 512.0 proves right associativity (2 ^ 9, not 8 ^ 2 = 64).

Real calculators and compilers use the same idea: parse the expression into postfix or a tree, then evaluate with a stack. Many virtual machines (including Python's own bytecode interpreter) are stack machines. You will meet the tree version, expression trees, in the Trees chapter.

Application 4: a stack with O(1) minimum

Problem. Design a stack with push, pop, peek and get_min, all O(1). get_min returns the smallest value currently in the stack.

Brute force. Compute min(self.items) each time: O(n) per get_min.

Track the min in a second stack. Keep a parallel stack where each entry is the minimum of everything at or below that position. When you push x, push min(x, current_min) onto the min-stack; when you pop, pop both. The top of the min-stack is always the current minimum. Space is O(n) extra; time O(1) per operation.

TEXT
push 5 -> items: 5          mins: 5
push 3 -> items: 5 3        mins: 5 3
push 7 -> items: 5 3 7      mins: 5 3 3     get_min = 3
pop    -> items: 5 3        mins: 5 3       get_min = 3
pop    -> items: 5          mins: 5         get_min = 5
Python Min stack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that after popping the second 3, the minimum is still 3, because the first 3 remains. A common wrong idea is to store a single current_min variable: it cannot be restored after the minimum is popped. The parallel stack remembers the answer for every depth.

Application 5: browser history

A browser keeps two stacks: back and forward. Visiting a page pushes the current page onto back and clears forward. Going back moves the current page to forward and pops back; going forward does the opposite. (A doubly linked list models the same behavior.)

Python Back and forward with two stacks

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Conversions in every direction

Infix, postfix and prefix (Polish notation, operator before operands: + 2 * 3 4) are three spellings of the same expression tree. Besides infix to postfix you will be asked for the other five directions. Each is a short stack program, and they all follow the same two ideas.

  • Postfix or prefix to something else: keep a stack of finished sub-expressions (strings). An operator pops its two operands and pushes a combined string. For postfix, read left to right: the top of the stack is the right operand and the one below it the left. For prefix, read right to left and the roles swap: the first pop is the left operand.
  • Infix to prefix: reverse the infix string, swap ( with ), run the infix to postfix conversion, then reverse the result. Because associativity flips under reversal, swap the equal-precedence rule: pop an equal-precedence operator only when it is ^, never for + - * /.
Python Postfix, prefix and infix in every direction

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check the 8 - 3 - 2 case: the prefix form - - 8 3 2 groups as (8 - 3) - 2, which is the left-associative reading, so the swapped equal-precedence rule did its job.

Redundant brackets

A pair of brackets is redundant if removing it does not change the meaning: ((a + b)) has a spare pair, and so does (a). Detect them with a stack. Push every character except ). On ), pop until the matching ( and note whether you popped an operator. If you popped none (the brackets enclose a single operand or another bracket group directly), the pair is redundant.

Python Find redundant parentheses

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Complexity at a glance

Application Time Extra space
Balanced brackets O(n) O(n) worst case
Infix to postfix O(n) O(n)
Postfix evaluation O(n) O(n)
Min stack O(1) per operation O(n)
Browser history O(1) per move O(n)

Common mistakes

  • Not checking for an empty stack before pop() on a closing bracket ("())" crashes with IndexError).
  • Forgetting the final check not stack: "((" never fails during the scan but is unbalanced.
  • Swapping operand order in evaluation. a - b needs right = pop() first.
  • Ignoring associativity, which gives wrong answers for ^ or long chains of -.
  • Using one running minimum instead of a stack of minimums.
  • Leaving unmatched parentheses silently in the shunting-yard algorithm. Raise an error.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. After scanning the whole string, the bracket checker's stack still holds one item. What does that mean?

    Leftover items are openers never matched by a closer, so the string is not balanced. An unmatched closer is caught earlier, when pop finds an empty stack.
  2. 2. What is the postfix form of 2 + 3 * 4?

    Multiplication has higher precedence, so 3 4 * is computed first, then added to 2.
  3. 3. When evaluating postfix 9 2 -, what must happen for the right answer 7?

    The first pop is the right operand. Swapping them would give 2 - 9 = -7.
  4. 4. Why does a min stack store a minimum for every position instead of one variable?

    After popping the smallest item you need the previous minimum, which only the parallel stack remembers.
  5. 5. In a browser model with back and forward stacks, what happens to the forward stack when you visit a new page?

    A new visit starts a new path, so the pages you had gone back from can no longer be reached with forward.

Summary

  • Use a stack whenever the most recently opened thing must be closed or handled first.
  • Balanced brackets: push openers, match closers against the top, and require an empty stack at the end (O(n)).
  • The shunting-yard algorithm converts infix to postfix with an operator stack, respecting precedence and associativity.
  • Postfix evaluation uses an operand stack; the first value popped is the right operand.
  • A min stack keeps a parallel stack of running minimums to answer get_min in O(1).
  • Browser history is two stacks (back and forward); a new visit clears forward.

Next: Monotonic Stack