brackets.py

# -*- coding: utf-8 -*-
"""
Author: Niall O'Connor

# https://app.codility.com/programmers/lessons/7-stacks_and_queues/brackets/

A string S consisting of N characters is considered to be properly nested if 
any of the following conditions is true:

        S is empty;
        S has the form "(U)" or "[U]" or "{U}" where U is a properly nested string;
        S has the form "VW" where V and W are properly nested strings.

For example, the string "{[()()]}" is properly nested but "([)()]" is not.

Write a function:

    def solution(S)

that, given a string S consisting of N characters, returns 1 if S is properly 
nested and 0 otherwise.

For example, given S = "{[()()]}", the function should return 1 and given 
S = "([)()]", the function should return 0, as explained above.

Write an efficient algorithm for the following assumptions:

        N is an integer within the range [0..200,000];
        string S consists only of the following characters: 
        "(", "{", "[", "]", "}" and/or ")".

# 100% solution https://app.codility.com/demo/results/trainingUMGUQH-FTX/
"""

import time


def solution(S):
    """
    Opening parenthesis are pushed and closing parenthesis pop.
    If the stack is empty prematurely there are too many closing brackets.
    If the stack is populated at the end there are too many opening brackets.
    """
    stack = []
    openers, closers = '{[(', '}])'
    for char in S:
        if char in openers:
            stack.append(char)
        else:
            # if there is a mismatch or an empty stack for a closing char its a fail
            if not stack or openers.index(stack.pop()) != closers.index(char):
                return 0

    return 0 if stack else 1


if __name__ == '__main__':

    tests = (
        # Test cases are in pairs of (expected, (args,))
        (1, ("{[()()]}",)),
        (0, ("([)()]",)),
    )

    for expected, args in tests:
        # record performance of solution
        tic = time.perf_counter()
        res = solution(*args)
        toc = time.perf_counter()
        print(f'ARGS produced {res} in {toc - tic:0.8f} seconds')

        if args[0] is None:
            continue # This is just a speed test

        try:
            assert(expected == res)
        except AssertionError as e:
            print(f'ERROR {args} produced {res} when {expected} was expected!')