How do I reverse the strings contained in each pair of matching parentheses, starting from the innermost pair? CodeFights

Question

So far I have done this. I am stuck on recursion. I have no idea how to move forward, joining and reversing etc.

def callrecursion(s):
    a=s.index('(')
    z=len(s) - string[::-1].index(')') -1
    newStr=s[a+1:z]
# Something is missing here i cant figure it out
    print(newStr)
    return newStr

def reverseParentheses(s):  
    if '(' in s:
        return reverseParentheses(callrecursion(s))        
        print('wabba labba dub dub')
    else:
        return s
string='a(bcdefghijkl(mno)p)q'
reverseParentheses(string)

EXPECTED OUTPUT : "apmnolkjihgfedcbq"

Answer 1

def reverseParentheses(s):
    if '(' in s:
        posopen=s.find('(')
        s=s[:posopen]+reverseParentheses(s[posopen+1:])
        posclose=s.find(')',posopen+1)
        s=s[:posopen]+s[posopen:posclose][::-1]+s[posclose+1:]
    return s

string='a(bcdefghijkl(mno)p)q'
print(string)
print(reverseParentheses(string))
print('apmnolkjihgfedcbq') # your test

string='a(bc)(ef)g'
print(string)
print(reverseParentheses(string))

The idea is to go 'inward' as long as possible (where 'inward' does not even mean 'nesting', it goes as long as there are any opening parentheses), so the innermost pairs are flipped first, and then the rest as the recursion returns. This way 'parallel' parentheses seem to work too, while simple pairing of "first opening parentheses" with "last closing ones" do not handle them well. Or at least that is what I think.

---

Btw: recursion is just a convoluted replacement for rfind here:

def reverseParentheses(s):
    while '(' in s:
        posopen=s.rfind('(')
        posclose=s.find(')',posopen+1)
        s=s[:posopen]+s[posopen+1:posclose][::-1]+s[posclose+1:]
    return s;

(... TBH: now I tried, and the recursive magic dies on empty parentheses () placed in the string, while this one works)

Answer 2

I've come up with tho following logic (assuming the parentheses are properly nested).

The base case is the absence of parentheses in s, so it is returned unchanged.

Otherwise we locate indices of leftmost and rightmost opening and closing parentheses
(taking care of possible string reversal, so ')' might appear opening and '(' -- as closing).

Having obtained beg and end the remaining job is quite simple: one has to pass the reversed substring contained between beg and end to the subsequent recursive call.

def reverseParentheses(s):
    if s.find('(') == -1:
        return s

    if s.find('(') < s.find(')'):
        beg, end = s.find('('), s.rfind(')')
    else:
        beg, end = s.find(')'), s.rfind('(')
    return s[:beg] + reverseParentheses(s[beg + 1:end][::-1]) + s[end + 1:]