Let’s write a function that checks whether, in a given text, every opening parenthesis has a matching closing parenthesis, and whether no closing parenthesis appears before its corresponding opening parenthesis. The function should return True if these conditions are satisfied; otherwise, it should return False.
For example, the text ‘f(x) and g(x)’ is correctly parenthesized because the numbers of opening and closing parentheses are equal, and every closing parenthesis appears after its matching opening parenthesis. In contrast, the texts ‘) f(x) and g(x)’, ‘f(x)) and g(x)’, and ‘f((x) and g(x)’ are incorrectly parenthesized.
One possible implementation of this validation function is as follows. We create a variable named state with an initial value of 0. We then process the characters of the text from left to right and check whether each character is an opening or closing parenthesis. If it is an opening parenthesis, we increment state by one; if it is a closing parenthesis, we decrement it by one.
If state ever becomes negative during the iteration, it means that a closing parenthesis has appeared before its corresponding opening parenthesis, so the parenthesization is definitely invalid. In that case, we immediately exit the loop and return False.
If state never becomes negative, then at the end of the iteration its value can only be positive or zero. A positive value means that the text contains more opening parentheses than closing ones. Therefore, the function can return True only if the final value of state is 0. The corresponding function definition is shown below.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
def are_brackets_balanced(txt: str) -> bool: """Checks whether, in the given text, every opening parenthesis has a matching closing parenthesis, and whether no closing parenthesis appears before its corresponding opening parenthesis. The function returns True if these conditions are satisfied; otherwise, it returns False. """ state = 0 # Value indicating the parenthesis-processing state. for c in txt: if c == '(': state += 1 if c == ')': state -= 1 # If the state value is positive, more opening parentheses have been processed than closing ones. # If it is negative, a closing parenthesis has appeared before its corresponding opening parenthesis. # The result is True only if the final state value is 0. if state < 0: return False return True if state == 0 else False # TEST texts = ('f(x)', 'fx)', ')f(x)', 'a) f(x):', 'f(x))(', '((1,2), (3,4))') for text in texts: if not are_brackets_balanced(text): print(f'Bracket mismatch: "{text}"') # Output: # Bracket mismatch: "fx)" # Bracket mismatch: ")f(x)" # Bracket mismatch: "a) f(x):" # Bracket mismatch: "f(x))(" |
The logic implemented by the two conditional branches can also be expressed in a different way: when an opening parenthesis is encountered, +1 should be added to the current value of state; when a closing parenthesis is encountered, -1 should be added. The result is then stored back in state.
This essentially defines a mapping between parentheses and the values +1 and -1, which can be represented using a dictionary. If we do so, we can call the dictionary’s get() method inside the loop, passing the current character and 0 as the default value. The result of this call can be one of three values:
+1 if the current character is an opening parenthesis,
-1 if it is a closing parenthesis,
0 if it is neither an opening nor a closing parenthesis.
We then update state using the value returned by get(). The function implemented in this way is shown below.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
def are_brackets_balanced(txt: str) -> bool: """Checks whether, in the given text, every opening parenthesis has a matching closing parenthesis, and whether no closing parenthesis appears before its corresponding opening parenthesis. The function returns True if these conditions are satisfied; otherwise, it returns False. """ state = 0 # # Value indicating the parenthesis-processing state. for c in txt: state += {'(': +1, ')': -1}.get(c, 0) # If the state value is positive, more opening parentheses have been processed than closing ones. # If it is negative, a closing parenthesis has appeared before its corresponding opening parenthesis. # The result is True only if the final state value is 0. if state < 0: return False return True if state == 0 else False # TEST texts = ('f(x)', 'fx)', ')f(x)', 'a) f(x):', 'f(x))(', '((1,2), (3,4))') for text in texts: if not are_brackets_balanced(text): print(f'Bracket mismatch: "{text}"') # Output: # Bracket mismatch: "fx)" # Bracket mismatch: ")f(x)" # Bracket mismatch: "a) f(x):" # Bracket mismatch: "f(x))(" |
Does this approach offer any benefit beyond being a useful exercise in working with the dict type?
Yes, it does—especially if we want to generalize our function so that it can validate not only parentheses, but also other types of brackets, such as square brackets, curly brackets, or angle brackets.
Of course, we could meet the new requirements by inserting additional if…elif branches into the function body for each new bracket type. However, this approach is generally discouraged because every modification introduces the risk of breaking code that has already been tested. Consequently, each change would require additional testing, which is both time-consuming and labor-intensive.
The dictionary-based approach presented above, however, can be generalized. This allows us to create a solution that does not require any modification of the function definition when a new bracket type is introduced. You can see such an implementation below.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
def are_brackets_balanced(txt: str, brackets: str = '()') -> bool: """Checks whether, in the given text, every opening bracket has a matching closing bracket, and whether no closing bracket appears before its corresponding opening bracket. The function returns True if these conditions are satisfied; otherwise, it returns False. The bracket pairs to be checked must be specified in the brackets parameter, separated by spaces. Within each bracket pair, the opening bracket comes first, followed by the closing bracket. Examples: brackets='()' checks only parentheses brackets='() [] {}' checks parentheses, square brackets, and curly brackets """ # If the state value is positive, more opening brackets have been processed than closing ones. # If it is negative, a closing bracket has appeared before its corresponding opening bracket of the same type. bracket_pair_states = [] for opening, closing in brackets.split(): bracket_pair_states.append([dict(zip((opening, closing), (+1, -1))), 0]) for c in txt: for bracket_state in bracket_pair_states: bracket_state[1] += bracket_state[0].get(c, 0) if bracket_state[1] < 0: return False # The result is True only if the state value associated with every bracket type is 0. return all(state == 0 for _, state in bracket_pair_states) # TEST texts = ('f(x)', 'fx)', ')f(x)', 'a) f(x):', 'f(x))(', '((1,2), (3,4))', 'f(x, [1,2])', 'f(x, [[1,2])', 'f(x, [1,2], {3, 4})', 'f(x, [1,2], {3, 4}})', 'f((x, [1,2], {3, 4})') for text in texts: if not are_brackets_balanced(text, '() [] {}'): print(f'Bracket mismatch: "{text}"') # Output: # Bracket mismatch: "fx)" # Bracket mismatch: ")f(x)" # Bracket mismatch: "a) f(x):" # Bracket mismatch: "f(x))(" # Bracket mismatch: "f(x, [[1,2])" # Bracket mismatch: "f(x, [1,2], {3, 4}})" # Bracket mismatch: "f((x, [1,2], {3, 4})" |
The first parameter of the function receives the text to be examined. The second argument specifies the bracket pairs as a string, separated by spaces. By default, it contains only the pair of parentheses.
For each bracket type, we create a dictionary that maps the opening and closing symbols to +1 and -1, respectively. Each dictionary is then stored in a two-element list, whose second element holds the state value for that bracket type, initialized to 0. These two-element lists are collected into another list.
The remainder of the code adapts the processing logic described earlier. We iterate through the characters of the text and, for each character, check whether it matches either the opening or closing symbol of any of the specified bracket types. If it does, we increment or decrement the corresponding state value.
If any state value becomes negative during processing, the function immediately returns False. Otherwise, once all characters have been processed, we check whether all state values are equal to 0. If they are, the function returns True; otherwise, it returns False.
Note: The solution presented here verifies that, for each bracket type, the number of opening brackets matches the number of closing brackets, and that no closing bracket appears before its corresponding opening bracket. However, it does not check whether different types of brackets are properly nested. As a result, it would incorrectly consider the string ‘( [ ) ]’ to be valid. Detecting such cases requires a stack-based solution.
The purpose of this article, however, is not to present a fully featured bracket validation algorithm. Rather, it is to demonstrate how an if…elif structure that requires modification whenever a new case is introduced can be replaced with a data-driven approach. Bracket validation merely serves as a practical example for illustrating this technique.
In this exercise, the dict type played a central role. You can learn more about it in the e-book Python Knowledge Building Step by Step: From the Basics to Your First Desktop Application, in the subsection “Dictionary” of the chapter “Built-in Container Objects”, as well as in the subsection “Mapping-Type Containers” of the chapter “Public Methods of Built-in Types”.