recursive way to find if a string is valid

Question

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 )

Is there a reason your code has to be recursive? The standard algorithm is to scan the string left to right and to increment a counter for each '(' and decrement it for each ')'. If the count is always ≥ 0 and is exactly zero at the end, you have a valid string. — Frank Yellin, Nov 30 '21 at 20:00
You don't do anything with the `cnt` variable. You don't pass it into the recursive call, and you never check it to see if it reaches zero. — khelwood, Nov 30 '21 at 20:04
See the accepted answer in [Recursive method for parentheses balancing](https://stackoverflow.com/questions/18007995/recursive-method-for-parentheses-balancing-python). — Nikolaos Chatzis, Nov 30 '21 at 20:11
There are several mistakes in logic in your code. A first mistake is the use of the `in` operator: you are checking if there is a '(' or a ')' in the string, but ignoring their order completely. Order is important. I suggest not using the `in` operator at all, and instead, only checking the next character in the string (so, always the character `s[0]`, if you choose to stick to the `is_valid_paren(s[1:])` method of recursion). — Stef, Dec 01 '21 at 00:25

Riccardo Bucco · Answer 1 · 2021-12-01T08:06:17.983

2

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
        if s[idx] == '(': return _is_valid(s, idx + 1) + 1
        if s[idx] == ')': return _is_valid(s, idx + 1) - 1
        return _is_valid(s, idx + 1)
    return _is_valid(s, 0) == 0

edited Dec 01 '21 at 08:06

answered Nov 30 '21 at 20:14

Riccardo Bucco

13,980
4
22
50

The OP appears to want to allow non-parens characters in valid strings, so the counter increment should probably be `+ (1 if s[idx] == '(' else -1 if s[idx] == ')' else 0)` – Stef Dec 01 '21 at 00:36

score 1 · Answer 2 · answered Nov 30 '21 at 20:16

1

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

answered Nov 30 '21 at 20:16

Alain T.

40,517
4
31
51

The user is for sure not interested in such a detail, but your solution is not ideal because you're creating useless copies of the original string with `s[1:]` (i.e., you're wasting memory). The overall complexity (both time and space) could be much better :) But I love how you select +1 or -1, I've never seen that! – Riccardo Bucco Nov 30 '21 at 20:19
Very true and worth mentionning. The approach is also constrained by the maximum recursion limit and won't be able to process strings that are close to 1000 characters. – Alain T. Nov 30 '21 at 20:24
1

@RiccardoBucco Have fun reading python code at https://codegolf.stackexchange.com if you want to see this trick used and abused ;) – Stef Dec 01 '21 at 00:30

Larry the Llama · Answer 3 · 2021-11-30T20:18:38.047

0

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.

edited Nov 30 '21 at 20:18

answered Nov 30 '21 at 20:03

Larry the Llama

958
3
13

1

This looked like homework. That's why I only hinted at the solution rather than writing out the code fo rhim. – Frank Yellin Nov 30 '21 at 20:05
@FrankYellin no problem - I will write an explanation for a recursive solution, and get rid of this one, because it doesn't really fit the prompt as Riccardo mentioned – Larry the Llama Nov 30 '21 at 20:07

recursive way to find if a string is valid

3 Answers3

Recursion