Validate Brackets in Python
Validating brackets is a common problem that tests logical thinking and understanding of data structures like stacks.
This article simplifies the topic, optimizing readability and implementation.
Let’s explore how to check whether parentheses, braces, and brackets are properly closed in a string using Python.
Introduction
Bracket validation is one of the most fundamental tasks in coding, often used in compilers and interpreters to ensure code syntax is correct.
In this tutorial, I will walk you through a Python solution for validating brackets in a string.
By the end of this article, you’ll understand how the stack data structure plays a key role in tackling this problem efficiently.
As software engineers, we solve such problems to build systems that are error-proof and dependable.
Our solution will focus on simplicity, readability, and optimization.
Solution: Understanding and Implementing the Code
Below is the Python implementation to validate if a string's brackets are balanced.
class Solution:
"""
Solution class to validate if a string's brackets are balanced.
"""
def isValid(self, s: str) -> bool:
"""
Validates whether the brackets in the input string are balanced.
Args:
s (str): The input string containing brackets.
Returns:
bool: True if the string has balanced brackets, False otherwise.
"""
# Map opening brackets to their corresponding closing brackets
brackets = {'(': ')', '{': '}', '[': ']'}
stack = [] # Stack to keep track of opening brackets
# Iterate through each character in the string
for char in s:
if char in brackets: # If it's an opening bracket
stack.append(char) # Push onto the stack
else: # If it's a closing bracket
# Check for mismatch or empty stack
if not stack or brackets[stack.pop()] != char:
return False
# If stack is empty, all brackets were matched correctly
return len(stack) == 0
Optimized Features
Clear Separation of Logic
The code distinguishes between opening and closing brackets with clarity.
Mismatched or extra brackets are caught early, improving efficiency.
Simple and Direct Checks
The logic to validate brackets ensures a clean O(n) time complexity.
Readability
Docstrings and inline comments explain every step of the process.
How It Works: Breaking It Down
Why Use a Stack?
A stack is a Last-In-First-Out (LIFO) structure, perfect for handling problems where the order of operations matters, such as matching opening and closing brackets.
Step-by-Step Execution
Let’s use the input s = "([{}])" to explain the workflow.
Initialization
The brackets dict is responsible for mapping opening to closing brackets.
The stack is initialized as empty to keep track of unmatched brackets.
Iterating Through Characters
When an opening bracket like (, {, or [ is found, it is added to the stack.
When a closing bracket like ), }, or ] is encountered:
- The stack is checked. On the off chance that it is empty, it means there’s no matching opening bracket.
- The bracket at the top of the stack is popped and compared to ensure it matches the current closing bracket.
Final Check
After processing all characters, the stack should be empty. If not, there are unmatched brackets, and the function returns False.
Performance
This solution processes each character once, resulting in a time complexity of O(n).
In the case above, n is the length of the input string.
The space complexity is also efficient, with the stack size at most equal to the number of opening brackets.
The Output in Action
Using the provided test case:
# Testing the solution
s = "([{}])"
sol1 = Solution()
print(sol1.isValid(s)) # Output: True
For input s = "([{}]), the output is True, indicating that all brackets are balanced. If we try an invalid string like s = "([{})]", the output will be False.
Why This Solution is a Go-To for Developers
This bracket validation problem is not just a theoretical exercise but a practical building block for applications like:
- Syntax validation in code editors.
- Parsing expressions in compilers.
- HTML/XML tag validation in web development.
- Our optimized solution ensures your applications are built on a robust foundation.
What’s Next? Learn and Practice
Now that you’ve mastered how to validate brackets using Python, here are a few steps to solidify your learning:
- Experiment with edge cases like empty strings, strings with only one type of bracket, or deeply nested brackets.
- Extend this solution to validate other matching symbols, like HTML tags.
- Explore queues & other data structures to establish their suitability for similar problems.
Balanced brackets might seem simple, but they pave the way for understanding complex data validation. Dive deeper and build even smarter solutions!