Parenthesis in a recursive way (Python)

December 3, 2022

def paren(s, cnt=0):
    if s == '':
        return True
    if s[0] == '(':
        return paren(s[1:], cnt + 1)
    elif s[0] == ')':
        return paren(s[1:], cnt - 1)
    return cnt == 0

So this code works for all cases if there is the same number of "(" and ")".
But for example it doesn’t work for "))(( ".
how can I modify the code for this to work that for every opening bracket there is a closing one, then it returns True.

>Solution :

Check if at any point c < 0, and fix the return for when s == ''

def paren(s, cnt=0):
    if c < 0: return False
    elif s == '': return c == 0
    elif s[0] == '(':
        return paren(s[1:], cnt + 1)
    elif s[0] == ')':
        return paren(s[1:], cnt - 1)
    # here, there's a non-parentheses character. I'll assume you want to ignore these
    # if they're impossible, just remove this line
    return parent(s[1:], cnt)