Detecting balanced parentheses

Question

Objective:

Given a string s containing '(', ')', '{', '}', '[', ']' (and other characters), determine if the input string is valid.

An input string is valid if:

1. Open brackets are closed by the same type of brackets.
2. Open brackets are closed in the correct order.

Code:

#!/usr/bin/env python3

from pathlib import Path

import typer


def validate_brackets(s: str, brackets={"[": "]", "{": "}", "(": ")"}) -> bool:
    stack = []

    opening = brackets.keys()
    closing = brackets.values()

    for c in s:
        if c in opening:
            stack.append(c)

        if c in closing:
            if not stack or c != brackets[stack[-1]]:
                return False
            stack.pop()
    return not stack


def main(file: Path) -> None:
    with open(file) as f:
        print(validate_brackets(f.read()))


if __name__ == "__main__":
    typer.run(main)

Review Request:

General coding comments, style, bad practices, et cetera.

Answer 1

Permit me to add the following to the review posted by toolic:

Use Docstrings

I would add a docstring to function validate_brackets describing its functionality.

Create a set from closing

Update

I have done a little research into the implementation of the dict_keys class an instance of which is created with opening = brackets.keys() and checking c in opening should be more or less equivalent to checking c in brackets, which is to say efficient. So there appears to be no need to create a set from the keys. However, if we want to efficiently check to see whether brackets.values() contains duplicates, then it seems to me we should create a set from these values and verify that its length is the same as the number of keys. This should also speed up the check c in closing. We can check to see if the set of keys and the set of values are disjoint by using opening.isdisjoint(closing) (see the next section concerning validation).

Sample Validation of the brackets Argument

Things you might test for:

1. The brackets argument is a non-empty dict instance.
2. brackets.values() contains no duplicate characters. Although this condition is not strictly necessary, it is the norm and we will enforce it.
3. The opening and closing characters should be disjoint.

The above validations are more easily performed when the closing characters are a set. This will also speed up the check c in closing. We will place the validation logic in a separate validate_brackets_dict function for greater readability. Since this function might be called repeatedly for the same brackets dictionary instance, we can cache previously-validated dictionaries in a dictionary whose key is a frozenset of the dictionary's items (since dictionaries are not hashable) and whose value is a tuple consisting of the opening and closing characters to be used.

I would also make the default value for the brackets argument to be None for which a default dictionary that requires no validation will be provided.

Putting It All Together

With the above suggested changes, the final source could be:

#!/usr/bin/env python3

from pathlib import Path
import typer
from typing import Union, Dict # For older Python versions

default_brackets = {"[": "]", "{": "}", "(": ")"}
default_opening = default_brackets.keys()
default_closing = set(default_brackets.values())

validated_brackets_dict = {}

def validate_brackets_dict(brackets: Dict) -> tuple:
    """Validate the brackets dictionary and if valid
    return a tuple of the opening and closing characters to be
    used. Otherwise, an exception is raised."""

    if not (isinstance(brackets, dict) and brackets):
        raise ValueError('brackets must be a non-empty dict instance')

    cache_key = frozenset(brackets.items()) # We cannot cache a dictionary
    opening_closing = validated_brackets_dict.get(cache_key, None)

    if opening_closing is None:
        # Validating a brackets dictionary that we haven't seen before
        opening, closing = brackets.keys(), set(brackets.values())
        # Although ensuring non-duplicate closing brackets is not strictly necessary,
        # it is certainly the norm. So we can consider the following
        # check optional but desirable:
        if len(closing) != len(brackets):
            raise ValueError('Duplicate closing characters')
        # Check for closing characters disjoint from opening
        # characters:
        if not opening.isdisjoint(closing):
            raise ValueError('Opening and closing characters are not disjoint')
        # Cache for possible next time:
        opening_closing = (opening, closing)
        validated_brackets_dict[cache_key] = opening_closing

    return opening_closing

def validate_brackets(text: str, brackets: Union[Dict, None]) -> bool:
    """Determine if the input text argument contains balanced
    parentheses. The optional brackets arguments is a dictionary
    of "parentheses" key/value pairs to be used.
    If brackets is None then a default dictionary is used."""

    if brackets is None:
        brackets = default_brackets
        opening, closing = default_opening, default_closing
    else:
        opening, closing = validate_brackets_dict(brackets)

    stack = []

    for c in text:
        if c in opening:
            stack.append(c)
        elif c in closing:
            if not stack or c != brackets[stack[-1]]:
                return False
            stack.pop()
    return not stack


def main(file: Path) -> None:
    with open(file) as f:
        text = f.read()

    print('text:', repr(text))
    print()
    # Some test case for validation:
    for brackets in (
        [],
        {},
        {'[': ']','(': ']'},
        {'[': ']','(': '['},
        {'[': 'x'},
        None
        ):
        print('brackets:', repr(brackets), end='')
        try:
            result = validate_brackets(text, brackets)
        except Exception as e:
            result = e
        print(', result:', repr(result))


if __name__ == "__main__":
    typer.run(main)

Prints:

text: 'abc[xx]'

brackets: [], result: ValueError('brackets must be a non-empty dict instance')
brackets: {}, result: ValueError('brackets must be a non-empty dict instance')
brackets: {'[': ']', '(': ']'}, result: ValueError('Duplicate closing characters')
brackets: {'[': ']', '(': '['}, result: ValueError('Opening and closing characters are not disjoint')
brackets: {'[': 'x'}, result: False
brackets: None, result: True

Answer 2

The code layout looks good, and you gave the functions and variables meaningful names.

That being said, you could consider using longer variable names for the single-letter ones. Perhaps, text instead of s, for example.

You should consider checking the inputs to the validate_brackets function. For example, I assume that you do not want to support the case where the opening and closing bracket is the same character, like [ and [. This code returns True:

print(validate_brackets('[aaa]', {"[": "["}))

If you do add checking for this case, then you can use elif for the closing condition since they are mutually exclusive:

    if c in opening:
        stack.append(c)
    elif c in closing:

I also recommend adding header comments describing the overall functionality and if there are restrictions on the inputs.

If you have not done so, adding some basic unit tests would be beneficial.

Answer 3

Minor improvement maybe: Replacing

if not stack or c != brackets[stack[-1]]:
    return False
stack.pop()

with:

if not stack or c != brackets[stack.pop()]:
    return False

Answer 4

Separate out the brackets

There's a bit of preprocessing necessary for the brackets:

• Validation
• Separation of keys and values

You can just preprocess the brackets again and again and again each time the function is called, but it's quite a waste of time when the user will, most likely, pass the same specification every, single, time.

The solution in such a case is to create a Brackets class, and perform all the preprocessing in its constructor.

The user is then free to pass the same instance over and over, or not to bother and just create it from scratch every time, or something in-between.

class Brackets:
    def __init__(self, brackets: dict[str, str]):
        self.__brackets = brackets
        self.__open = frozenset(brackets.keys())
        self.__close = frozenset(brackets.values())

        #   You may or may not wish to impose that closing brackets are
        #   distinct from one another. It is not strictly necessary though.

        if not self.__open.isdisjoin(self.__close)
            raise ValueError(f'Opening and closing characters are not disjoint in {brackets}')

    def is_open(self, c: str) -> bool:
        """Returns whether `c` is an opening bracket"""
        return c in self.__open

    def is_close(self, c: str) -> bool:
        """Returns whether `c` is a closing bracket"""
        return c in self.__close

    def is_matching(self, open: str, close: str) -> bool:
        """Returns whether `close` is the matching closing bracket of `open`"""
        return self.__brackets[open] == close

DEFAULT_BRACKETS = Brackets({"[": "]", "{": "}", "(": ")"})

Then, the function becomes:

def validate_brackets(s: str, brackets: Brackets=DEFAULT_BRACKETS) -> bool:
    """Returns whether `s` has balanced brackets, or not.

    A string has `s` has balanced brackets if ...
    """

    stack = []

    for c in s:
        if brackets.is_open(c):
            stack.append(c)
            continue

        if not brackets.is_close(c):
            continue

        if not stack or not brackets.is_matching(stack[-1], c):
            return False

        stack.pop()

    return not stack

Answer 5

The code is lean and maintainable. There are minor issues:

predicate naming

Predicates shall start with e. g. is_... or has_... so that True and False are natural answers.

useless locals

There is no need for

opening = brackets.keys()
closing = brackets.values()

as you can test for membership directly at no extra cost. Also the names do not help, brackets is a well introduced variable and is comparable in reading length. Also the locals miss the plural. Reading code is simpler if there are less names.

dict.keys()

Instead of testing for

some_var in brackets.keys()

you test for

some_var in brackets

Parameter brackets

I dislike the parameter as it is calling for errors. The function fails if the user does a typo. Also there might be a genius using the function to test for closed strings by passing

is_valid(s, brackets={'"': '"'}) 

Either

• make brackets a constant

• or limit the function parameters to explicitly named bracket types

  is_valid(s, brackets=True, braces=True, parentheses=True)

So you can test your function for all parameters.

Documentation

Add a one liner docstring explaining what is the meaning of "valid".