🧠 12.11 Stack in Action: Solving the Valid Parentheses Problem Using Python

Stacks are more than just abstract concepts — they solve real programming challenges! One classic example is checking whether an expression with brackets or parentheses is valid. This blog walks you through how a stack can help solve the Valid Parentheses problem using Python.

---

🔎 Problem Statement

Given a string containing brackets like (), {}, and [], determine whether the brackets are balanced and properly nested.

Examples:

• "(a+b)" → Valid
• "(a+b]*(c-d)" → Invalid
• "[{()}]" → Valid
• "[(])" → Invalid

---

🧰 Why Use a Stack?

Stacks work perfectly for this problem because of their LIFO nature. We push opening brackets onto the stack and pop them when a matching closing bracket is found.

🧮 Logic:

• Traverse the string character by character.
• Push all opening brackets ( { [ onto the stack.
• On encountering a closing bracket ) } ]:
  • Check if the stack is empty → Invalid.
  • Pop from the stack and check if it matches the current closing bracket.
• After the loop, if the stack is empty → Valid. Else → Invalid.

---

🧪 Python Implementation

def is_valid_parentheses(expr):
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}

    for ch in expr:
        if ch in '([{':
            stack.append(ch)
        elif ch in ')]}':
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()

    return len(stack) == 0

# Test Cases
print(is_valid_parentheses("([]{})"))       # ✅ True
print(is_valid_parentheses("([)]"))         # ❌ False
print(is_valid_parentheses("{[()()]}"))     # ✅ True
print(is_valid_parentheses("((())"))        # ❌ False

💡 Output:

True
False
True
False

---

🧾 Summary Table: Valid Parentheses Logic

Step	Action
Read opening bracket	Push onto stack
Read closing bracket	Check if it matches top of stack; if yes, pop it
Mismatch or empty stack during check	Invalid expression
After complete traversal	If stack is empty → Valid; else → Invalid

---

📌 Real-World Use Cases of Stack

• Undo feature in editors (Notepad, Word, etc.)
• Browser history navigation
• Syntax validation in compilers
• Function call tracking in recursion

---

📝 Summary

• Stack helps solve problems where tracking last-in elements is essential.
• Valid parentheses checking uses push and pop logic smartly.
• Python list methods like append() and pop() make stack implementation easy.

---

💡 Tip: Stack is one of the most powerful tools in your algorithm toolbox. Practice problems like parentheses check, infix-to-postfix conversion, and more!

Keep stacking knowledge, and you’ll balance all your brackets like a pro! 🚀📚