Python - Matching Pairs of Brackets

Python - Matching Pairs of Brackets

Matching pairs of brackets in a string is a classic problem often encountered in programming interviews. The goal is to determine if the string has well-formed and matching brackets.

1. Introduction:

Consider the following examples:

  • "[]" �� This is well-formed.
  • "{[()]}" �� This is well-formed.
  • "{[(])}" �� This is not well-formed.
  • "{" �� This is not well-formed.

2. Using Stack:

A stack is an ideal data structure for this problem. We'll iterate through the string and:

  • Push any opening bracket onto the stack.
  • For any closing bracket, check the top of the stack:
    • If it matches the corresponding opening bracket, pop it.
    • Otherwise, the string is not well-formed.
def is_matched(expression): stack = [] bracket_map = {')': '(', '}': '{', ']': '['} for char in expression: if char in bracket_map.values(): # If character is an opening bracket stack.append(char) elif char in bracket_map.keys(): # If character is a closing bracket if stack == [] or bracket_map[char] != stack.pop(): return False else: return False # Invalid character return stack == [] # Test cases print(is_matched("{[()]}")) # True print(is_matched("{[(])}")) # False print(is_matched("{")) # False

3. Explanation:

For the string "{[()]}":

  1. { is pushed onto the stack.
  2. [ is pushed onto the stack.
  3. ( is pushed onto the stack.
  4. ) matches with the top of the stack ((), so ( is popped.
  5. ] matches with the top of the stack ([), so [ is popped.
  6. } matches with the top of the stack ({), so { is popped.
  7. At the end, the stack is empty, so the string is well-formed.

For the string "{[(])}":

  1. { is pushed onto the stack.
  2. [ is pushed onto the stack.
  3. ( is pushed onto the stack.
  4. ] does not match with the top of the stack ((), so we know it's not well-formed.

4. Real-world Applications:

  • Text Editors/IDEs: They often highlight mismatched brackets in your code to help you spot errors.

  • Compilers: They check for well-formed brackets to validate the syntax of code.

5. Considerations:

  • Performance: This algorithm runs in linear time, O(n), since we iterate through the string once and perform constant-time operations for each character.

  • Extensions: The basic concept can be extended to other matching pairs, not just typical brackets. For instance, matching HTML or XML tags.

  • Empty String: An empty string can be considered as well-formed.

6. Conclusion:

Using a stack is a straightforward and effective approach for matching pairs of brackets. This method ensures that we not only have a matching closing bracket for every opening bracket but also that they are in the correct order.

More Tags

wifi capacity-planning keyword unc flutter-packages trailing odata messaging real-time-data tcpdf

More Programming Guides

Other Guides

More Programming Examples