47:"/_next/static/chunks/33yus346z0l_n.js" 48:"/_next/static/chunks/1r8ezocsukqp8.js" 49:"/_next/static/chunks/0iv56yrji_20j.js" 4a:"/_next/static/chunks/0wa9m1-tphf9u.js" 4b:"/_next/static/chunks/08cuqqn_f60pp.js" 4c:"/_next/static/chunks/3zdsl3f9b0--r.js" 4d:"/_next/static/chunks/2j22cxchii_xx.js" 4e:"/_next/static/chunks/3bgoyiso1rhn7.js" 4f:"/_next/static/chunks/01a-3hvnqu8wl.js" 50:"/_next/static/chunks/3m1xjj5kw5fie.js" 51:"/_next/static/chunks/0om3fkgfnicab.js" 52:"/_next/static/chunks/0gafyzg9j9yqj.js" 53:"/_next/static/chunks/20w4eaqlekefm.js" 54:"/_next/static/chunks/449--h5z1s6nq.js" 55:"/_next/static/chunks/3k2gyg36fnag_.js" 56:"/_next/static/chunks/18ggtgz2yf759.js" 57:"/_next/static/chunks/0hlb44ca7-4a2.js" 58:"/_next/static/chunks/253gnmj0-cj17.js" 59:"/_next/static/chunks/09nq57stwzkgf.js" 5a:"/_next/static/chunks/082jo-0ajazgr.js" 5b:"/_next/static/chunks/2ozcrjb_hh74t.js" 5c:"/_next/static/chunks/05i8en-x14ibi.js" 5d:"/_next/static/chunks/32izpn90gvm22.js" 5e:"/_next/static/chunks/0jbzid2v9xv3h.js" 5f:"/_next/static/chunks/0i3-eynrkvqi7.js" 60:"/_next/static/chunks/1tn-0fivsxsv1.js" 61:"/_next/static/chunks/34h36hyf_ggow.js" 62:"/_next/static/chunks/20329i6m_04t6.js" 63:"/_next/static/chunks/161uxd62cjny2.js" 64:"/_next/static/chunks/2k8pepwc4pxns.js" 65:I[593304,["$2c","$2d","$2e","$2f","$30","$31","$47","$48","$49","$4a","$4b","$4c","$4d","$4e","$4f","$50","$51","$52","$53","$54","$55","$56","$57","$58","$59","$5a","$5b","$5c","$5d","$5e","$5f","$60","$61","$62","$63","$64"],"OwnedHydration"] 66:T427,import java.util.Stack; public class BalancedParentheses { /** * Check if a string has balanced parentheses (single type: '(' and ')'). * * Time Complexity: O(n) - single pass through the string * Space Complexity: O(n) - stack can hold up to n/2 opening brackets */ public static boolean isBalancedSingle(String s) { Stack stack = new Stack<>(); for (char c : s.toCharArray()) { if (c == '(') { // Opening bracket: push onto stack stack.push(c); } else if (c == ')') { // Closing bracket: need a matching opener if (stack.isEmpty()) { // No opener available - unbalanced return false; } // Pop the matching opener stack.pop(); } // Other characters are ignored for balance checking } // Stack must be empty for perfect balance return stack.isEmpty(); } }67:T538,def is_balanced_multi(s: str) -> bool: """ Check if a string has balanced brackets of multiple types. Supports: (), [], {} Time Complexity: O(n) - single pass Space Complexity: O(n) - stack space in worst case The key insight: we must verify that closing brackets match the MOST RECENT opening bracket, not just any opening bracket. """ stack = [] # Mapping from closing to opening brackets bracket_pairs = { ')': '(', ']': '[', '}': '{' } # Set of opening brackets for quick lookup opening_brackets = set(bracket_pairs.values()) for char in s: if char in opening_brackets: # It's an opener - push to stack stack.append(char) elif char in bracket_pairs: # It's a closer - need matching opener if not stack: # No opener available return False # Check if top of stack matches this closer expected_opener = bracket_pairs[char] if stack[-1] != expected_opener: # Wrong type of opener on top return False # Match found - pop the opener stack.pop() # Other characters are ignored return len(stack) == 068:T578,function isBalancedMulti(s: string): boolean { /** * Check if a string has balanced brackets of multiple types. * Supports: (), [], {} * * Time Complexity: O(n) - single pass * Space Complexity: O(n) - stack space in worst case */ const stack: string[] = []; // Mapping from closing to opening brackets const bracketPairs: Record = { ')': '(', ']': '[', '}': '{' }; // Set of opening brackets for quick lookup const openingBrackets = new Set(Object.values(bracketPairs)); for (const char of s) { if (openingBrackets.has(char)) { // It's an opener - push to stack stack.push(char); } else if (char in bracketPairs) { // It's a closer - need matching opener if (stack.length === 0) { // No opener available return false; } // Check if top of stack matches this closer const expectedOpener = bracketPairs[char]; if (stack[stack.length - 1] !== expectedOpener) { // Wrong type of opener on top return false; } // Match found - pop the opener stack.pop(); } // Other characters are ignored } return stack.length === 0; }69:T4b1,Understanding *why* an algorithm works—not just *that* it works—distinguishes deep comprehension from rote memorization. Let's prove the correctness of our balanced parentheses algorithm. **Claim:** The algorithm returns `true` if and only if the string is balanced. **Proof Strategy:** We'll prove both directions: 1. If the string is balanced → algorithm returns `true` 2. If algorithm returns `true` → the string is balanced **Part 1: Balanced String → Algorithm Returns True** If a string is balanced: - Every opener has exactly one matching closer - The closer appears after the opener - No other opener between them remains unmatched when the closer appears By structural induction on balanced strings: - **Base case:** Empty string → no characters processed → stack stays empty → returns `true` ✓ - **Inductive case:** If `S` is balanced, consider how it's structured: - `S = (A)` where `A` is balanced: Push `(`, process `A` (by induction, stack back to original), pop for `)`. Stack restored → balanced ✓ - `S = AB` where `A`, `B` are balanced: Process `A` (stack empty by induction), process `B` (stack empty by induction). Result: empty stack → balanced ✓6a:T4b2,# Comprehensive edge case tests def test_balanced_parentheses(): # Basic valid cases assert is_balanced_multi("") == True # Empty string assert is_balanced_multi("()") == True # Simple pair assert is_balanced_multi("()[]{}") == True # Multiple types assert is_balanced_multi("{[()]}") == True # Nested assert is_balanced_multi("abc") == True # No brackets # Basic invalid cases assert is_balanced_multi("(") == False # Single opener assert is_balanced_multi(")") == False # Single closer assert is_balanced_multi(")(") == False # Wrong order assert is_balanced_multi("([)]") == False # Interleaved assert is_balanced_multi("{[(])}") == False # Complex interleave # Edge cases assert is_balanced_multi("((((((((((") == False # All openers assert is_balanced_multi("))))))))))") == False # All closers assert is_balanced_multi("a(b)c[d]e{f}g") == True # With other chars # Stress test: deeply nested deep_nested = "(" * 1000 + ")" * 1000 assert is_balanced_multi(deep_nested) == True print("All tests passed!") test_balanced_parentheses()46:["$","$L65",null,{"owner":"anonymous","state":{"mutations":[],"queries":[{"dehydratedAt":1792315812735,"state":{"data":{"json":{"id":"seed_75e0268ae558afd4cbd072034800bfb5","slug":"parentheses-matching-expression-problems","category":"Data Structures & Algorithms","topic":"Parentheses Matching & Expression Problems","title":"Parentheses Matching & Expression Problems","description":"Master the classic stack applications of bracket matching and expression handling. Learn how stacks naturally solve nesting problems, validate syntactic structures, and form the backbone of expression parsing in compilers, interpreters, and calculators.","difficulty":"INTERMEDIATE","estimatedMinutes":60,"pages":[{"id":"seed_a84b732174304740fd06e1a70abc64a1","title":"Balanced Parentheses Checking","order":0,"content":[{"id":"opening-hook","title":"The Nesting Problem","content":[{"data":{"content":"Every programmer has experienced the frustration of a mismatched parenthesis. You're deep into a complex expression, confident in your logic, only to be greeted by a cryptic compiler error: **\"Unexpected token ')'\"** or **\"Missing closing delimiter\"**. Hours of debugging can ensue, all because of a single misplaced bracket.\n\nThis seemingly simple problem—determining whether every opening bracket has a matching closing bracket in the correct order—lies at the heart of programming language design, compiler construction, and text processing. And remarkably, its elegant solution is also one of the most beautiful applications of the stack data structure.\n\nIn this page, we'll explore why parentheses matching is fundamentally a **nesting problem**, why stacks are the perfect data structure to solve it, and how this pattern extends to real-world applications far beyond simple bracket counting."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"By the end of this page, you will understand why balanced parentheses checking is a foundational stack application, master the algorithm for single and multiple bracket types, recognize the invariants that make the solution correct, and see how this pattern manifests in real-world systems like compilers, interpreters, and IDEs.","variant":"info"},"type":"callout"}]},{"id":"understanding-the-problem","title":"Understanding the Balanced Parentheses Problem","content":[{"data":{"content":"Before we dive into solutions, let's rigorously define what \"balanced\" means. This precision matters because ambiguous problem definitions lead to incorrect solutions.\n\n**Definition:** A string containing parentheses (and potentially other characters) is **balanced** if and only if:\n\n1. **Every opening bracket has a corresponding closing bracket** — No opener is left unmatched\n2. **Every closing bracket has a corresponding opening bracket** — No closer appears before its opener\n3. **Brackets are properly nested** — If bracket A opens, and bracket B opens inside A, then B must close before A closes\n\nThe third condition is subtle but critical. It distinguishes proper nesting from mere counting."},"type":"text"},{"data":{"left":[{"data":{"items":["`()` — Simple matching pair","`(())` — Nested pairs","`()()` — Sequential pairs","`((()))` — Deeply nested","`(()())` — Mixed nesting","`a(b(c)d)e` — With other characters","Empty string — Vacuously balanced"],"title":{"icon":"CheckCircle","text":"Valid (Balanced)","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}],"right":[{"data":{"items":["`)` — Closer without opener","`(` — Opener without closer","`)(` — Wrong order","`(()` — Missing closer","`())` — Extra closer","`(()(` — Complex imbalance"],"title":{"icon":"XCircle","text":"Invalid (Unbalanced)","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"accent"},"type":"list"}]},"type":"two-column"},{"data":{"icon":"AlertCircle","title":"The Counting Trap","content":"A naive approach might count opening and closing brackets and check if they're equal. But consider `)(` — it has equal counts (one each) yet is clearly unbalanced. The **order** matters as much as the **count**. This is why a stack is necessary, not just a counter.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":1},{"id":"why-stacks","title":"Why Stacks Are the Natural Solution","content":[{"data":{"content":"The balanced parentheses problem has a beautiful structural property: **the most recently opened bracket must be the first one closed**. This is the LIFO principle incarnate.\n\n**The key insight:** When you encounter a closing bracket, you need to know what the most recent unmatched opening bracket was. If they match, great—discard both and continue. If they don't match, the string is invalid.\n\nA stack naturally tracks this \"most recent unmatched opener\" because:\n- When you see an opening bracket, you **push** it onto the stack\n- When you see a closing bracket, you **pop** the stack and check for a match\n- If the stack is empty when you try to pop, there's no opener to match\n- If the stack is non-empty after processing all characters, there are unmatched openers"},"type":"text"},{"data":{"content":"**Visualizing the Process:**\n\nConsider the string `(())`:\n\n```\nPosition 0: '(' → Push '(' → Stack: ['(']\nPosition 1: '(' → Push '(' → Stack: ['(', '(']\nPosition 2: ')' → Pop '(' → Match! Stack: ['(']\nPosition 3: ')' → Pop '(' → Match! Stack: []\n\nEnd of string, stack empty → BALANCED ✓\n```\n\nNow consider the invalid string `())`:\n\n```\nPosition 0: '(' → Push '(' → Stack: ['(']\nPosition 1: ')' → Pop '(' → Match! Stack: []\nPosition 2: ')' → Pop ???? → Stack empty! No opener to match\n\n→ UNBALANCED ✗\n```"},"type":"text"},{"data":{"icon":"Lightbulb","title":"The Invariant Principle","content":"At every step, the stack contains exactly the unmatched opening brackets, in the order they appeared. The top of the stack is always the most recent unmatched opener. This invariant is maintained by pushing openers and popping on closers. When we finish, an empty stack means perfect balance.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":2},{"id":"single-bracket-algorithm","title":"The Algorithm: Single Bracket Type","content":[{"data":{"content":"Let's formalize the algorithm for strings containing only `(` and `)`. This simplified version captures the core logic before we extend to multiple bracket types.\n\n**Algorithm: Single Bracket Balance Check**\n\n1. Initialize an empty stack\n2. For each character in the string:\n - If it's `(`, push it onto the stack\n - If it's `)`, check if the stack is empty:\n - If empty: return `false` (unmatched closer)\n - If not empty: pop the stack (the match is consumed)\n - If it's any other character: skip (or process as needed)\n3. After processing all characters:\n - If stack is empty: return `true` (balanced)\n - If stack is non-empty: return `false` (unmatched openers)"},"type":"text"},{"data":{"fileName":"balanced_single.py","languages":[{"code":"def is_balanced_single(s: str) -> bool:\n \"\"\"\n Check if a string has balanced parentheses (single type: '(' and ')').\n \n Time Complexity: O(n) - single pass through the string\n Space Complexity: O(n) - stack can hold up to n/2 opening brackets\n \n Args:\n s: The input string to check\n \n Returns:\n True if parentheses are balanced, False otherwise\n \"\"\"\n stack = []\n \n for char in s:\n if char == '(':\n # Opening bracket: push onto stack\n stack.append(char)\n elif char == ')':\n # Closing bracket: need a matching opener\n if not stack:\n # No opener available - unbalanced\n return False\n # Pop the matching opener\n stack.pop()\n # Other characters are ignored for balance checking\n \n # Stack must be empty for perfect balance\n return len(stack) == 0","label":"Python","value":"python"},{"code":"function isBalancedSingle(s: string): boolean {\n /**\n * Check if a string has balanced parentheses (single type: '(' and ')').\n * \n * Time Complexity: O(n) - single pass through the string\n * Space Complexity: O(n) - stack can hold up to n/2 opening brackets\n */\n const stack: string[] = [];\n \n for (const char of s) {\n if (char === '(') {\n // Opening bracket: push onto stack\n stack.push(char);\n } else if (char === ')') {\n // Closing bracket: need a matching opener\n if (stack.length === 0) {\n // No opener available - unbalanced\n return false;\n }\n // Pop the matching opener\n stack.pop();\n }\n // Other characters are ignored for balance checking\n }\n \n // Stack must be empty for perfect balance\n return stack.length === 0;\n}","label":"TypeScript","value":"typescript"},{"code":"$66","label":"Java","value":"java"}]},"type":"code"},{"data":{"content":"**Optimization Note:** For the single bracket type problem, we can actually use a simple counter instead of a full stack. Since there's only one type of bracket, we don't need to remember *which* bracket is on top—just *how many* unmatched openers there are.\n\nHowever, the stack-based solution is more general and extends naturally to multiple bracket types, which is why we present it first."},"type":"text"},{"data":{"fileName":"balanced_counter.py","languages":[{"code":"def is_balanced_counter(s: str) -> bool:\n \"\"\"\n Optimized version using a counter instead of a stack.\n Only works for single bracket type!\n \n Time Complexity: O(n)\n Space Complexity: O(1) - just a counter, no stack needed\n \"\"\"\n counter = 0\n \n for char in s:\n if char == '(':\n counter += 1\n elif char == ')':\n if counter == 0:\n return False # No opener to match\n counter -= 1\n \n return counter == 0","label":"Python","value":"python"}]},"type":"code"}],"titleType":"number","titleNumber":3},{"id":"multiple-bracket-types","title":"Extending to Multiple Bracket Types","content":[{"data":{"content":"Real-world applications rarely involve just one type of bracket. Programming languages use `()`, `[]`, and `{}`, sometimes with distinct semantic meanings. HTML uses `` and ``. The generalized problem requires that:\n\n1. Each bracket type must be balanced independently\n2. Brackets must be **properly nested** — you can't have `([)]` (interleaving)\n\n**The key extension:** When we encounter a closing bracket, we don't just check if *any* opener is available—we check if the *matching* opener is on top of the stack. This is why we need a stack (storing the actual characters) rather than just a counter.\n\nConsider these examples with mixed brackets:\n\n- `([])` — Valid: `[` opens inside `()`, closes before `)`\n- `([)]` — Invalid: `[` opens inside `()`, but `)` tries to close before `]`\n- `{[()]}` — Valid: perfectly nested triple brackets\n- `{[(])}` — Invalid: improper nesting"},"type":"text"},{"data":{"fileName":"balanced_multi.py","languages":[{"code":"$67","label":"Python","value":"python"},{"code":"$68","label":"TypeScript","value":"typescript"}]},"type":"code"},{"data":{"icon":"AlertCircle","title":"The Interleaving Problem","content":"The string `([)]` has equal counts of all brackets and each type is individually 'matched' in count. But it's invalid because the nesting is wrong. When we see `)`, the top of stack is `[`, not `(`. This mismatch instantly reveals the interleaving error. Without a stack tracking the actual characters, we couldn't detect this.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":4},{"id":"detailed-walkthrough","title":"Detailed Algorithm Walkthrough","content":[{"data":{"content":"Let's trace through the algorithm step-by-step for several examples to build deep intuition.\n\n**Example 1: `{[()]}`** (Valid)"},"type":"text"},{"data":{"rows":[["0","Initial","—","[]","Start"],["1","{","Push '{'","['{']","Continue"],["2","[","Push '['","['{', '[']","Continue"],["3","(","Push '('","['{', '[', '(']","Continue"],["4",")","Pop, check '(' matches ')'","['{', '[']","Match ✓"],["5","]","Pop, check '[' matches ']'","['{']","Match ✓"],["6","}","Pop, check '{' matches '}'","[]","Match ✓"],["7","End","Check stack empty","[]","✅ BALANCED"]],"caption":"Trace for {[()]} - Valid","headers":["Step","Character","Action","Stack After","Status"]},"type":"table"},{"data":{"content":"**Example 2: `([)]`** (Invalid - Interleaving)"},"type":"text"},{"data":{"rows":[["0","Initial","—","[]","Start"],["1","(","Push '('","['(']","Continue"],["2","[","Push '['","['(', '[']","Continue"],["3",")","Pop, check '[' matches ')'","—","❌ MISMATCH!"]],"caption":"Trace for ([)] - Invalid","headers":["Step","Character","Action","Stack After","Status"]},"type":"table"},{"data":{"content":"The algorithm correctly identifies the failure at step 3. When we encounter `)`, the top of stack is `[`, not `(`. The brackets are interleaved, not properly nested.\n\n**Example 3: `(((`** (Invalid - Unclosed)"},"type":"text"},{"data":{"rows":[["0","Initial","—","[]","Start"],["1","(","Push '('","['(']","Continue"],["2","(","Push '('","['(', '(']","Continue"],["3","(","Push '('","['(', '(', '(']","Continue"],["4","End","Check stack empty","['(', '(', '(']","❌ Non-empty!"]],"caption":"Trace for ((( - Invalid","headers":["Step","Character","Action","Stack After","Status"]},"type":"table"},{"data":{"content":"At the end, three unmatched openers remain on the stack, indicating the string is unbalanced."},"type":"text"}],"titleType":"number","titleNumber":5},{"id":"correctness-proof","title":"Why the Algorithm Is Correct","content":[{"data":{"content":"$69"},"type":"text"},{"data":{"content":"**Part 2: Algorithm Returns True → String Is Balanced**\n\nContrapositive: If string is *not* balanced, algorithm returns `false`.\n\nAn unbalanced string has one of these issues:\n1. **More closers than openers at some point** — Algorithm returns `false` when popping empty stack\n2. **More openers than closers total** — Stack non-empty at end → returns `false`\n3. **Mismatched bracket types** — Pop mismatch detected → returns `false`\n\nEach failure mode is correctly identified by the algorithm. ∎\n\n**The Invariant:**\n\nThe key proof technique involves the **loop invariant**: At each step, the stack contains exactly the unmatched opening brackets seen so far, in order. This invariant is established at initialization (empty stack, no characters seen) and preserved by each iteration (push adds an unmatched opener, pop removes a matched pair)."},"type":"text"},{"data":{"icon":"Info","title":"Why Proofs Matter","content":"Understanding the correctness proof gives you confidence when extending or modifying the algorithm. If you need to handle new bracket types, escaped characters, or special rules, you can reason about whether your changes preserve the invariant rather than just hoping they work.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":6},{"id":"complexity-analysis","title":"Complexity Analysis","content":[{"data":{"content":"**Time Complexity: O(n)**\n\nWe make a single pass through the string of length `n`. Each character is processed in O(1) time:\n- Character lookup for bracket type: O(1)\n- Stack push: O(1)\n- Stack pop: O(1)\n- Comparison: O(1)\n\nTotal: O(n) operations.\n\n**Space Complexity: O(n)**\n\nIn the worst case, the entire string consists of opening brackets (e.g., `((((((((((`). Each opening bracket is pushed onto the stack, resulting in a stack of size n.\n\nIn practice, for typical inputs with balanced or nearly-balanced brackets, the stack size is proportional to the maximum nesting depth, which is often much smaller than n."},"type":"text"},{"data":{"rows":[["Empty string","0","O(1)","O(1)"],["Perfectly balanced `()()()`","1 (max)","O(n)","O(1)"],["Deeply nested `(((...)))`","n/2","O(n)","O(n)"],["All openers `(((((...`","n","O(n)","O(n)"],["All closers `)))...`","0","O(1)*","O(1)"]],"caption":"Complexity Summary","headers":["Input Pattern","Stack Size","Time","Space"]},"type":"table"},{"data":{"content":"*For all closers: fails on first character, so effective O(1) time.\n\n**Can we do better than O(n) space?**\n\nFor the *general* multiple bracket type problem: No, we need to remember the order of different bracket types.\n\nFor the *single* bracket type problem: Yes! We can use a counter (O(1) space) as shown earlier.\n\n**Early Termination:**\n\nNote that the algorithm can terminate early (before scanning the full string) in two cases:\n1. A closing bracket with no matching opener (return `false` immediately)\n2. A mismatched bracket type (return `false` immediately)\n\nThis is an important practical optimization—we don't waste time scanning the rest of a clearly invalid string."},"type":"text"}],"titleType":"number","titleNumber":7},{"id":"real-world-applications","title":"Real-World Applications","content":[{"data":{"content":"Balanced parentheses checking isn't just an academic exercise—it's a fundamental operation in countless software systems. Here are some of the most important applications:"},"type":"text"},{"data":{"items":["**Compilers and Interpreters** — Before any semantic analysis, compilers verify that all brackets, braces, and parentheses are balanced. An unbalanced source file cannot possibly be valid code. This check happens in the lexer/parser pipeline.","**IDE Syntax Highlighting** — Modern IDEs highlight matching brackets in real-time as you type. They use stack-based algorithms to find the matching bracket for your cursor position. Try pressing `Ctrl+Shift+\\` in VS Code to jump to a matching bracket.","**JSON/XML Validators** — Structured data formats require properly nested delimiters. JSON validators check matching `{}` and `[]`. XML validators check matching `` and `` pairs.","**Mathematical Expression Validators** — Calculators and formula editors verify that mathematical expressions have balanced parentheses before attempting to evaluate them.","**Regular Expression Engines** — Regex patterns use parentheses for grouping. The regex engine must validate that groups are properly formed before compiling the pattern.","**HTML/Template Linters** — Web development tools validate that HTML tags are properly nested. An unclosed `

` or mismatched `` indicates a bug."],"title":{"icon":"Zap","text":"Critical Applications","type":"icon","color":"primary","variant":"outline-circle"},"variant":"glass"},"type":"list"},{"data":{"icon":"Lightbulb","title":"The Compiler Pipeline","content":"In a typical compiler, bracket matching happens during lexical analysis (tokenization). The lexer produces a stream of tokens, and the parser uses a stack to verify that bracket tokens are properly nested. If they're not, a syntax error is reported before any semantic analysis begins.","variant":"tip"},"type":"callout"},{"data":{"content":"**Production-Grade Considerations:**\n\nReal applications extend the basic algorithm in several ways:\n\n1. **Error Reporting:** Instead of just returning true/false, provide meaningful error messages:\n - Line number and column of the mismatch\n - The expected vs. actual bracket type\n - Suggestions for fixes\n\n2. **Real-Time Checking:** IDEs perform bracket matching incrementally as you type, not on the entire file every time\n\n3. **Context Sensitivity:** Some languages have context-dependent delimiters (e.g., `<>` in C++ templates vs. comparison operators)\n\n4. **Performance at Scale:** For very large files, optimized data structures and parallel processing may be employed"},"type":"text"}],"titleType":"number","titleNumber":8},{"id":"common-mistakes","title":"Common Mistakes and Edge Cases","content":[{"data":{"content":"Even though the algorithm is straightforward, there are several common mistakes and edge cases that trip up developers:"},"type":"text"},{"data":{"items":["**Forgetting to check if stack is empty before popping** — This causes a runtime error (stack underflow). Always check `stack.isEmpty()` or `len(stack) > 0` before popping.","**Only checking counts, not order** — `)(` has equal counts but is unbalanced. You must use a stack to track order.","**Not handling non-bracket characters** — If the input can contain letters, numbers, or other characters, make sure they're properly ignored (or processed as required).","**Confusing opening and closing brackets in the map** — Double-check that your bracket pairs map closers to openers (for lookup) or openers to closers (for validation), and use the correct direction.","**Returning early on match instead of continuing** — A match means you pop and continue, not return true immediately."],"title":{"icon":"AlertCircle","text":"Common Mistakes","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"items":["**Empty string** — Vacuously balanced. Stack stays empty, return `true`.","**Single character** — If it's an opener, unbalanced (stack non-empty). If it's a closer, unbalanced (pop on empty). If other, balanced.","**All openers** — Stack fills up, remains non-empty at end, unbalanced.","**All closers** — First closer triggers pop on empty stack, unbalanced.","**Only non-bracket characters** — No pushes or pops, stack stays empty, balanced.","**Deeply nested** — Tests stack capacity and recursion depth if implemented recursively."],"title":{"icon":"Target","text":"Critical Edge Cases","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"fileName":"edge_cases_test.py","languages":[{"code":"$6a","label":"Python","value":"python"}]},"type":"code"}],"titleType":"number","titleNumber":9},{"id":"summary","title":"Summary: The Foundation of Bracket Matching","content":[{"data":{"content":"We've thoroughly explored the balanced parentheses problem—one of the most elegant applications of the stack data structure. Let's consolidate what we've learned:"},"type":"text"},{"data":{"type":"ordered","items":["**Balance means nesting, not counting** — Equal counts of openers and closers isn't enough; they must be properly nested so closers match the most recent unmatched opener.","**Stacks naturally solve LIFO matching** — The top of the stack always holds the most recent unmatched opener, which is exactly what we need to check when a closer appears.","**The core algorithm is simple and elegant** — Push openers, pop on closers (checking for match), verify empty stack at end.","**Multiple bracket types require actual character storage** — Unlike the single-type case (counter suffices), we must store which character is on top.","**O(n) time, O(n) space in worst case** — Single pass through the string, stack size bounded by input length.","**Real-world applications abound** — Compilers, IDEs, validators, and countless other tools rely on this pattern."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**What's Next:**\n\nBalanced parentheses checking is just the beginning of stack-based expression problems. In the next page, we'll extend this concept to **valid bracket sequences**, exploring how to generate all valid combinations, count them, and understand the deeper mathematical structure (Catalan numbers) that governs these patterns."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now have a deep understanding of balanced parentheses checking using stacks. This foundational pattern—push on open, pop on close, verify empty at end—appears throughout computer science. Master this, and you've mastered one of the most important stack applications.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":10}],"isLocked":false},{"id":"seed_fdcdcfd027e8ea3c9301ae1cfdc0a21d","title":"Valid Bracket Sequences","order":1,"content":null,"isLocked":true},{"id":"seed_8af764504527902b0f6624230d76613e","title":"Evaluating Postfix Expressions","order":2,"content":null,"isLocked":true},{"id":"seed_0f13d291230e824c9107ef8ddb7a7914","title":"Converting Infix to Postfix (Shunting-Yard Intuition)","order":3,"content":null,"isLocked":true}]}},"dataUpdateCount":1,"dataUpdatedAt":1792315812622,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["learningContent","getModule"],{"input":{"slug":"parentheses-matching-expression-problems"},"type":"query"}],"queryHash":"[[\"learningContent\",\"getModule\"],{\"input\":{\"slug\":\"parentheses-matching-expression-problems\"},\"type\":\"query\"}]"},{"dehydratedAt":1792315812736,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792315812734,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["learningContent","getProgress"],{"input":{"moduleId":"seed_75e0268ae558afd4cbd072034800bfb5"},"type":"query"}],"queryHash":"[[\"learningContent\",\"getProgress\"],{\"input\":{\"moduleId\":\"seed_75e0268ae558afd4cbd072034800bfb5\"},\"type\":\"query\"}]"},{"dehydratedAt":1792315812736,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792315812735,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["feedback","get"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_fdcdcfd027e8ea3c9301ae1cfdc0a21d"},"type":"query"}],"queryHash":"[[\"feedback\",\"get\"],{\"input\":{\"contentId\":\"seed_fdcdcfd027e8ea3c9301ae1cfdc0a21d\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792315812736,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792315812735,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["feedback","getUserLike"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_fdcdcfd027e8ea3c9301ae1cfdc0a21d"},"type":"query"}],"queryHash":"[[\"feedback\",\"getUserLike\"],{\"input\":{\"contentId\":\"seed_fdcdcfd027e8ea3c9301ae1cfdc0a21d\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792315812736,"state":{"data":{"json":[]},"dataUpdateCount":1,"dataUpdatedAt":1792315812735,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["highlights","getHighlights"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_fdcdcfd027e8ea3c9301ae1cfdc0a21d"},"type":"query"}],"queryHash":"[[\"highlights\",\"getHighlights\"],{\"input\":{\"contentId\":\"seed_fdcdcfd027e8ea3c9301ae1cfdc0a21d\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792315812736,"state":{"data":"$undefined","dataUpdateCount":0,"dataUpdatedAt":0,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"pending","fetchStatus":"fetching"},"queryKey":[["highlights","getPopularHighlights"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_fdcdcfd027e8ea3c9301ae1cfdc0a21d","minCount":2},"type":"query"}],"queryHash":"[[\"highlights\",\"getPopularHighlights\"],{\"input\":{\"contentId\":\"seed_fdcdcfd027e8ea3c9301ae1cfdc0a21d\",\"contentType\":\"LEARNING_PAGE\",\"minCount\":2},\"type\":\"query\"}]","promise":"$@6b"}]},"children":"$L6c"}]