Python: Find the index of the matching parentheses for each character in a given string

Last update on March 22 2025 13:47:27 (UTC/GMT +8 hours)

Matching Parentheses Indices

Write a Python program to find the index of the matching parentheses for each character in a given string.

Input:  
()(())
Output:
[1, 0, 5, 4, 3, 2]

Input:  
()()()
Output:
[1, 0, 3, 2, 5, 4]

Input:  
((()))
Output:
[5, 4, 3, 2, 1, 0]

Visual Presentation:

Sample Solution:

Python Code:

# License: https://bit.ly/3oLErEI

# Define a function named 'test' that takes a string of parentheses 'parens' as input
def test(parens):
    # Convert the string of parentheses into a list
    a = list(parens)
    # Initialize an empty stack to keep track of the indices of opening parentheses
    stack = []
    
    # Iterate through the enumerated characters in the list 'a'
    for i, c in enumerate(a):
        # Check if the character is an opening parenthesis "("
        if c == "(":
            # Push the current index onto the stack
            stack.append(i)
        else:
            # Update the indices of the matching parentheses
            a[stack[-1]] = i
            a[i] = stack.pop()
    
    # Return the list with indices of the matching parentheses
    return a 

# Example 1
parens1 = "()(())"
print("Original parentheses:", parens1) 
print("Index of the matching parentheses for each character in a given string:")
print(test(parens1))

# Example 2
parens2 = "()()()"
print("\nOriginal parentheses:", parens2) 
print("Index of the matching parentheses for each character in a given string:")
print(test(parens2))

# Example 3
parens3 = "((()))"
print("\nOriginal parentheses:", parens3) 
print("Index of the matching parentheses for each character in a given string:")
print(test(parens3))

Sample Output:

Original parentheses: ()(())
Index of the matching parentheses for each character in a given string:
[1, 0, 5, 4, 3, 2]

Original parentheses: ()()()
Index of the matching parentheses for each character in a given string:
[1, 0, 3, 2, 5, 4]

Original parentheses: ((()))
Index of the matching parentheses for each character in a given string:
[5, 4, 3, 2, 1, 0]

Flowchart:

For more Practice: Solve these Related Problems:

• Write a Python program to find the matching closing parenthesis index for each opening parenthesis in a balanced string using a stack.
• Write a Python program to iterate over a string of parentheses and output a list pairing each opening with its corresponding closing index.
• Write a Python program to implement a stack-based algorithm that returns a list of indices where each parenthesis’s match is found.
• Write a Python program to use recursion or iteration to compute the matching indices for each parenthesis in a string.

Python Code Editor :

Have another way to solve this solution? Contribute your code (and comments) through Disqus.

Previous: Find two indices making a given string unhappy.
Next: Find an increasing sequence consisting of the elements of the original list.