Stack Applications: Balanced Parentheses, Expressions & Undo

The stack earns its keep because LIFO order matches a huge family of problems: anything involving nesting, matching, or “go back to the previous state”. This page works through three classic applications — balanced parentheses, postfix expression evaluation, and undo/redo — with correct, idiomatic code in all four languages. If you are new to stacks, start with the stacks introduction.

1. Balanced parentheses

Problem: given a string of brackets ()[]{}, decide whether every opener has a matching closer in the right order. Push each opener; on a closer, the top of the stack must be its matching opener. At the end the stack must be empty.

#include <string>
#include <stack>
#include <unordered_map>
bool isBalanced(const std::string& s) {
    std::unordered_map<char, char> match = {{')','('}, {']','['}, {'}','{'}};
    std::stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') st.push(c);
        else if (match.count(c)) {
            if (st.empty() || st.top() != match[c]) return false;
            st.pop();
        }
    }
    return st.empty();
}

import java.util.*;
boolean isBalanced(String s) {
    Map<Character, Character> match = Map.of(')', '(', ']', '[', '}', '{');
    Deque<Character> st = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') st.push(c);
        else if (match.containsKey(c)) {
            if (st.isEmpty() || st.pop() != match.get(c)) return false;
        }
    }
    return st.isEmpty();
}

function isBalanced(s) {
  const match = { ')': '(', ']': '[', '}': '{' };
  const st = [];
  for (const c of s) {
    if (c === '(' || c === '[' || c === '{') st.push(c);
    else if (c in match) {
      if (st.pop() !== match[c]) return false;
    }
  }
  return st.length === 0;
}

def is_balanced(s):
    match = {')': '(', ']': '[', '}': '{'}
    st = []
    for c in s:
        if c in '([{':
            st.append(c)
        elif c in match:
            if not st or st.pop() != match[c]:
                return False
    return not st

Complexity: O(n) time, O(n) space (worst case all openers).

Pitfall: Forgetting the final st.empty() check. "(((" never hits a mismatch but is still unbalanced — leftover openers mean failure.

2. Evaluating a postfix expression

In postfix (Reverse Polish) notation, operators come after their operands, e.g. 3 4 + 2 * = (3+4)*2 = 14. No parentheses needed. Push numbers; on an operator, pop the top two, apply, push the result. The last value on the stack is the answer.

#include <vector>
#include <string>
#include <stack>
int evalPostfix(const std::vector<std::string>& tokens) {
    std::stack<int> st;
    for (const std::string& t : tokens) {
        if (t == "+" || t == "-" || t == "*" || t == "/") {
            int b = st.top(); st.pop();
            int a = st.top(); st.pop();
            if (t == "+") st.push(a + b);
            else if (t == "-") st.push(a - b);
            else if (t == "*") st.push(a * b);
            else st.push(a / b);
        } else st.push(std::stoi(t));
    }
    return st.top();
}

import java.util.*;
int evalPostfix(String[] tokens) {
    Deque<Integer> st = new ArrayDeque<>();
    for (String t : tokens) {
        switch (t) {
            case "+": case "-": case "*": case "/":
                int b = st.pop(), a = st.pop();
                st.push(t.equals("+") ? a + b
                      : t.equals("-") ? a - b
                      : t.equals("*") ? a * b : a / b);
                break;
            default:
                st.push(Integer.parseInt(t));
        }
    }
    return st.pop();
}

function evalPostfix(tokens) {
  const st = [];
  const ops = {
    '+': (a, b) => a + b,
    '-': (a, b) => a - b,
    '*': (a, b) => a * b,
    '/': (a, b) => Math.trunc(a / b),
  };
  for (const t of tokens) {
    if (t in ops) {
      const b = st.pop(), a = st.pop();
      st.push(ops[t](a, b));
    } else st.push(Number(t));
  }
  return st.pop();
}

def eval_postfix(tokens):
    st = []
    ops = {
        '+': lambda a, b: a + b,
        '-': lambda a, b: a - b,
        '*': lambda a, b: a * b,
        '/': lambda a, b: int(a / b),  # truncate toward zero
    }
    for t in tokens:
        if t in ops:
            b = st.pop()
            a = st.pop()
            st.append(ops[t](a, b))
        else:
            st.append(int(t))
    return st[-1]

Complexity: O(n) time, O(n) space.

Pitfall: Operand order. The second value popped is the left operand. a - b and b - a differ — get the order wrong and subtraction/division silently break.

3. Undo / redo

Editors keep two stacks: an undo stack of past actions and a redo stack. Doing an action pushes it on undo and clears redo. Undo pops from undo and pushes onto redo; redo does the reverse.

#include <stack>
#include <string>
struct History {
    std::stack<std::string> undo, redo;
    void doAction(const std::string& a) { undo.push(a); while(!redo.empty()) redo.pop(); }
    void undoAction() { if (!undo.empty()) { redo.push(undo.top()); undo.pop(); } }
    void redoAction() { if (!redo.empty()) { undo.push(redo.top()); redo.pop(); } }
};

import java.util.*;
class History {
    Deque<String> undo = new ArrayDeque<>(), redo = new ArrayDeque<>();
    void doAction(String a) { undo.push(a); redo.clear(); }
    void undoAction() { if (!undo.isEmpty()) redo.push(undo.pop()); }
    void redoAction() { if (!redo.isEmpty()) undo.push(redo.pop()); }
}

class History {
  constructor() { this.undo = []; this.redo = []; }
  doAction(a) { this.undo.push(a); this.redo = []; }
  undoAction() { if (this.undo.length) this.redo.push(this.undo.pop()); }
  redoAction() { if (this.redo.length) this.undo.push(this.redo.pop()); }
}

class History:
    def __init__(self):
        self.undo, self.redo = [], []
    def do_action(self, a):
        self.undo.append(a)
        self.redo.clear()
    def undo_action(self):
        if self.undo:
            self.redo.append(self.undo.pop())
    def redo_action(self):
        if self.redo:
            self.undo.append(self.redo.pop())

Each operation is O(1).

Why clear redo on a new action? Once you branch off in a new direction, the old “future” no longer makes sense — that’s exactly how every real editor behaves.

Other places stacks shine

Infix → postfix conversion (the shunting-yard algorithm).
Iterative DFS on trees and graphs.
Monotonic stack problems like next-greater-element — see monotonic stack.

Practice these on the stacks & queues exercises, or move on to queues.