Pair my brackets

Question

Given a string consisting of ()[]{}, print the paired brackets in the same order as they appear in the string.
Any opening bracket ([{ can be paired with any closing bracket )]}.

For example:

({()[}]]
returns:
(], {], (), [}

Rules

• A string consisting of ()[]{} should be received as the input
• The bracket-pairs should be returned as a list, or separated by a distinct character (or nothing), etc.
• The bracket-pairs should be in the same order as the starting brackets in the string
• The brackets will be balanced, i.e. the number of opening brackets and the number of the closing brackets will be the same
• Default Loopholes apply
• This is code-golf, so the shortest code wins!

Examples

[In]: ()
[Out]: ()

[In]: (}{]
[Out]: (}, {]

[In]: ([{}])
[Out]: (), [], {}

[In]: {]([(}]{)}
[Out]: {], (}, [], (}, {)

Answer 1

x86-64 machine code, 16 15 bytes

57 57 AA 5A 88 02 AC 3C 22 7B F8 AA 79 F2 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 a null-terminated byte string; and the address of the input, as a null-terminated byte string, in RSI. The starting point is after the first 6 bytes.

In assembly:

s:  push rdi        # (Left brackets) Push the current output address
    push rdi        #                  onto the stack twice.
    stosb           # Add AL to the output string again as a placeholder,
                    #  advancing the pointer.
                    #         (Right brackets enter here.)
r:  pop rdx         # Pop from the stack into RDX.
    mov [rdx], al   # Place AL at that address.
                    # For right brackets, this puts them in the spot reserved previously.
                    # For left brackets, this does nothing: the value there is the same.
f:                  #     (START HERE.)
    lodsb           # Load a byte from the input string into AL, advancing the pointer.
    cmp al, 0x22    # Set flags from that number minus 0x22.
    jpo r           # Jump if it has an odd number of 1 bits, true for right brackets.
    stosb           # (Left & null) Add AL to the output string, advancing the pointer.
    jns s           # Jump if the result was nonnegative.
    ret             # (Null terminator) Return.

Answer 2

Brain-Flak, 144 bytes

{(({}(<()>))<<>(()()()()){(({})){<>({}[()])}{}}>)<>({}[{}])((){[()](<{}>)}){{}{}<>(<({}<<>{({}<>)<>}{}>)>)}{}<>{({}<>)<>}{}}<>{({}<({}<>)>)<>}<>

Try it online!

Every bracket matching challenge needs a Brain-Flak submission.

# For each character in the input
{

  # Push zero below character, and keep another copy of character on third stack
  (({}(<()>))<

    # Compute character mod 4
    <>(()()()()){(({})){<>({}[()])}{}}

  # Push character back onto left stack
  >)

  # Is character equal to 1 mod 4?
  <>({}[{}])

  # If so:
  ((){[()](<{}>)}){

    {}{}<>(<({}<

      # Move to first 0 in right stack
      <>{({}<>)<>}{}

    # Push character, along with zero to break conditional
    >)>)

  }{}

  # Move elements back to right stack (or move character above an earlier pushed zero if was opening bracket)
  <>{({}<>)<>}{}

}

# Move bracket pairs to left stack to output in correct order
<>{({}<({}<>)>)<>}<>

Answer 3

Python, 77 72 bytes

Returns a string without separators.

f=lambda s,a='':s and f(s[:-1],(r:=s[-1]+a)[(q:=6-ord(s[-1])&2):])+r[:q]

Attempt This Online!

6-ord(x)&2 is 2 for opening brackets and 0 for closing ones.

Answer 4

Curry (PAKCS), 45 bytes

f[]=[]
f(a:b++c:d)|elem c")]}"=[a,c]:f b++f d

Try it online!

Answer 5

05AB1E, 17 14 bytes

RvyžuykÈiìˆ]¯R

-3 bytes thanks to @ovs.

Try it online or verify all test cases.

Explanation:

R           # Reverse the (implicit) input
 v          # Pop and loop over each character `y`:
  y         #  Push the character
   žuykÈi   #  If the character is an opening bracket:
   žu       #   Push constant string "()<>[]{}"
     yk     #   Get the (0-based) index of the character in this string
       Èi   #   If this index is even:
         ì  #    Prepend the top two characters together
          ˆ #    Pop this pair and add it to the global array
 ]          # Close both the if-statement and loop
  ¯         # Push the global_array
   R        # Revert it
            # (after which it is output implicitly as result)

Answer 6

Pyth - 23 bytes

Uses the fact that all the closing brackets (and none of the opening brackets) are 1 modulo 4 in ascii.

tMt#S.e?t%Cb4aY,kb+.)Yb

tM                 map "removing the first element"
 t#                filter on a no-op (its no-op in this case)
  S                sort
   .e              map over enumerate (k is idx, b is element)
    ?              ternary (0 is falsey)
     t             subtract 1
      %   4        modulo 4
       Cb          convert b to char code
     aY            append to Y (Y is global starting at [])
      ,kb          [k, b]
     +             concatenate
      .)Y          pop from back of Y
      b            

Try it online.

Answer 7

MathGolf, 13 11 bytes

x{_$4%┴┌Å▌¬

-2 bytes by outputting without delimiter, which is apparently allowed (see "(or nothing)" in the second rule)

Try it online.

Explanation:

x              # Reverse the (implicit) input-string
 {             # Foreach over each character:
               #  (implicitly push the current character we're looping over)
  _            #  Duplicate this character
   $4%┴┌Å      #  If this character is an opening bracket:
   $           #   Pop the copy, and push its codepoint-integer
    4%         #   Modulo-4
      ┴        #   Check if this is equal to 1
       ┌       #   Invert this boolean
        Å      #   Loop that many times,
               #   using 2 characters as inner code-block:
         ▌     #    Prepend the top two characters together
          ¬    #    Rotate the entire stack once towards the right
               # (implicitly output the entire stack joined together)

There are a bunch of alternatives possible for 4%┴┌Å▌¬, like for example Z+¶¿⌐▌¬: try it online.

    Z+         #   Add 38 to the codepoint-integer
      ¶        #   Check if this is a prime number
       ¿       #   If this is truthy, thus a closing bracket:
        ⌐      #    Rotate the entire stack once towards the left
       ¿       #   Else:
        ▌      #    Prepend the top two characters together
         ¬     #   Then rotate the entire stack once towards the right

Answer 8

Mathematica/Wolfram Language, 90 88 bytes

Transpose@MapAt[Reverse,GatherBy[Characters@#,Mod[First@ToCharacterCode@#,4]==1&]&@#,2]&

Uses the Mod-4 trick from the Pyth answer to split the characters into opening and closing brackets. Takes me 20 characters to reverse the closing list (so that the first opening bracket matches the last closing) which is annoying. Then, we transpose the lists and output. Shaved two characters by keeping the characters as characters and simply comparing their char codes. 11 more characters can be removed if we allow input as a list of chars instead of as a string.

Try it online!

Answer 9

Bash, ^{104 99} 94 bytes

awk '/[[{(]/{s[i++]=NR$1;next}{a[j++]=s[i---1]$1}END{for(x in a)print a[x]}'|sort -n|tr -d 0-9

Try it online!

-5 thanks to m90 for tr idea!

Bash translation of my JS answer. Was a nicer fit for awk than JS.

Answer 10

JavaScript (Node.js), 73 bytes

s=>s.map(c=>[c]).filter(c=>/[([{]/.test(c)?s.push(c):!s.pop().push(c[0]))

Try it online! I/O is lists of characters, but the examples in the footer convert from and to strings for convenience.

Answer 11

JavaScript (Node.js), 70 bytes

s=>s.map(c=>s[/[[({]/.test(c)?s.push([c])-1:s.pop()[0]+=c]||[]).flat()

Try it online!

Input array of characters. The idea about reusing s as the stack is learnt from Neil's answer.

Answer 12

PHP, 93 bytes

$i=0;foreach(str_split($argn)as$v){if(strpos(" ({[",$v)){$a.=$v;}else{echo"$a[$i]$v ";$i++;}}

Try it online!

Explanation: As opening brackets are encountered in the given string they're appended to a second string, then later paired up with closing brackets as the latter are encountered in the given string.

Answer 13

Python3, 155 bytes:

lambda x:f(x)[0]
def f(s):
 t,r=[],[]
 while s and s[0]in'([{':
  if s[1]in')]}':t+=[s[:2],*r];r=[];s=s[2:]
  else:x,y=f(s[1:]);r+=x;s=s[0]+y
 return t+r,s

Try it online!

Answer 14

Retina 0.8.2, 43 bytes

M!&`[({[](([({[])|(?<-2>).)*.
(.).+(.)
$1$2

Try it online! Link includes test cases. Explanation:

M!&`

List all overlapping matches...

[({[](([({[])|(?<-2>).)*.

... match an opening bracket, then any number of matched brackets, and then another character.

(.).+(.)
$1$2

Remove the inner matched brackets from each result.

Answer 15

Ruby, 103 bytes

->d{s,a=[],[];i=-1;d.chars.map{|x|i+=1;/[\[{(]/=~x ?s<<[i,x]:[t=s.pop,t[1]+=x,a<<t]};a.sort.map{_1[1]}}

Attempt This Online!

Answer 16

Charcoal, 24 22 bytes

ＦＳ¿№)]}ιＵＭ⊟υι«ι⊞υＫＤ¹↙↙

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

ＦＳ

Loop over the characters in the input string.

¿№)]}ι

If this is a close bracket, then...

ＵＭ⊟υι«

... pop a peeked cell and replace it with the close bracket, otherwise:

ι

Output the open bracket.

⊞υＫＤ¹↙

Peek the cell now under the cursor, but as a list whose elements can be modified.

↙

Move to the start of the next line.

Answer 17

Jelly, 17 15 14 bytes

O’4ḍ-*Ä+ƲỤs2Ṣị

Try it online!

Function returning a list of pairs, or full program smash-printing with no separator. Uses Maltysen's mod 4 trick.

O’                 Decrement the codepoints of the input,
  4ḍ               and test divisibility by 4.
O’4ḍ               That is, for each bracket, is it closing?
    -*             Raise -1 to the power of each,
      Ä            take cumulative sums,
       +Ʋ          and add the ones back in.
O’4ḍ-*Ä+Ʋ          This gives the depth of each bracket.
         Ụ         Grade up: sort the indices by the obtained depths.
          s2       Split the indices into adjacent pairs,
            Ṣ      sort the pairs lexicographically,
             ị     and index back into the original list.

Answer 18

Julia, 60 bytes

!x=x>"" ? !((m=match(r"(.*)([([{].)(.*)",x))[1]m[3])m[2] : x

Attempt This Online!

Similar to other answers, using a regex to capture the last open bracket + the next character

Answer 19

C (gcc), 122 111 bytes

6 bytes, 1 byte, and 2 bytes saved thanks to @ceilingcat, @m90, and @ovs

i;f(s,l,n)char*s,*n;{for(n=s;i+=~-(-*n&2)%~*n;n++);l-=printf("%c%c",*s,*n)+(n-++s?f(s,n-s),n-s:0);l&&f(n+1,l);}

Try it online! Takes input as a pointer to a character array and its length f(array,length) (the third parameter is unused). Outputs the mashed-together brackets to stdout.

Answer 20

Perl 5, 59 bytes

sub{$_=pop;1while s/(.*)([({[][)}\]])/unshift@_,$2;$1/e;@_}

Try it online!

Answer 21

JavaScript (Node.js), ^{123 113} 129 bytes

d=>(s=a=[],[...d].map((x,i)=>/[[{(]/.test(x)?s=[...s,[i,x]]:a.push((t=s.pop(),t[1]+=x,t))),a.sort((a,b)=>a[0]-b[0]).map(x=>x[1]))

Try it online!

-10 thanks to Steffan!

+16 thanks to allxy for pointing out I need to explicitly specify numeric sort

Uses a stack s which tracks open characters along with their index of occurence. On each close character, moves the top stack element to an answer array a, modifying it to include the close character. At the end, sorts according to start index and returns the pairs.

Answer 22

Python 3.8 (pre-release), 67 bytes

f=lambda s:s and f(s[:(q:=len(s.strip(']})'))-1)]+s[q+2:])+s[q:q+2]

Try it online!

Finds the rightmost opening bracket, which by definition must be paired with a closing bracket. Then, it recursively prepends the remaining brackets in the same way.

Answer 23

APL(Dyalog Unicode), 45 bytes ^SBCS

while this does change the order of brackets i found this approch very intersting

{{⍵[a,⍨(⍳≢⍵)~a←0 1+1⍳⍨2-/⍵∊'({[']}⍣(2÷⍨≢⍵)⊢⍵}

explanation

{f⍣n⊢⍵} ⍝ rubs the function f , n tikes which half its length

0 1+1⍳⍨2-/⍵∊'({[' ⍝ finds the index of first pair of brackets

a,⍨(⍳≢⍵)~a ⍝ puts those brackets at the end of the array

Try it on APLgolf!

A full program which ____.