Find the index of the matching parentheses for each character

Question

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.

This is code-golf so shortest bytes wins!

Answer 1

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).

Answer 2

BQN, 37 bytes^SBCS

{⌽˘⌾(∘‿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.

Answer 3

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.

Answer 4

Haskell, 112 bytes

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=(![])

Answer 5

Haskell, 94 bytes

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!

Answer 6

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

Other solutions:

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!

Answer 7

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.

Answer 8

05AB1E, 19 17 bytes

'(QvyiNëN‚ˆ]¯vyÂǝ

Input as a list of characters.

Try it online or verify all test cases.

Explanation:

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

Answer 9

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!

Answer 10

Perl 5, 82 bytes

sub f{($_,$i)=(@_,0);/\((?R)*\)/?(reverse($i..$i-1+($l=length$&)),f($',$i+$l)):()}

Try it online!

Answer 11

x86-16 machine code, 21 bytes

00000000: 33db ac3c 2974 0353 eb07 5888 0193 8801  3..<)t.S..X.....
00000010: 9343 e2ee c3                             .C...

Listing:

33 DB       XOR  BX, BX             ; start index counter at 0 
        P_LOOP: 
AC          LODSB                   ; AL = next char in input string 
3C 29       CMP  AL, ')'            ; is it an end paren? 
74 03       JZ   END_PAREN          ; if so, jump to handle
53          PUSH BX                 ; else, push index of left paren to stack 
EB 07       JMP  NEXT_PAREN         ; continue loop 
        END_PAREN: 
58          POP  AX                 ; AL = index of last start paren 
88 01       MOV  [DI+BX], AL        ; write to output at current index of input string 
93          XCHG AX, BX             ; AL = current index of input string 
88 01       MOV  [DI+BX], AL        ; write to output at index of last start paren 
93          XCHG AX, BX             ; restore index counter to BX 
        NEXT_PAREN: 
43          INC  BX                 ; increment counter 
E2 EE       LOOP P_LOOP             ; continue string loop 
C3          RET

Custom calling convention - input string at [SI], length in CX, output to buffer at [DI].

Tests with DOS DEBUG:

Answer 12

Retina 0.8.2, 67 bytes

\((?=((\()|(?<-2>.))*(?<=(.+)))|(?<=(.*).((\))|(?<-6>.))*).
$.3$.4 

Try it online! Link includes test cases. Assumes input is a balanced string of ()s. Explanation: The first alternation matches a (, skips over any balanced ()s, then captures the resulting index, while the second alternation matches in reverse, skipping back over any balanced ()s and an implied ( before capturing the resulting index, then matching an implied ). Fortunately $. outputs an empty string if the group was not captured at all, so we can just output the length of whichever capture was successful followed by a separator.

Answer 13

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

Answer 14

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

Answer 15

Curry (PAKCS), 55 bytes

g .zip[0..]
g[]=[]
g((i,'('):x++(j,')'):y)=j:g x++i:g y

Try it online!

Answer 16

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!

Answer 17

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.

Answer 18

BQN, 24 bytes

(⊢⊔⁼⊢(⊔⊒˜¨×⋈¬⊸×)·+`¬-»)⊐

Try it here.

How it works (with example):

1. Calculate the parenthesis depths from a mask of the string.
2. Split the depths into one vector where the indices of open parens are replaced with 0, and one vector where the indices of close parens are 0, such that if you add them together you get back the original depths.
3. Match depths of the open parens in the close paren half of the depth vector, and close parens in the open paren half, without repeats.
4. Use the original mask to combine the two lists of indices back together.

Detailed breakdown:

(⊢⊔⁼⊢(⊔⊒˜¨×⋈¬⊸×)·+`¬-»)⊐  # 
                       ⊐  # Classify the string to get a mask
(               ·+`¬-»)   # Generate depths of parentheses
    ⊢(    ×⋈¬⊸×)          # Pair mask and it's negation, multiplied by the depths
      ⊔                   # Group depths according to the mask
       ⊒˜                 # Take the progressive index-of
         ¨                #   between corresponding groups and depths 
  ⊔⁼                      # Inverse partition to combine results
 ⊢                        #   according to the original mask