Reversing substrings in parentheses

Question

Problem:
The task is to reverse the strings contained in each pair of matching parentheses, starting from the innermost pair. The results string should not contain any parentheses.

Example:

>>> s = "a(bc)de"
>>> reverseParentheses(s)
"acbde"
>>> s = "The ((quick (brown) (fox) jumps over the lazy) dog)"
>>> reverseParentheses(s)
"The god quick nworb xof jumps over the lazy"

To achieve this task I have written the following piece of code:

def reverseParentheses(s):
 i = 0
 brackarray = []
 recursivearray = []
 a = []
 numberofbrack = -1
 alteredstring = s


 chars = "()"
 for char in chars:
  alteredstring = alteredstring.replace(char, "")

 while i < len(s):

  if s[i] == '(':
   j = i
   numberofbrack = numberofbrack + 1
   j = j - numberofbrack
   brackarray.append(j)


  if s[i] == ')':
   m = i
   numberofbrack = numberofbrack + 1
   m = m- numberofbrack
   n = brackarray.pop()
   recursivearray.append((n,m))


  i = i+1

 for item in recursivearray:
  lenas = len(alteredstring)
  z = recursive(item[0], item[1], alteredstring)
  alteredstring1 =  alteredstring[0:item[0]]
  alteredstring2 = alteredstring[item[1]:lenas]
  alteredstring =  alteredstring1+z+alteredstring2


 return alteredstring


def recursive(start, end, string):
  y = string[start:end]
  string = y[::-1]
  return string

Could somebody please review above code and provide suggestions and improvements?

Answer 1

Please follow the official PEP 8 style guide. In particular, indentation matters a lot in Python! One space per level of indentation is much too stingy for readability; four spaces is standard. Also, using lowercase_with_underscores for function and variable names is the norm.

For this kind of function, I would strongly recommend writing a docstring with doctests. You could easily test your code by running python -mdoctest reverse.py.

recursive is a poorly named function: it's not recursive, and the name tells you nothing about what it does. I'd call it extract_and_reverse_substring.

You have too many variables, which makes the code confusing. In particular, a is never used! Furthermore, a lot of the complication arises from your decision to strip out all of the parentheses at the beginning, to form alteredstring. If you keep the parentheses, and strip them out afterwards, then you wouldn't need alteredstring, numberofbrack, and recursivearray, because that information would still be preserved in the string itself.

Python strings are immutable. When doing many repositioning operations on the characters in a string, consider using a list instead, for efficiency. That would allow you to replace individual characters without allocating new strings.

Suggested solution

def reverse_parentheses(s):
    """
    Reverse the strings contained in each pair of matching parentheses,
    starting from the innermost pair. The results string should not contain
    any parentheses.

    >>> reverse_parentheses('a(bc)de')
    'acbde'

    >>> reverse_parentheses(
    ...     'The ((quick (brown) (fox) jumps over the lazy) dog)'
    ... )
    'The god quick nworb xof jumps over the lazy'
    """
    chars = list(s)
    open_bracket_indexes = []
    for i, c in enumerate(chars):
        if c == '(':
            open_bracket_indexes.append(i)
        elif c == ')':
            j = open_bracket_indexes.pop()
            chars[j:i] = chars[i:j:-1]
    if open_bracket_indexes:
        raise ArgumentError('Unclosed parenthesis')
    return ''.join(c for c in chars if c not in '()')

Answer 2

A sidenote on style. Function names in Python should be lower case and separated with underscores instead of camelCase e.g. function_name

Also, I recommend you switch out that while i < len(s): with

for i in "string":
    #do something with i'th character

It removes the need to track a counter, and looks cleaner and more functional.

I also recommend you have a "Stack" helper class. It will really help clean up this implementation since you can just push on the stack and take it out when needed. Automatic reversal!

Example: https://stackoverflow.com/a/18279878/138228