hey so i am trying to write a code that that tells me if a string is valid or not . a valid string is a string that contains an equal number of "(" and ")" and each "(" must be closed by a ")" for example

'((()()))' this is a valid string . this isn't ')( '

this is what i wrote so far :

def is_valid_paren(s, cnt=0):
    if s == "":
        return True
    if "(" in s:
        cnt  = 1
    if ")" in s:
        cnt -= 1
    return is_valid_paren(s[1:])

it doesn't give the correct output for

"(.(a)"

yet for

"p(()r((0)))"

it does why does it sometimes work ? oh one more thing this is to be solved only by recursion ( without the use of loops anywhere )

CodePudding user response：

While I don't understand why you want to solve this problem with recursion (it's very unnatural in this case), here is a recursive solution:

def is_valid(s):
    def _is_valid(s, idx):
        if idx == len(s): return 0
        return _is_valid(s, idx   1)   (1 if s[idx] == '(' else -1)
    return _is_valid(s, 0) == 0

CodePudding user response：

You can pass down a count of pending apertures (i.e. number of unclosed parentheses) and check if the count goes below 0 (too many closures) as you go and if it ends back at zero at the end:

def validPar(s,count=0):
    if count<0 : return False     # too many closing
    if not s: return count == 0   # must balance pending apertures
    return validPar(s[1:],count (-1,1)[s[0]=="("]) # pass down count  /- 1

print(validPar('((()()))')) # True

CodePudding user response：

Recursion

Iteration is likely to be the best method of solving this, but recursion also works. To attack this problem recursively, we need a system of checking the count of each and if at any stage that count falls below zero, the parentheses will be invalid because there are more closing brackets than opening ones. This is where the tough section comes into play: we need some method of not only returning the count, but whether or not the past ones were valid, so we will have to return and save using variables like return count, valid and count, valid = is_valid_parentheses(s[1:]). The next thing we need is some over-arching function which looks at the end results and says: "is the count equal to zero, and were the parentheses valid to begin with". From there, it needs to return the result.