CODEWITHSUNDEEP
pythontuples
SgtStens
SgtStens

Reputation: 300

Find all parentheses in a string by pairs - Python 3

I'm trying to get a list of tuples with the indices of all sets of parentheses in a string. I can find the left and right parens independently easily with list comprehensions:

s = "12(34)567"

left_parens = [i for i,j in enumerate(s) if j == "("]
right_parens = left_parens = [i for i,j in enumerate(s) if j == ")"]

The most logical way to turn these separate lists into a list of tuples with (left paren, right paren) pairs is with the zip function.

parens = zip(right_parens,left_parens)
print(list(parens))

From this I would expect to yield:

[(2,5)]

But instead, I get:

[(5,5)]

Even if I switch the order like this:

parens = zip(left_parens,right_parens)

The result is still [(5,5)].

What am I missing?

Try it online!

Upvotes: 3

Views: 935

Answers (1)

Prune
Prune

Reputation: 77860

The problem is here:

right_parens = left_parens = [ ... ]

You set the two lists to the same memory area; they are now the same list. Keep them separate:

left_parens  = [i for i,j in enumerate(s) if j == "("]
right_parens = [i for i,j in enumerate(s) if j == ")"]

EXTENSION

Note that your algorithm won't work for nested parentheses:

s = "1(2(34)56)7"

Output:

[(1, 6), (3, 9)]

You can solve this with a counter: pre-increment for each Lparen, post-decrement for each Rparen. Mark each paren location with its nesting level:

string 1(2(34)56)7(8)
marker -1-2--2--1-1-1

From here, move from the inside out: match the 2's, left to right (only one pair), then the 1's (two pairs). Coding is left as an exercise for the student. :-) From here, you can

Upvotes: 7

Related Questions