Find the matching opening/closing brace index in a string

Question

I want the index of the corresponding brace in a for loop of a string like this for example: "(foo(bar))".

At first I did it like this, but it would always match the right/leftmost brace and thus it would not work with multiple braces:

for item in string:
    if item == "(":
        matchingbraceindex = string.find(")", item)

    elif item == ")":
        matchingbraceindex = string.rfind("(", 0, item)

Then I thought about counting the braces but I still wouldn't get the index, just the position among other braces, which I couldn't think of a way to extract an index from.

What output are you expecting for input `(foo(bar))`? – Abhijit Sarkar Aug 12 '20 at 17:59 — Abhijit Sarkar, Aug 12 '20 at 17:59

score 0 · Answer 1 · answered Aug 12 '20 at 17:54

0

Use a stack. Push left parens until you come across a right paren, at which time you’ve found the innermost pair. It’s not clear from your question what output you’re looking for, so I can’t say what to do with the letters.

answered Aug 12 '20 at 17:54

Abhijit Sarkar

21,927
20
110
219

score 0 · Answer 2 · answered Aug 12 '20 at 18:00

indexes_of_opening_brackets = []
indexes_of_closing_brackets = []

for index, item in enumerate(string):
    if item == "(":
        indexes_of_opening_brackets.append(index)
    elif item == ")":
        indexes_of_closing_brackets.append(index)

I didn't try the code, but I think it would work.

score 0 · Answer 3 · answered Aug 12 '20 at 18:11

Try this one, If I understand your question correctly, this is what you want. Here I am appending the values in a dictionary after searching "(" and ")" in the string

string = "(foo(bar))"

print(string.find(")"))
num = string.count(")")
a = 0
b = 0
dict_ = {"open": [], "close": []}
a = string.find("(", a)
dict_["open"].append(a)

for _ in range(0, num):
    a = string.find("(", a+1)
    dict_["open"].append(a)
    b = string.find(")", b+1)
    dict_["close"].append(b)

dict_["open"].pop(-1)
print(dict_)

score 0 · Answer 4 · answered Aug 12 '20 at 18:26

Stack is the easiest way to solve the problem. The below solution will give you the start and end index of every pair of braces as a list of tuples.

In [37]: string = '(foo(bar))'

In [38]: braces_stack = []
    ...:
    ...: pairs = []
    ...:
    ...: for index, char in enumerate(string):
    ...:     if char=='(':
    ...:         braces_stack.append(index)
    ...:     elif char==')':
    ...:         idx = braces_stack.pop()
    ...:         pairs.append((idx, index))
    ...:
    ...:

In [39]: pairs
Out[39]: [(4, 8), (0, 9)]

score 0 · Accepted Answer · answered Aug 12 '20 at 18:48

Using a stack, keep track of all of the pairs as you traverse the string:

def find_matching_parens(s, braces=None):
    openers = braces or {"(": ")"}
    closers = {v: k for k, v in openers.items()}
    stack = []
    result = []

    for i, c in enumerate(s):
        if c in openers:
            stack.append([c, i])
        elif c in closers:
            if not stack:
                raise ValueError(f"tried to close brace without an open at position {i}")

            pair, idx = stack.pop()
            result.append([idx, i])

            if pair != closers[c]:
                raise ValueError(f"mismatched brace at position {i}")
    
    if stack:
        raise ValueError(f"no closing brace at position {i}")

    return result

if __name__ == "__main__":
    print(find_matching_parens("(foo(bar)()baz(a(fz()asdf)))"))

Output:

[[4, 8], [9, 10], [19, 20], [16, 25], [14, 26], [0, 27]]

If you just want the matching bracket for a specific index, you can use this modification to the above function:

def find_matching_paren(s, i, braces=None):
    openers = braces or {"(": ")"}
    closers = {v: k for k, v in openers.items()}
    stack = []
    result = []

    if s[i] not in openers:
        raise ValueError(f"char at index {i} was not an opening brace")

    for ii in range(i, len(s)):
        c = s[ii]

        if c in openers:
            stack.append([c, ii])
        elif c in closers:
            if not stack:
                raise ValueError(f"tried to close brace without an open at position {i}")

            pair, idx = stack.pop()

            if pair != closers[c]:
                raise ValueError(f"mismatched brace at position {i}")

            if idx == i:
                return ii
    
    if stack:
        raise ValueError(f"no closing brace at position {i}")

    return result

if __name__ == "__main__":
    print(find_matching_paren("(foo(barbaz(a(fz()asdf))))", 4)) # => 24

score -2 · Answer 6 · answered Aug 12 '20 at 17:56

-2

Use a regular expression (source)

import re
[m.start() for m in re.finditer('\(', '(foo(bar))')]

[0, 4]

answered Aug 12 '20 at 17:56

Sebastian Baum

365
1
9

Find the matching opening/closing brace index in a string

6 Answers6