Given a string with parantheses, return the number of parantheses needed to ensure there are enough matching.

paran_matching.py

# (()) -> 0
# ))(( -> 4
# ()() -> 0
# (())) -> 1
# ()())( -> 2

def find_num_missing_parans(inp):
    i = 0
    j = 1
    res = 0

    # A single character string implies a paranthesis is orphaned
    if len(inp) <= 1:
        return 1

    while i < len(inp):
        if inp[i] == ')':
            res = res + 1
            i = i + 1
            j = i + 1
            continue

        next = None
        while j < len(inp):
            if inp[j] == ')':
                if next is None:
                    # If we haven't seen any open parans,
                    # we advance both pointers ahead
                    i = j + 1
                    j = j + 2
                else:
                    # Otherwise we track both pointers forward appropriately
                    i = next
                    j = j + 1
                break

            # Record the next open paran we need to match if we see it
            if next is None:
                next = j

            j = j + 1

        # When there are no closing parantheses anymore,
        # we stop trying to match
        if j >= len(inp):
            break

    orphaned_parans = 0
    
    # If we haven't looked at all the parans yet, each one left is missing a counterpart
    if i < len(inp):
        orphaned_parans = j-i
    return res + orphaned_parans


assert find_num_missing_parans('(())') == 0
assert find_num_missing_parans('))((') == 4
assert find_num_missing_parans('()()') == 0
assert find_num_missing_parans('(()))') == 1
assert find_num_missing_parans('()())(') == 2