Beginner Exercism • python

Matching Brackets

Challenge Overview

Make sure the brackets and braces all match.

Introduction

You’re given the opportunity to write software for the Bracketeer™, an ancient but powerful mainframe. The software that runs on it is written in a proprietary language. Much of its syntax is familiar, but you notice lots of brackets, braces and parentheses. Despite the Bracketeer™ being powerful, it lacks flexibility. If the source code has any unbalanced brackets, braces or parentheses, the Bracketeer™ crashes and must be rebooted. To avoid such a scenario, you start writing code that can verify that brackets, braces, and parentheses are balanced before attempting to run it on the Bracketeer™.

Instructions

Given a string containing brackets [], braces {}, parentheses (), or any combination thereof, verify that any and all pairs are matched and nested correctly. Any other characters should be ignored. For example, "{what is (42)}?" is balanced and "[text}" is not.

Dig Deeper

Stack Match

def is_paired(input_string):
    bracket_map = {"]" : "[", "}": "{", ")":"("}
    stack = []

    for element in input_string:
        if element in bracket_map.values():
            stack.append(element)
        if element in bracket_map:
            if not stack or (stack.pop() != bracket_map[element]):
                return False
    return not stack

The point of this approach is to maintain a context of which bracket sets are currently “open”:

If a left bracket is found, push it onto the stack (append it to the list).
If a right bracket is found, and it pairs with the last item placed on the stack, pop the bracket off the stack and continue.
If there is a mismatch, for example '[' with '}' or there is no left bracket on the stack, the code can immediately terminate and return False.
When all the input text is processed, determine if the stack is empty, meaning all left brackets were matched.

In Python, a [list]concept:python/lists is a good implementation of a stack: it has list.append() (equivalent to a “push”) and lsit.pop() methods built in.

Some solutions use collections.deque() as an alternative implementation, though this has no clear advantage (since the code only uses appends to the right-hand side) and near-identical runtime performance.

The default iteration for a dictionary is over the keys, so the code above uses a plain bracket_map to search for right brackets, while bracket_map.values() is used to search for left brackets.

Other solutions created two sets of left and right brackets explicitly, or searched a string representation:

    if element in ']})':

Such changes made little difference to code length or readability, but ran about 5-fold faster than the dictionary-based solution.

At the end, success is an empty stack, tested above by using the False-y quality of [] (as Python programmers often do).

To be more explicit, we could alternatively use an equality:

    return stack == []

Repeated Substitution

def is_paired(text):
    text = "".join([element for element in text if element in "()[]{}"])
    while "()" in text or "[]" in text or "{}" in text:
        text = text.replace("()","").replace("[]", "").replace("{}","")
    return not text

In this approach, the steps are:

Remove all non-bracket characters from the input string (as done through the filter clause in the list-comprehension above).
Iteratively remove all remaining bracket pairs: this reduces nesting in the string from the inside outwards.
Test for a now empty string, meaning all brackets have been paired.

The code above spells out the approach particularly clearly, but there are (of course) several possible variants.

Variation 1: Walrus Operator within a Generator Expression

def is_paired(input_string):
    symbols = "".join(char for char in input_string if char in "{}[]()")
    while (pair := next((pair for pair in ("{}", "[]", "()") if pair in symbols), False)):
        symbols = symbols.replace(pair, "")
    return not symbols

The second solution above does essentially the same thing as the initial approach, but uses a generator expression assigned with a walrus operator := (introduced in Python 3.8) in the while-loop test.

Variation 2: Regex Substitution in a While Loop

Regex enthusiasts can modify the previous approach, using re.sub() instead of string.replace() in the while-loop test:

import re

def is_paired(text: str) -> bool:
    text = re.sub(r'[^{}\[\]()]', '', text)
    while text != (text := re.sub(r'{\}|\[]|\(\)', '', text)):
        continue
    return not bool(text)

Variation 3: Regex Substitution and Recursion

It is possible to combine re.sub() and recursion in the same solution, though not everyone would view this as idiomatic Python:

import re

def is_paired(input_string):
    replaced = re.sub(r"[^\[\(\{\}\)\]]|\{\}|\(\)|\[\]", "", input_string)
    return not input_string if input_string == replaced else is_paired(replaced)

Note that solutions using regular expressions ran slightly slower than string.replace() solutions in benchmarking, so adding this type of complexity brings no benefit to this problem.

Source: Exercism python/matching-brackets