Reversing substrings in a string in python

Question

I am writing a program to reverse the substrings enclosed in parenthesis in python. The resultant string should not contain any parenthesis. I am printing b1 and b2 and ch for testing purposes. It seems that in the second iteration of the for loop inside the while loop, the b1 variable is not updated with the correct index. I tried to write a solution like below:

def reverseParentheses(s):
    r = s
    sstring = ''
    astring = ''
    b1 = b2 = 0
    count = 0
    for ch in s:
        if ch == '(':
            count+=1
        elif ch ==')':
            count+=1
        else:
            pass

    while True:
        b1 = b2 = 0
        for ch in r:
            if ch == '(':
                b1 = r.index(ch)
                print("b1= ",b1, ch)
            if ch == ')':
                b2 = r.index(ch)
                print("b2= ",b2, ch)
                sstring = r[b2-1:b1:-1]
                print(r)
                print(sstring)
                astring = r[0:b1]+sstring+r[b2+1:]
                print(astring)
                r = astring
                break
        if len(astring)+count == len(s):
            break
    return r



s = "a(bcdefghijkl(mno)p)q"
print(reverseParentheses(s))

This is the output that I get: aonmpbcdefghijklq This is the output I expect: apmnolkjihgfedcbq

It outputs this: b1= 1 ( b1= 1 ( b2= 17 ) a(bcdefghijkl(mno)p)q onm(lkjihgfedcb aonm(lkjihgfedcbp)q b1= 4 ( b2= 17 ) aonm(lkjihgfedcbp)q pbcdefghijkl aonmpbcdefghijklq aonmpbcdefghijklq. The last line is the end result of the program — Arshid Baba
– Arshid Baba, Commented Nov 30, 2018 at 6:45
find parens index on the deepest nested paren level, reverse chars in between, repeat until no parens left — Jean-François Fabre
– Jean-François Fabre ♦, Commented Nov 30, 2018 at 6:47
don't answer in comments, edit your question to include the expected output and actual output — Jean-François Fabre
– Jean-François Fabre ♦, Commented Nov 30, 2018 at 6:48

Mark · Accepted Answer · 2018-11-30 09:02:31Z

6

A nice way to deal with nested delimiters is to use a stack. When you encounter an opening delimiter push a new collection to the stack. pop() when you find a closing. This will keep the order of nesting correct.

Here's one way to do this (it doesn't check for balanced parenthesis, but it's not hard to add):

s = "a(bcdefghijkl(mno)p)q"
stack = [[]] # accumulate letters in stack[0]
for l in s:
    if l == '(':
        stack.append([])        # start a new level
    elif l == ')':
        sub = stack.pop()[::-1] # pop the last level and reverse
        stack[-1].extend(sub)   # add to current 
    else:
        stack[-1].append(l)     # add to current

''.join(stack[0]) #'apmnolkjihgfedcbq'

edited Nov 30, 2018 at 9:02

answered Nov 30, 2018 at 6:58

Mark

92.6k8 gold badges116 silver badges156 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

b-fg · Accepted Answer · 2018-11-30 08:13:04Z

1

A method by finding the position of the parenthesis and reversing from inside out (so the ones that are contained in-between an even number of parenthesis stay the same) and finally gets rid of the parenthesis:

s = "a(bcdefghijkl(mno)p)q"

leftp = reversed([pos for pos, char in enumerate(s) if char == "("])
rightp = [pos for pos, char in enumerate(s) if char == ")"]

for i in zip(leftp,rightp):
    subs = s[i[0]+1:i[1]][::-1]
    s = s[:i[0]+1]+subs+s[i[1]:]
for c in ["(", ")"]:
    s = s.replace(c, "")
print(s) # Outputs "apmnolkjihgfedcbq"

EDIT

For parenthesis that are not nested, as pointed out by .@Mark Meyer, you can find them as described here and same rule applies

def find_parens(s):
    toret = {}
    pstack = []
    for i, c in enumerate(s):
        if c == '(':
            pstack.append(i)
        elif c == ')':
            if len(pstack) == 0:
                raise IndexError("No matching closing parens at: " + str(i))
            toret[pstack.pop()] = i
    if len(pstack) > 0:
        raise IndexError("No matching opening parens at: " + str(pstack.pop()))
    return toret

s = "a(bcd)efghijkl(mno)pq"
parens = find_parens(s)

for leftp, rightp in parens.items():
    subs = s[leftp+1:rightp][::-1]
    s = s[:leftp+1]+subs+s[rightp:]
for c in ["(", ")"]:
    s = s.replace(c, "")
print(s) # Outputs "adcbefghijklonmpq"

edited Nov 30, 2018 at 8:13

answered Nov 30, 2018 at 7:33

b-fg

4,1872 gold badges31 silver badges45 bronze badges

3 Comments

Mark Over a year ago

seems problematic with strings like: s = "(ab)cdefghijklmno(pq)" --> "conmlkjihgfedcbadefghijklmnopq"

b-fg Over a year ago

More robust than yours now hehe :P

Mark Over a year ago

Seems pretty bulletproof now.

Collectives™ on Stack Overflow

Reversing substrings in a string in python

2 Answers 2

Comments

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related