Stack Simulation Problems: DSA Guide & Examples

Stack Simulation uses a stack to remember the most recent state and undo it later.

Its core advantage:

Nested dependencies resolve in reverse order of creation — exactly what LIFO gives you for free.

Focus on recognizing:

“Nested” or “undo/history” = Stack Simulation

Pattern Table

Pattern	Typical Questions	Trigger
Matching	Valid Parentheses	Push open, pop-and-check on close
Operand Stack	Evaluate Postfix/RPN	Pop two, apply operator, push back
Directory Stack	Simplify Path	`..` pops, name pushes

Mental Trigger

Open → Push | Close/Undo → Validate then Pop | Process → Repeat.

1. Generic Stack Simulation Template (Base)

Watch "({[]})" validate — each closer pops its matching opener until the stack empties. Press ▶ to animate, or step through manually with the arrows and speed control.

Valid Parentheses

Given a string of brackets, return true if every opener has a matching closer in the correct order. A stack remembers what to match — LIFO resolves innermost first.

Input: "({[]})". Push openers, pop on closers. If the popped opener doesn't match the closer type → invalid. Stack empty at end → valid. Watch the stack grow and shrink at each step.

STACK VISUALIZER

Steps –

TOP ↓

STACK (LIFO)

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        for each char c in s:
                      
                        2
                          if c is an opener '(', '{', '[':
                      
                        3
                            push c
                      
                        4
                          else if stack empty OR top does not match c:
                      
                        5
                            return false
                      
                        6
                          else:  pop the matched opener
                      
                        7
                        return stack is empty

public void simulate(char[] tokens) {
    Deque<Character> stack = new ArrayDeque<>();

    for (char c : tokens) {
        if (/* opens a nested scope */) {
            stack.push(c);
        } else if (/* closes or undoes */) {
            if (stack.isEmpty()) return; // nothing to undo
            char open = stack.pop();
            // validate/process the pair
        }
    }
}

def simulate(tokens: str) -> None:
    stack = []

    for c in tokens:
        if /* opens a nested scope */:
            stack.append(c)
        elif /* closes or undoes */:
            if not stack:
                return  # nothing to undo
            open = stack.pop()
            # validate/process the pair

void simulate(string& tokens) {
    stack<char> st;

    for (char c : tokens) {
        if (/* opens a nested scope */) {
            st.push(c);
        } else if (/* closes or undoes */) {
            if (st.empty()) return; // nothing to undo
            char open = st.top(); st.pop();
            // validate/process the pair
        }
    }
}

function simulate(tokens) {
  const stack = [];

  for (const c of tokens) {
    if (/* opens a nested scope */) {
      stack.push(c);
    } else if (/* closes or undoes */) {
      if (stack.length === 0) return; // nothing to undo
      const open = stack.pop();
      // validate/process the pair
    }
  }
}

Everything else in Stack Simulation is just a modification of this template.

Two rules baked into the base:

Never pop an empty stack — check first.
Leftover state matters — decide what a non-empty stack means at the end.

Pattern 1: Valid Parentheses

The failure path: a closer pops a mismatched opener and bails instantly.

Valid Parentheses — Failure

When a closer doesn't match the popped opener type, return false immediately. No full scan needed.

Input: "(]". Push '(', then encounter ']'. Pop '(' — it's a round bracket, not square. Mismatch detected → invalid.

STACK VISUALIZER

Steps –

TOP ↓

STACK (LIFO)

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        opener → push
                      
                        2
                        closer  → pop must match
                      
                        3
                        end     → stack must be empty

Code

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();

    for (char c : s.toCharArray()) {
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) return false;

            char open = stack.pop();
            if (!matches(open, c)) return false;
        }
    }

    return stack.isEmpty();
}

private boolean matches(char open, char close) {
    return (open == '(' && close == ')') ||
           (open == '{' && close == '}') ||
           (open == '[' && close == ']');
}

MATCH = {')': '(', '}': '{', ']': '['}

def is_valid(s: str) -> bool:
    stack = []

    for c in s:
        if c in "([{":
            stack.append(c)
        else:
            if not stack or stack.pop() != MATCH[c]:
                return False

    return not stack

bool isValid(string s) {
    stack<char> st;
    unordered_map<char, char> match{
        {')', '('}, {'}', '{'}, {']', '['}};

    for (char c : s) {
        if (c == '(' || c == '{' || c == '[') {
            st.push(c);
        } else {
            if (st.empty() || st.top() != match[c])
                return false;

            st.pop();
        }
    }

    return st.empty();
}

function isValid(s) {
  const match = { ")": "(", "}": "{", "]": "[" };
  const stack = [];

  for (const c of s) {
    if (c === "(" || c === "{" || c === "[") {
      stack.push(c);
    } else {
      if (stack.length === 0 || stack.pop() !== match[c])
        return false;
    }
  }

  return stack.length === 0;
}

What Changed from the Base Template?

Match map + final emptiness check

Base:

// validate/process the pair

# validate/process the pair

// validate/process the pair

// validate/process the pair

Changed:

if (!matches(open, c)) return false;
...
return stack.isEmpty();

if stack.pop() != MATCH[c]:
    return False
...
return not stack

if (st.top() != match[c]) return false;
...
return st.empty();

if (stack.pop() !== match[c]) return false;
...
return stack.length === 0;

because a popped opener that doesn’t match means invalid — and leftover openers at the end mean invalid too.

Valid Parentheses = Base Template + Pair matching + Empty-at-end check.

Pattern 2: Evaluate Postfix Expression (RPN)

Numbers push; operators consume two and push one back.

Evaluate Reverse Polish Notation

Evaluate a postfix expression using a stack. Numbers push onto the stack. Each operator pops two operands, applies the operation, and pushes the result.

Tokens: 2, 1, +, 3, *. Push numbers, apply operators. Watch the stack grow and shrink. Final answer is the only item left.

STACK VISUALIZER

Steps –

TOP ↓

STACK (LIFO)

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        for token in tokens:
                      
                        2
                          if number: push(token)
                      
                        3
                          else: b = pop(); a = pop()
                      
                        4
                                push(a OP b)
                      
                        5
                        return stack[0]

The same loop — but the stack holds operands, and an operator pops two and pushes one result.

Code

public int evalRPN(String[] tokens) {
    Stack<Integer> stack = new Stack<>();

    for (String token : tokens) {
        switch (token) {
            case "+" -> stack.push(stack.pop() + stack.pop());
            case "*" -> stack.push(stack.pop() * stack.pop());
            case "-" -> {
                int b = stack.pop(), a = stack.pop();
                stack.push(a - b);
            }
            case "/" -> {
                int b = stack.pop(), a = stack.pop();
                stack.push(a / b);
            }
            default -> stack.push(Integer.parseInt(token));
        }
    }

    return stack.pop();
}

def eval_rpn(tokens: list[str]) -> int:
    stack = []
    ops = {
        "+": lambda a, b: a + b,
        "-": lambda a, b: a - b,
        "*": lambda a, b: a * b,
        "/": lambda a, b: int(a / b),
    }

    for token in tokens:
        if token in ops:
            b = stack.pop()
            a = stack.pop()
            stack.append(ops[token](a, b))
        else:
            stack.append(int(token))

    return stack.pop()

int evalRPN(vector<string>& tokens) {
    stack<long long> st;

    for (string& token : tokens) {
        if (token == "+" || token == "-" ||
            token == "*" || token == "/") {
            long long b = st.top(); st.pop();
            long long a = st.top(); st.pop();

            if (token == "+") st.push(a + b);
            else if (token == "-") st.push(a - b);
            else if (token == "*") st.push(a * b);
            else st.push(a / b);
        } else {
            st.push(stoll(token));
        }
    }

    return st.top();
}

function evalRPN(tokens) {
  const stack = [];
  const ops = {
    "+": (a, b) => a + b,
    "-": (a, b) => a - b,
    "*": (a, b) => a * b,
    "/": (a, b) => Math.trunc(a / b),
  };

  for (const token of tokens) {
    if (token in ops) {
      const b = stack.pop();
      const a = stack.pop();
      stack.push(ops[token](a, b));
    } else {
      stack.push(Number(token));
    }
  }

  return stack.pop();
}

What Changed from the Base Template?

Pop two operands — order matters

Base:

char open = stack.pop();  // pop ONE, validate

open = stack.pop()  # pop ONE, validate

char open = st.top(); st.pop();  // pop ONE, validate

const open = stack.pop(); // pop ONE, validate

Changed:

int b = stack.pop();  // second operand first
int a = stack.pop();  // then the first
stack.push(a op b);

b = stack.pop()
a = stack.pop()
stack.append(a op b)

long long b = st.top(); st.pop();
long long a = st.top(); st.pop();
st.push(a OP b);

const b = stack.pop();
const a = stack.pop();
stack.push(a op b);

because a - b ≠ b - a — the first pop is the right operand.

Postfix Evaluation = Base Template + Operand stack + Pop-two-apply-push.

Pattern 3: Simplify Path

Push descends a directory, ’..’ pops — the stack IS the path depth.

Simplify Path

Given a Unix-style path, simplify it to its canonical form. A stack tracks the directory depth — push descends, '..' pops up.

Path: '/a/./b/../c'. Split on '/'. Push names, skip '.' and empty, pop on '..'. The stack IS the directory depth.

STACK VISUALIZER

Steps –

TOP ↓

STACK (LIFO)

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        parts = path.split('/')
                      
                        2
                        for p in parts:
                      
                        3
                          '.' or ''  → skip
                      
                        4
                          '..'       → pop
                      
                        5
                          else       → push
                      
                        6
                        '/' + join(stack)

Undo semantics: a directory pushes, .. undoes, everything else is ignored.

Code

public String simplifyPath(String path) {
    Stack<String> stack = new Stack<>();

    for (String dir : path.split("/")) {
        if (dir.equals("..")) {
            if (!stack.isEmpty()) stack.pop();
        } else if (!dir.isEmpty() && !dir.equals(".")) {
            stack.push(dir);
        }
    }

    return "/" + String.join("/", stack);
}

def simplify_path(path: str) -> str:
    stack = []

    for part in path.split("/"):
        if part == "..":
            if stack:
                stack.pop()
        elif part and part != ".":
            stack.append(part)

    return "/" + "/".join(stack)

string simplifyPath(string path) {
    stack<string> st;
    stringstream ss(path);
    string dir;

    while (getline(ss, dir, '/')) {
        if (dir == "..") {
            if (!st.empty()) st.pop();
        } else if (!dir.empty() && dir != ".") {
            st.push(dir);
        }
    }

    string result;
    while (!st.empty()) {
        result = "/" + st.top() + result;
        st.pop();
    }
    return result.empty() ? "/" : result;
}

function simplifyPath(path) {
  const stack = [];

  for (const dir of path.split("/")) {
    if (dir === "..") {
      if (stack.length) stack.pop();
    } else if (dir && dir !== ".") {
      stack.push(dir);
    }
  }

  return "/" + stack.join("/");
}

What Changed from the Base Template?

Three-way token handling instead of push/pop pairs

Base:

if (/* opens */) push;
else if (/* closes */) pop;

if /* opens */:
    push
elif /* closes */:
    pop

if (/* opens */) push;
else if (/* closes */) pop;

if (/* opens */) push;
else if (/* closes */) pop;

Changed:

if (dir.equals(".."))       pop;   // undo
else if (!dir.isEmpty()
      && !dir.equals("."))  push;  // keep
// else ignore                     // noise

if part == "..":
    pop           # undo
elif part and part != ".":
    push          # keep
# else ignore     # noise

if (dir == "..")            pop;   // undo
else if (!dir.empty()
      && dir != ".")        push;  // keep
// else ignore                     // noise

if (dir === "..")         pop;   // undo
else if (dir && dir !== ".")
                          push;  // keep
// else ignore                   // noise

because paths contain noise ("", ".") that neither opens nor closes anything.

Simplify Path = Base Template + Undo-on-.. + Ignore-noise + Join survivors.

Stack Simulation Pattern Evolution

Base Stack Simulation
    ↓
Valid Parentheses
    (+ pair matching + empty-at-end check)
    ↓
Postfix Evaluation
    (+ operand stack + pop-two-apply-push)
    ↓
Simplify Path
    (+ undo-on-'..' + ignore noise)

Common Mistakes

Popping without checking.

// Wrong — EmptyStackException on "]"
char open = stack.pop();

// Correct
if (stack.isEmpty()) return false;
char open = stack.pop();

# Wrong — IndexError on "]"
open = stack.pop()

# Correct
if not stack:
    return False
open = stack.pop()

// Wrong — undefined behavior on "]"
char open = st.top();

// Correct
if (st.empty()) return false;
char open = st.top(); st.pop();

// Wrong — silently returns undefined on "]"
const open = stack.pop();

// Correct
if (stack.length === 0) return false;
const open = stack.pop();

Wrong operand order for - and /.

tokens: ["5", "3", "-"] → 5 - 3 = 2, NOT 3 - 5

First pop = b, second pop = a, compute a op b.

Skipping the final emptiness check.

"(((" never hits a mismatch — only the empty-stack check catches it:

return stack.isEmpty();

return not stack

return st.empty();

return stack.length === 0;

Recognition Cheat Sheet

If you see…	Think…
Brackets / nesting validity	Push open, pop-and-match close
Postfix/prefix expression	Operand stack, pop two
File path with `..`	Directory stack, `..` = undo
Undo / history / backtracking state	Push state, pop to revert

⚠️ Animation & Content Notice

Stack Simulation

Pattern Table

Mental Trigger

1. Generic Stack Simulation Template (Base)

⚠️ Animation & Content Notice

Valid Parentheses

Pattern 1: Valid Parentheses

⚠️ Animation & Content Notice

Valid Parentheses — Failure

Code

What Changed from the Base Template?

Match map + final emptiness check

Pattern 2: Evaluate Postfix Expression (RPN)

⚠️ Animation & Content Notice

Evaluate Reverse Polish Notation

Code

What Changed from the Base Template?

Pop two operands — order matters

Pattern 3: Simplify Path

⚠️ Animation & Content Notice

Simplify Path

Code

What Changed from the Base Template?

Three-way token handling instead of push/pop pairs

Stack Simulation Pattern Evolution

Common Mistakes

Recognition Cheat Sheet

Premium Content

My Private Notes

Earn Premium with Referrals

Pattern Table

Mental Trigger

1. Generic Stack Simulation Template (Base)

Valid Parentheses

Pattern 1: Valid Parentheses

Valid Parentheses — Failure

Code

What Changed from the Base Template?

Match map + final emptiness check

Pattern 2: Evaluate Postfix Expression (RPN)

Evaluate Reverse Polish Notation

Code

What Changed from the Base Template?

Pop two operands — order matters

Pattern 3: Simplify Path

Simplify Path

Code

What Changed from the Base Template?

Three-way token handling instead of push/pop pairs

Stack Simulation Pattern Evolution

Common Mistakes

Recognition Cheat Sheet

Premium Content

My Private Notes