Minimal, copy-paste C++ for parentheses matching, expression evaluation, nested structures, and monotonic stack.

Contents

Parentheses Matching

Use stack’s LIFO property to match opening and closing brackets in reverse order.

def is_valid_parentheses(s: str) -> bool:
    st: list[str] = []
    closing = {")": "(", "]": "[", "}": "{"}
    for c in s:
        if c in "({[":
            st.append(c)
        else:
            if not st or st[-1] != closing[c]:
                return False
            st.pop()
    return not st
ID Title Link Solution
20 Valid Parentheses Link Solution
921 Minimum Add to Make Valid Parentheses Link Solution
1249 Minimum Remove to Make Valid Parentheses Link Solution

Expression Evaluation

Use stack to handle operator precedence and parentheses in mathematical expressions.

def calculate_basic(s: str) -> int:
    stk: list[int] = []
    result = num = 0
    sign = 1
    for c in s:
        if c.isdigit():
            num = num * 10 + int(c)
        elif c in "+-":
            result += sign * num
            num = 0
            sign = 1 if c == "+" else -1
        elif c == "(":
            stk.append(result)
            stk.append(sign)
            result = num = 0
            sign = 1
        elif c == ")":
            result += sign * num
            num = 0
            result *= stk.pop()
            result += stk.pop()
    return result + sign * num
ID Title Link Solution
150 Evaluate Reverse Polish Notation Link Solution
224 Basic Calculator Link Solution
227 Basic Calculator II Link Solution
772 Basic Calculator III Link Solution

Nested Structure Processing

Use stack to process nested structures like strings, expressions, or function calls.

def decode_string(s: str) -> str:
    stack: list = []
    cur = ""
    k = 0
    for c in s:
        if c.isdigit():
            k = k * 10 + int(c)
        elif c == "[":
            stack.append(cur)
            stack.append(k)
            cur, k = "", 0
        elif c == "]":
            repeat = stack.pop()
            prev = stack.pop()
            cur = prev + cur * repeat
        else:
            cur += c
    return cur
ID Title Link Solution
394 Decode String Link Solution
636 Exclusive Time of Functions Link Solution
71 Simplify Path Link -

Monotonic Stack

Maintain a stack with elements in monotonic order (increasing or decreasing) to efficiently find next/previous greater/smaller elements.

def next_greater_elements(nums: list[int]) -> list[int]:
    n = len(nums)
    result = [-1] * n
    st: list[int] = []
    for i in range(n):
        while st and nums[st[-1]] < nums[i]:
            result[st.pop()] = nums[i]
        st.append(i)
    return result
ID Title Link Solution
42 Trapping Rain Water Link Solution
84 Largest Rectangle in Histogram Link Solution
239 Sliding Window Maximum Link Solution
496 Next Greater Element I Link Solution
503 Next Greater Element II Link Solution
316 Remove Duplicate Letters Link Solution
1944 Visible People in Queue Link Solution

Stack for State Management

Use stack to save and restore state when processing nested or hierarchical structures.

# Example: exclusive time of functions (simplified)
def exclusive_time(n: int, logs: list[str]) -> list[int]:
    res = [0] * n
    st: list[tuple[int, int]] = []  # (func_id, start_time)
    for log in logs:
        parts = log.split(":")
        fid, typ, t = int(parts[0]), parts[1], int(parts[2])
        if typ == "start":
            st.append((fid, t))
        else:
            fid, start = st.pop()
            duration = t - start + 1
            res[fid] += duration
            if st:
                res[st[-1][0]] -= duration
    return res
ID Title Link Solution
636 Exclusive Time of Functions Link Solution
394 Decode String Link Solution

Stack Design (Min/Max Stack)

Maintaining extra information (like minimums or frequencies) alongside the primary stack data.

class MinStack:
    def __init__(self) -> None:
        self.stk: list[int] = []
        self.min_stk: list[int] = []

    def push(self, val: int) -> None:
        self.stk.append(val)
        self.min_stk.append(val if not self.min_stk else min(val, self.min_stk[-1]))

    def pop(self) -> None:
        self.stk.pop()
        self.min_stk.pop()

    def top(self) -> int:
        return self.stk[-1]

    def getMin(self) -> int:
        return self.min_stk[-1]
ID Title Link Solution
155 Min Stack Link Solution
716 Max Stack Link -

Key Patterns

  1. LIFO Property: Stack naturally handles reverse-order matching (parentheses, brackets)
  2. State Preservation: Save state before entering nested structures, restore after exiting
  3. Operator Precedence: Use stack to defer low-precedence operations
  4. Monotonic Order: Maintain sorted order to efficiently find extrema
  5. Index Tracking: Store indices instead of values when you need position information

When to Use Stack

  • ✅ Matching problems (parentheses, brackets, tags)
  • ✅ Expression evaluation with precedence
  • ✅ Nested structure processing
  • ✅ Finding next/previous greater/smaller elements
  • ✅ Reversing order or processing in reverse
  • ✅ Undo/redo functionality
  • ✅ Function call tracking

Common Mistakes

  1. Forgetting to check empty stack before st.top() or st.pop()
  2. Wrong stack order when pushing/popping multiple values
  3. Not resetting state after processing elements
  4. Index vs value confusion in monotonic stack problems

More templates