if s.startswith('1'):
    return True, s[1:]
if s.startswith('('):
    success, rest = valid(s[1:])
if not success or not rest.startswith('|'):
    return False, s
success, rest = valid(rest[1:])
if not success or not rest.startswith(')'):
    return False, s
return True, rest[1:]
return False, s

def check(s):
    return valid(s) == (True, '')
Evaluating a string using recursion