DEV Community

Shahrouz Nikseresht
Shahrouz Nikseresht

Posted on

Day 43: Python Valid Parentheses Checker, Stack-Based Bracket Validation with Mapping and Loop Scanning

#challenge #python #intermediate #programming

Welcome to Day 43 of the #80DaysOfChallenges journey! This intermediate challenge focuses on validating if a string has properly matched parentheses using a stack, supporting types like (), {}, [], while ignoring non-bracket characters and running in linear O(n) time. It utilizes dictionary mapping for closing to opening brackets, loop iteration for scanning, and stack operations for tracking opens, a core technique in parsing and algorithm problems. If you're moving from basic strings to data structure applications or preparing for interview classics like balanced brackets, this "Python valid parentheses checker" script illustrates a function that's concise, efficient for long strings, and adaptable to more bracket types or error reporting.

💡 Key Takeaways from Day 43: Valid Parentheses Checker

This task centers on a single function that uses a stack to push opens and pop on closes, with a dict for pair checks. It's a standard stack pattern: push on open, pop and verify on close, empty at end. We'll detail: function with stack and pairs dict, loop for char handling, and main with input and result print.

1. Function Design: Stack and Pairs Mapping

The is_valid function takes a string and returns bool on balance:

def is_valid(s: str) -> bool:
    """
    Validate parentheses using stack logic.
    Returns True if all brackets close correctly.
    """
    stack = []  # Stack for open brackets
    pairs = {")": "(", "}": "{", "]": "["}  # Closing -> Opening
Enter fullscreen mode Exit fullscreen mode

Stack holds opens for matching. Dict maps closes to expected opens, O(1) lookup. This setup is flexible, add more pairs like '<': '>' easily.

2. Loop Scanning: Push Opens, Pop and Check Closes

Process each char:

for char in s:
    if char in pairs.values():  # Opening bracket
        stack.append(char)
    elif char in pairs:  # Closing bracket
        if not stack or stack.pop() != pairs[char]:
            return False
    # Ignore all non-bracket characters
return len(stack) == 0  # Must end with an empty stack
Enter fullscreen mode Exit fullscreen mode

Checks if open (values), push. If close (keys), pop and match or false if mismatch/empty. Ignores others. Final empty stack means balanced. For "{a[b]c}", true; "{[}" false.

3. Main Interactive: Input and Result

Script prompts and calls:

input_str = input("Enter a string: ").strip()

if is_valid(input_str):
    print("Result: True (valid parentheses)\n")
else:
    print("Result: False (invalid parentheses)\n")
Enter fullscreen mode Exit fullscreen mode

Strip cleans, calls function, prints bool. Simple, could add sequence examples.

🎯 Summary and Reflections

This parentheses checker embodies stack utility in validation, with dict for pairs. It reinforced:

  • Stack for matching: Push/pop for last-in-first-out order.
  • Mapping efficiency: Dict for quick verification.
  • Ignore non-relevant: Focus on brackets only.

Reflections: Common in compilers for syntax. Efficient, O(n) time/space. For fun, count mismatches.

Advanced Alternatives: Use deque for stack. Regex pre-filter brackets. Your bracket tip? Share!

🚀 Next Steps and Resources

Day 43 strengthened stack skills, prepping for parsing. In #80DaysOfChallenges? Added types? Post!

Top comments (0)