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
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
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
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