# Find the index of the matching parentheses for each character

The challenge is simple, find the matching parentheses for every one of the parentheses in a given string input

E.g.

()()() -> [1, 0, 3, 2, 5, 4]


Always start with the ending parentheses index before the starting parentheses, which is why () becomes [1,0], not [0,1], unless the parentheses is stacked e.g. (()), where the position of the parentheses must match the index so (()) is [3, 2, 1, 0]

## Test Cases:

() -> [1, 0]
()(()) -> [1, 0, 5, 4, 3, 2]
()()() -> [1, 0, 3, 2, 5, 4]
((())) -> [5, 4, 3, 2, 1, 0]
(()(())) -> [7, 2, 1, 6, 5, 4, 3, 0]


You may output the indexes in the form of a list, or in the form of a string representation if so, but the output indexes must be distinguishable from each other e.g. 1 0

You are allowed to use 0-index or 1-indexed lists/arrays

• Suggested test-case: (()(())). Feb 3 at 19:39

# BQN, 37 bytesSBCS

{⌽˘⌾(∘‿2⊸⥊)¨⌾(((1⊸≠++)¯1⋆𝕩-@)⊸⊔)⊒˜𝕩}


Run online!

(1⊸≠++)¯1⋆𝕩-@ generates a depth map for the brackets. Coupled with Under, we can group the indices by depths, and reverse the grouping to get back the original array shape.

⌽˘⌾(∘‿2⊸⥊)¨ reverses each pair of bracket indices, putting them in the correct place.

-1 and -4 with ovs' help.

• ⌽˘⌾(∘‿2⊸⥊)¨⌾... saves a byte
– ovs
Feb 3 at 8:52
• very cute very neat Feb 3 at 8:52
• And this might help
– ovs
Feb 3 at 8:58

# x86-64 machine code, 21 bytes

5A 58 89 0A 8D 51 57 AB FF C1 45 31 C9 AC 84 C0 7B EE 75 F1 C3


Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes in RDI an address at which to place the result, as an array of 32-bit integers; and the address of the input, as a null-terminated byte string, in RSI.

In assembly:

.global f
rp: pop rdx           # (Right parenthesis) Pop the matching left parenthesis's
#   corresponding output address into RDX.
pop rax           # Pop its index into RAX.
mov [rdx], ecx    # Put the current index at the popped address.
.byte 0x8D        # Subsumes the next two instructions into 'lea edx, [rcx+0x57]'.
lp: push rcx        # (Left parenthesis) Push the index onto the stack.
push rdi        # Push the corresponding output address onto the stack.
stosd             # Store EAX at [RDI] and advance the pointer.
inc ecx           # Increment the index.
.byte 0x45        # REX.RB prefix byte; changes the next instruction to 'xor r9, r9'.
f:  xor ecx, ecx    # (Start here.) Set ECX to 0 (index in string).
lodsb             # Load a character of the string into AL, advancing the pointer.
test al, al       # Set the flags based on that character.
jpo rp            # Jump if it has an odd number if 1 bits (for a right parenthesis).
jnz lp            # Jump if it is nonzero (for a left parenthesis).
ret               # Return (for the null terminator).


# JavaScript (Node.js), 51 bytes

a=>a.map((c,i)=>a[a[i]=a.lastIndexOf(c>'('&&-1)]=i)


Try it online!

Input an array of characters. Output by modify the array in-place.

• what does this do btw lastIndexOf(c>'('&&-1) Feb 3 at 7:28
• @DialFrost if c is (, we try to find false in a, which results -1, since a doesn't contain false. So ( is replaced by -1. If c is ), we try to find -1 in a, which results last unclosed ( (had been replaced by -1 previously).
– tsh
Feb 3 at 7:30
• is there a way to implement is this in python3 (my code is too long lol i think its possible to use ur code as a reference for mine) Feb 3 at 7:41

g(a:x)|a>'('=1|w<-g x=1+w+g(drop w x)
a#b=succ<$>a!map(-1+)b ('(':x)!s=g x:x#(0:s) (_:x)!(a:s)=a:x#s _!w=w (![])  Try it online! With some comments: -- Get the 1-based index of the first unmatched ')' g :: [Char] -> Int g(a:x)|a>'('=1|w<-g x=1+w+g(drop w x) -- Common part of the two cases in (!); updates the indices (#) :: [Char] -> [Int] -> [Int] a#b=succ<$>a!map(-1+)b

-- Main function, iterates through the string
(!) :: [Char] -> [Int] -> [Int]
-- '(' are replaced by the result of g on the remaining string
('(':x)!s=g x:x#(0:s)
-- ')' are replaced by the index of the matching '(' (stored in the right argument)
(_:x)!(a:s)=a:x#s
_!w=w

h :: [Char] -> [Int]
h=(![])


snd.([]%).zip[0..]
z%((i,c):x)|c<')',(j:k,a)<-(i:z)%x=(k,j:a)|v:w<-z=([i],[v])<>w%x
z%e=mempty


Try it online!

# Python3, 75 bytes

def f(a,*s,i=-1):
for c in a:
i+=1;s+=i,
if"("<c:*s,a[i],_=s;a[a[i]]=i


Try it online!

-2 thx to @KevinCruijessen

-6 thx to @ovs

-10 thx to @loopywalt

-6 thx to @ovs

-4 thx to @loopywalt

## Python3, 76 bytes

def f(a,s=[]):
for*s[:0],c in enumerate(a):
if"("<c:i,v,*_=a[v],a[i],*s=s


Try it online!

• if c=="(" can be if")">c for -2. Feb 3 at 8:06
• s+=i, does s.extend((i,)) which has the same effect as s.append(i)
– ovs
Feb 3 at 9:14
• "a lot more readable"? I've taken care of that ;-] tio.run/… Feb 3 at 11:10
• 81 bytes
– ovs
Feb 3 at 11:36
• Eventually it has to stop, but for now have 79 bytes
– ovs
Feb 3 at 11:56

# Python, 93 bytes

def f(x):
d=c=0
for y in x:c-=y<')';x[d]=c;x[k:=x.index(c)]=d;x[d]=[c,k][k<d];c+=y>'(';d+=1


Attempt This Online!

Takes a list of characters and modifies it in-place.

#### How?

Simply walks the list from left to right. Tracks the bracketing depth (uses negative numbers, so we can unambiguously overwrite them with indices later). Whenever we encounter a level for the second time swap indices with first occurrence.

• beat me by 2 :( although mine is a lot more readable Feb 3 at 11:02

# 05AB1E, 19 bytes

vy'(QiNëN‚ˆ]¯€Âvyǝ


Input as a list of characters.

Explanation:

v          # Foreach over the characters of the (implicit) input-list:
y'(Qi    '#  If the current character is a ")":
N    #   Push the loop-index
ë     #  Else:
N‚   #   Pair the top with the loop-index
ˆ  #   Pop and add it to the global array
]          # Close both the if-statement and loop
¯         # Push the global array of index-pairs
€        # Map over each pair:
Â       #  Bifurcate it; short for Duplicate & Reverse copy
v      # Loop over each pair:
y    #  Push the value and index of the pair separated to the stack
ǝ   #  Insert the value at the index in the list
#  (which will use the implicit input-list the first iteration)
# (after which the list is output implicitly as result)


# Pari/GP, 61 bytes

-1 byte thanks to @DialFrost.

s->for(i=j=1,#a=s,if(")">s[i],s[j]=i;j++,a[a[i]=s[j--]]=i));a


Try it online!

• 61 Feb 3 at 13:37

# SNOBOL4 (CSNOBOL4), 144 136 bytes

	I =INPUT
M =BAL | ''
N	I POS(X) LEN(1) . B @X	:F(END)
B ")"	:F(L)
I @O '(' M B POS(X) 	:(O)
L	I POS(X) M @O ')'
O	OUTPUT =O	:(N)
END


Try it online!

	I =INPUT			;* Read input
M =BAL | ''			;* Alias: M is BAL (the shortest, non-null balanced string) or the empty string
N	I POS(X) LEN(1) . B @X	:F(END)	;* extract the next character of I as B, and store the position after B as X
B ")"	:F(L)			;* If B matches ")", goto next line, else goto L
I				;* In I, match:
@O				;* the position before the match as O
'(' M B			;* "(", a balanced string (or nothing), and ")"
POS(X) 	:(O)	;* ending at position X, then goto O
L	I POS(X) M @O ')'		;* In I, match, starting at position X, a balanced string, storing position as O, followed by ")"
O	OUTPUT =O	:(N)		;* Output O and goto N
END


# APL+WIN, 42 bytes

Prompts for input string. Index origin = 1

(,⌽((.5×⍴n),2)⍴n)[⍋n←⍋+$$~n)-¯1↓0,n←')'=⎕]  Try it online! Thanks to Dyalog Classic # Python3, 124 bytes: import re def f(s): while'('in s: s=re.sub('\(\d*$$',lambda x:f'{(S:=x.span())[1]-1}{x.group()[1:-1]}{S[0]}',s)
return s


Try it online!

• 121 Feb 3 at 23:41

# Charcoal, 34 bytes

≔⟦⟧ηＦθ¿⁼(ι«⊞υＬη⊞η⁰»«§≔η⌈υＬη⊞η⊟υ»Ｉη


Try it online! Link is to verbose version of code. Explanation:

≔⟦⟧η


Start building up the output list. (I need a second list as I want to use the predefined empty list as a stack.)

Ｆθ


Loop over the input characters.

¿⁼(ι«


If this is a (, then...

⊞υＬη


... save the current index to the stack, and...

⊞η⁰


... push a dummy value to the output list.

»«


Otherwise, ...

§≔η⌈υＬη


... replace the latest dummy value with the current index, and...

⊞η⊟υ


... push its index to the output list, removing it from the stack.

»Ｉη


Output the final list of indices.