fix.py

OPERATORS = "+-"


def simplify_parens(expr):
    """
    Remove all unnecessary parenthesis for a simple algebra-like string. It maintains the brackets, so any operator can be swapped for any other and the resulting expression will have the same results before and after parenthesis reduction.

    >>> simplify_parens('a')
    'a'
    >>> simplify_parens('a + b')
    'a + b'
    >>> simplify_parens('a + b - c')
    'a + (b - c)'
    >>> simplify_parens('(a + ((b + c)))')
    'a + (b + c)'
    >>> simplify_parens('(((a + b)) + c)')
    '(a + b) + c'
    >>> simplify_parens('(((((a + b) + ((c + z)))) + (((d))))) + ((b))')
    '(((a + b) + (c + z)) + d) + b'
    """

    rv = postfix_to_infix(infix_to_postfix(expr))

    if rv.startswith("(") and rv.endswith(")"):
        return rv[1:-1]
    else:
        return rv


def infix_to_postfix(expr):
    stack = []

    for c in expr:
        if c.isalnum():
            yield c
        elif c == ")":
            yield from reversed(stack)
            stack = []
        elif c in OPERATORS:
            stack.append(c)

    yield from reversed(stack)


def postfix_to_infix(expr):
    stack = []

    for c in expr:
        if c.isalnum():
            stack.append(c)
        elif c in OPERATORS:
            a, b = stack.pop(), stack.pop()
            stack.append(f"({b} {c} {a})")

    return stack.pop()


def oneshot_parens(expr):
    """
    Remove all unnecessary parenthesis for a simple algebra-like string. It maintains the brackets, so any operator can be swapped for any other and the resulting expression will have the same results before and after parenthesis reduction.

    >>> oneshot_parens('a')
    'a'
    >>> oneshot_parens('a + b')
    'a + b'
    >>> oneshot_parens('a + b - c')
    'a + (b - c)'
    >>> oneshot_parens('(a + ((b + c)))')
    'a + (b + c)'
    >>> oneshot_parens('(((a + b)) + c)')
    '(a + b) + c'
    >>> oneshot_parens('(((((a + b) + ((c + z)))) + (((d))))) + ((b))')
    '(((a + b) + (c + z)) + d) + b'
    """

    ip_stack = []
    pi_stack = []

    for c in expr:
        if c.isalnum():
            pi_stack.append(c)
        elif c in OPERATORS:
            ip_stack.append(c)
        elif c == ")":
            while ip_stack:
                o = ip_stack.pop()
                a, b = pi_stack.pop(), pi_stack.pop()
                pi_stack.append(f"({b} {o} {a})")

    while ip_stack:
        o = ip_stack.pop()
        a, b = pi_stack.pop(), pi_stack.pop()
        pi_stack.append(f"({b} {o} {a})")

    rv = pi_stack.pop()

    if rv.startswith("(") and rv.endswith(")"):
        return rv[1:-1]
    else:
        return rv