Check whether parens are matched in a string

parens.py

import re
from hypothesis import strategies as st, given, assume, note, example
from typing import List, Optional


def is_balanced(mystr):
    if len(mystr) % 2 != 0:
        return False

    stack = []
    for i in mystr:
        if i == '(':
            stack.append(')')
        elif i == '[':
            stack.append(']')
        elif i == '{':
            stack.append('}')
        else:
            if len(stack) == 0 or stack[-1] != i:
                return False
            else:
                stack.pop()

    return len(stack) == 0


def is_balanced_brute_force_no_regex(text: str):
    while (new_text := text.replace(
            '()', '').replace('[]', '').replace('{}', '')) != text:
        text = new_text
    return text == ''


def is_balanced_brute_force(text: str):
    while (new_text := re.sub(r'\(\)|{}|\[\]', '', text)) != text:
        text = new_text
    return text == ''


PAIRS = {'(': ')', '[': ']', '{': '}'}


def is_balanced_matthias(mystr: str):
    stack: List[Optional[str]] = [None]
    for c in mystr:
        if c == stack[-1]:
            stack.pop()
        else:
            stack.append(PAIRS.get(c))
    return len(stack) == 1


def extend(part):
    """This meta-strategy extends a partial strategy to one that can:
    - repeat the partial strategy
    - or put various parens around it
    """
    return (st.lists(part, min_size=2).map(''.join)
            | part.map(lambda s: f"({s})")
            | part.map(lambda s: f"[{s}]")
            | part.map(lambda s: f"{{{s}}}")
            )


# This strategy only produced balanced strings.
# Balanced strings are basically either the empty string,
# or an already balanced string that we are extending.
#
# Try in the REPL:
# >>> create_balanced.example()
# '{(({}{}(){}))}'
# >>> create_balanced.example()
# '({{{({})({})}}})'
create_balanced = st.recursive(st.just(''), extend)


@given(s=create_balanced)
def test_balanced(s):
    assert is_balanced(s)
    assert is_balanced_matthias(s)
    assert is_balanced_brute_force(s)


# Here we either create random strings,
# or we deliberately create a balanced string.
parens = st.text(alphabet="()[]{}x") | create_balanced


@ given(s=parens)
def test_against_reference_implementation(s):
    assert is_balanced_brute_force(s) == is_balanced(s)


def reverse_parens(s):
    """Turns eg '(hello {w]orld)' into '(dlro[w} olleh)'

    Ie we reverse the string, and flip all the parens.

    The input doesn't have to be balanced."""
    parens = {'(': ')', ')': '(', '[': ']', ']': '[', '{': '}', '}': '{'}
    return ''.join(parens.get(c, c) for c in reversed(s))


@ given(text=parens)
def test_reverse(text):
    """'Reversing' a string shouldn't change whether it's balanced or not."""
    reverse_text = reverse_parens(text)
    note(f"reverse_text: {reverse_text}")
    assert is_balanced(text) == is_balanced(reverse_text)


if __name__ == '__main__':
    # print(create_balanced.example())
    test_against_reference_implementation()
    test_balanced()
    test_reverse()