22
\$\begingroup\$

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

\$\endgroup\$
1
  • 4
    \$\begingroup\$ Suggested test-case: (()(())). \$\endgroup\$
    – pajonk
    Feb 3 at 19:39

16 Answers 16

6
\$\begingroup\$

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.

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

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).
\$\endgroup\$
0
5
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ what does this do btw lastIndexOf(c>'('&&-1) \$\endgroup\$
    – DialFrost
    Feb 3 at 7:28
  • 4
    \$\begingroup\$ @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). \$\endgroup\$
    – tsh
    Feb 3 at 7:30
  • \$\begingroup\$ 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) \$\endgroup\$
    – DialFrost
    Feb 3 at 7:41
5
\$\begingroup\$

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=(![])
\$\endgroup\$
5
\$\begingroup\$

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!

\$\endgroup\$
5
\$\begingroup\$

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!

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

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.

\$\endgroup\$
1
  • \$\begingroup\$ beat me by 2 :( although mine is a lot more readable \$\endgroup\$
    – DialFrost
    Feb 3 at 11:02
3
\$\begingroup\$

05AB1E, 19 bytes

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

Input as a list of characters.

Try it online or verify all test cases.

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)
\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 61 \$\endgroup\$
    – DialFrost
    Feb 3 at 13:37
2
\$\begingroup\$

Perl 5, 82 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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:

enter image description here

enter image description here

enter image description here

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
  • \$\begingroup\$ 121 \$\endgroup\$
    – DialFrost
    Feb 3 at 23:41
1
\$\begingroup\$

Charcoal, 34 bytes

≔⟦⟧ηFθ¿⁼(ι«⊞υLη⊞η⁰»«§≔η⌈υLη⊞η⊟υ»Iη

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

Fθ

Loop over the input characters.

¿⁼(ι«

If this is a (, then...

⊞υLη

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

⊞η⁰

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

»«

Otherwise, ...

§≔η⌈υLη

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

⊞η⊟υ

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

»Iη

Output the final list of indices.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.