• Martin Thoma
  • Home
  • Categories
  • Tags
  • Archives
  • Support me

Code Golf: Brackets Check

Contents

  • Solution: 846 characters
  • Minified Solution: 766 characters
  • See also

Write a function check_bracket_validity which takes a sequence of brackets as input and determines if it is valid.

A sequence is valid, iff:

  • All opened brackets close
  • Brackets come in pairs - only what was opened can be closed again
  • The 3 styles which should be supported are:
    • Round brackets: ( and )
    • Square brackets: [ and ]
    • Curly brackets: { and }
  • Brackets must be ordered: Either the opening and the closing brackets are within another pair of brackets or not. Something like this is invalid: [(])

Restrictions:

  • The formatter black will be applied to any solution
  • The signature, the docstring and the doctest is fixed.

Solution: 846 characters

def check_bracket_validity(brackets: str):
    """
    Check if a sequence of brackets is valid.

    Examples
    --------
    >>> check_bracket_validity("()[]{}")
    True
    >>> check_bracket_validity("([{([{}])}])")
    True
    >>> check_bracket_validity("([{([{}])}]")
    False
    >>> check_bracket_validity("([{([{}])}]))")
    False
    >>> check_bracket_validity("([)]")
    False
    """
    opening = "([{"
    pair = {"(": ")", "[": "]", "{": "}"}
    stack = []
    for bracket in brackets:
        if bracket in opening:
            stack.append(bracket)
        else:
            if len(stack) == 0:
                return False
            popped = stack.pop()
            if pair[popped] != bracket:
                return False
    return len(stack) == 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()

Minified Solution: 766 characters

Just using one-letter variable names:

def check_bracket_validity(brackets: str):
    """
    Check if a sequence of brackets is valid.

    Examples
    --------
    >>> check_bracket_validity("()[]{}")
    True
    >>> check_bracket_validity("([{([{}])}])")
    True
    >>> check_bracket_validity("([{([{}])}]")
    False
    >>> check_bracket_validity("([{([{}])}]))")
    False
    >>> check_bracket_validity("([)]")
    False
    """
    o, p, s = "([{", {"(": ")", "[": "]", "{": "}"}, []
    for b in brackets:
        if b in o:
            s.append(b)
        else:
            if len(s) == 0:
                return False
            q = s.pop()
            if p[q] != b:
                return False
    return len(s) == 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()

See also

  • Codegolf
    • Bracket balancing
    • Are the brackets fully matched?

Published

Mär 13, 2020
by Martin Thoma

Category

Code

Tags

  • Code 10
  • Code Golf 2
  • Python 141

Contact

  • Martin Thoma - A blog about Code, the Web and Cyberculture
  • E-mail subscription
  • RSS-Feed
  • Privacy/Datenschutzerklärung
  • Impressum
  • Powered by Pelican. Theme: Elegant by Talha Mansoor