16
\$\begingroup\$

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 , so the shortest code wins!

Examples

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

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

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

[In]: {]([(}]{)}
[Out]: {], (}, [], (}, {)
\$\endgroup\$
2
  • 3
    \$\begingroup\$ 3rd test case is duplicated \$\endgroup\$
    – Steffan
    Apr 14 at 20:53
  • \$\begingroup\$ @Steffan oh right \$\endgroup\$
    – mathcat
    Apr 15 at 6:36

23 Answers 23

10
\$\begingroup\$

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

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
<>{({}<({}<>)>)<>}<>
\$\endgroup\$
6
\$\begingroup\$

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.

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

Curry (PAKCS), 45 bytes

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

Try it online!

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

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)
\$\endgroup\$
2
  • 1
    \$\begingroup\$ RvyyÇ4%≠iìˆ]¯R works for 14 bytes. (the last 4 bytes could be .Á]) instead) \$\endgroup\$
    – ovs
    Apr 15 at 7:59
  • \$\begingroup\$ @ovs Thanks. :) \$\endgroup\$ Apr 15 at 8:25
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
2
  • 1
    \$\begingroup\$ You're allowed to output without separator, so 11 is definitely possible ;) \$\endgroup\$
    – ovs
    Apr 15 at 9:59
  • \$\begingroup\$ @ovs Oh.. didn't knew that was allowed. Ok, that makes it a lot easier. ;) \$\endgroup\$ Apr 15 at 10:08
4
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Instead of awk '{print $2}', tr -d 0-9\ is shorter. \$\endgroup\$
    – m90
    Apr 15 at 10:20
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
4
  • 2
    \$\begingroup\$ Welcome to Code Golf, and nice answer! It looks like you're taking input through the variable $s though, and that's disallowed. \$\endgroup\$ Apr 18 at 16:57
  • \$\begingroup\$ Thanks! Is wrapping a function around the code the accepted way to golf with PHP? function s($s){$i=0;foreach(str_split($s)as$v){if(strpos(" ({[",$v)){$a.=$v;}else{echo"$a[$i]$v ";$i++;}}} \$\endgroup\$
    – Steve
    Apr 18 at 17:38
  • \$\begingroup\$ That's probably the most common method, yeah. Other things like STDIN and GET params are also valid, but might be longer. \$\endgroup\$ Apr 18 at 17:42
  • \$\begingroup\$ Got it. I switched to taking input through $argn because I saw some other codegolf PHP answers doing it that way so I'm assuming that's valid too, and I added a Try it link. \$\endgroup\$
    – Steve
    Apr 18 at 18:28
3
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\begingroup\$ 150 \$\endgroup\$
    – Steffan
    Apr 14 at 22:39
  • \$\begingroup\$ 135 with python 3.8 and recursion \$\endgroup\$
    – Steffan
    Apr 14 at 22:54
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

Charcoal, 24 22 bytes

FS¿№)]}ιUM⊟υι«ι⊞υKD¹↙↙

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

FS

Loop over the characters in the input string.

¿№)]}ι

If this is a close bracket, then...

UM⊟υι«

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

ι

Output the open bracket.

⊞υKD¹↙

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

Move to the start of the next line.

\$\endgroup\$
0
3
\$\begingroup\$

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

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

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ Even shorter is *n?i+=*n%4%3*2-1:0. \$\endgroup\$
    – m90
    Apr 18 at 14:23
  • 2
    \$\begingroup\$ *n%4%3*2 can be (-*n&2). And i+=~-(-*n&2)%~*n saves another byte. \$\endgroup\$
    – ovs
    Apr 18 at 16:33
2
\$\begingroup\$

Perl 5, 59 bytes

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

Try it online!

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

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.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Doesn't actually work due to the cursedness of JS's sort, where 2 > 12 because of lexicographic sorting. \$\endgroup\$
    – allxy
    Apr 15 at 4:00
2
\$\begingroup\$

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.

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

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

\$\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.