Recursive Program for Sum of an Array in Python

Question

I've written the following program in Python, it is supposed to use only recursion to output whether or not the number of parentheses is even. For example:

nestParen("(())") --> true

nestParen("(((x))") --> false

Below is the code from my program. For some reason, it always returns true. Why is this and how can it be fixed? Thank you!

def nestParen(string1, max = 0, min = 0): 

    if max == 0:
        max = len(string1) - 1
    checker = False
    if max > min:
        if string1[max] == ")" and string1[min] == "(":
            checker = True
            min = min + 1
            max = max - 1
            if max > min:
                nestParen(string1, max, min)
                print checker
    return checker
nestParen("(((x))")

Please spend some more time formatting your code appropriately. — Brien Foss, Mar 08 '18 at 04:24
Possible duplicate of [Python recursion and return statements](https://stackoverflow.com/questions/937000/python-recursion-and-return-statements). Also your approach does not work e.g. for this case: `()()`. — Wombatz, Mar 08 '18 at 04:41
You don't even use the result of `nestParen(string1, max, min)`. Maybe you meant `checker = nestParen(string1, max, min)`? — Garrett Gutierrez, Mar 08 '18 at 18:10
I have absolutely no idea what the title is supposed to do with the question. — Karl Knechtel, Aug 13 '22 at 00:26

Ajax1234 · Answer 1 · 2018-03-08T18:02:21.700

A list may be best to keep track of the number of parenthesis you have currently seen. Also, it is easier to create a token system for easier identification. Lastly, cast each string as an iter, thus, by using next, you can more easily determine if you have finished iteration over the string:

import re
import collections
test = ["(())", "(((x))"]
def tokenize():
   token = collections.namedtuple('token', ['type', 'value'])
   token_results = [re.findall('\(|\)|\w+', i) for i in test]
   token_types = {'OPAREN':'\(', 'CPAREN':'\)', 'VAR':'\w+'}
   return [iter(token([a for a, b in token_types.items() if re.findall(b, c)][0], c) for c in i) for i in token_results]


def nestParen(s, current = []):
   checking = next(s, None)
   if not checking and current:
       return False
   if not checking and not current:
       return True
   if checking.type == 'OPAREN':
      return nestParen(s, current+[checking.value])
   if checking.type == 'CPAREN':
      if not current:
        return False
      val = current.pop()
      return nestParen(s, current)
   if checking.type not in ['CPAREN', 'OPAREN']:
      return nestParen(s, current)

final_results = map(nestParen, tokenize())
print(final_results)

Output:

[True, False]

While the tokenization system makes the program longer than other, more algorithmic versions, it is helpful to clearly create a method by which each character in the input strings is tagged and accounted for. This shortens nestParen in the long run as in your input it appears that other characters can appear besides (|).

Thank you for the solution. But could you please explain the purpose of the tokenize function? I don't entirely understand what it is supposed to do? — Eesha Agarwal, Mar 12 '18 at 10:15
@EeshaAgarwal The tokenize function makes it easier to identify key characters in the text. — Ajax1234, Mar 12 '18 at 14:47

Recursive Program for Sum of an Array in Python

1 Answers1