# Golf A Parentheses Matching Algorithm

You will be given a string s. It is guaranteed that the string has equal and at least one [s and ]s. It is also guaranteed that the brackets are balanced. The string can also have other characters.

The objective is to output/return a list of tuples or a list of lists containing indices of each [ and ] pair.

### note: The string is zero-indexed.

Example: !^45sdfd[hello world[[djfut]%%357]sr[jf]s][srtdg][] should return

[(8, 41), (20, 33), (21, 27), (36, 39), (42, 48), (49, 50)] or something equivalent to this. Tuples are not necessary. Lists can also be used.

Test cases:

input:[[asdf][][td([)ty54g% ]hg[[f]u][f[[jhg][gfd]sdf]sdfs]ghd]fr43f]
output:[(0, 62),(1, 6), (7, 8), (9, 56), (13, 22), (25, 30), (26, 28), (31, 52), (33, 47), (34, 38), (39, 43)]
input:[[][][][]][[][][][[[[(]]]]]))
output:[(0, 9), (1, 2), (3, 4), (5, 6), (7, 8), (10,26),(11, 12), (13, 14), (15, 16), (17, 25), (18, 24), (19, 23), (20, 22)]
input:[][][[]]
output:[(0, 1), (2, 3), (4, 7), (5, 6)]
input:[[[[[asd]as]sd]df]fgf][][]
output:[(0, 21), (1, 17), (2, 14), (3, 11), (4, 8), (22, 23), (24, 25)]
input:[]
output:[(0,1)]
input:[[(])]
output:[(0, 5), (1, 3)]


This is , so the shortest code in bytes for each programming language wins.

• Does the output order matter? – wastl Jun 7 '18 at 17:04
• no, it does not. – Windmill Cookies Jun 7 '18 at 17:05
• "note: The string is zero-indexed." - It's very common to allow implementations to choose a consistent indexing in these kind of challenges (but it is, of course, up to you) – Jonathan Allan Jun 7 '18 at 17:05
• Can we take input as an array of characters? – Shaggy Jun 7 '18 at 17:31
• Costs one byte... – dylnan Jun 7 '18 at 18:28

# Brain-Flak Classic, 108 bytes

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


Try it online!

Stores each opening [ in the right stack, and outputs whenever we hit a ].

# Python 2, 74 bytes

s=[];i=0
for c in input():
if'['==c:s+=i,
if']'==c:print s.pop(),i
i+=1


Try it online!

# JavaScript, 69 62 bytes

A quick bit of golf on the train home. Can probably be improved on.

Takes input as an array of characters and outputs an object with the keys being the indices of the [s and their values being the indices of their corresponding ]s.

a=>a.map((x,y)=>x==]?o[a.pop()]=y:x==[&&a.push(y),o={})&&o


Try it online

• It blows my mind that you can golf on mobile. :P – Oliver Jun 7 '18 at 18:09
• @Oliver, it blows my mind that I can (just about) type on touchscreens at all - bring back keyboards! – Shaggy Jun 7 '18 at 18:36

# Haskell, 92 79 bytes

g(u:a)n(']':x)=(u,n):g a(n+1)x
g a n(s:x)=g([n|s=='[']++a)(n+1)x
g[]_[]=[]
g[]0


Try it online!

## Explanation

We create a function g which takes 3 arguments.

• a, which is the locations of all unmatched [s.

• n, which is the number of characters processed

• x which is the characters unprocessed.

If our first character is ] we remove u from the front our a and return (u,n) plus whatever else remains.

g(u:a)n(']':x)=(u,n):g a(n+1)x


If our first character is not ], that is either [ or something else, we increment n and add [n|s=='['] to the front of a. [n|s=='['] will be [n] if s=='[' and [] otherwise.

g a n(s:x)=g([n|s=='[']++a)(n+1)x


If we are out of characters we return the empty list.

g[]_[]=[]

• wow, thats some nice piece of recursive functions. I'm a beginner on Haskell, this impressed me:) – Windmill Cookies Jun 7 '18 at 17:01
• @gnu-nobody Thanks! This answer is probably not optimal, so I would encourage you to try and beat it, or wait until the serious Haskell golfers arrive. – Sriotchilism O'Zaic Jun 7 '18 at 17:08
• I'd better wait until the serious Haskell golfers arrive – Windmill Cookies Jun 7 '18 at 17:09

# Java 10, 95 bytes

A void lambda taking the input string as an int[] of Unicode code points.

s->{int r=0,w=0;for(var c:s){if(c==91)s[w++]=r;if(c==93)System.out.println(s[--w]+","+r);r++;}}


Try It Online

## Ungolfed

s -> {
int r = 0, w = 0;
for (var c : s) {
if (c == 91)
s[w++] = r;
if (c == 93)
System.out.println(s[--w] + "," + r);
r++;
}
}


## Acknowledgments

• thanks to Jonathan Frech for the idea of using the input string as a stack (here)
• You must define r and w as part of the code, not as parameters: s->{int r=0,w=0;...}. – Olivier Grégoire Jun 7 '18 at 21:10
• @OlivierGrégoire Kind of ambiguous, but this looks like it was intended to cover multiple empty inputs. – Jakob Jun 7 '18 at 21:19
• The answer you quote explicitly answers the question "Are we allowed to take an empty parameter instead we won't use anywhere?". You're using these inputs. I see no ambiguity at all here. – Olivier Grégoire Jun 7 '18 at 21:20
• The edit part of the question makes it absolutely unambiguous about the "no-use" the variable. – Olivier Grégoire Jun 7 '18 at 21:30
• Right, but then why does the top answer (1) not state that inputs are unused, (2) specify what the values of extra inputs are, and (3) mention the possibility of abusing extra inputs? Regardless, I'll move the variables. – Jakob Jun 7 '18 at 21:43

# vim, 89 bytes

:s/$$.$$/\1<C-V><C-M>/g|g/^$/ :norm %mm%:pu! =line('.').','.line(\"'m\")<C-V><C-M><C-X><C-X>J :v/$$/d|%s/\[//g  ## Annotated :s/$$.$$/\1<C-V><C-M>/g " one character per line |g/^\[/ " for each opening square bracket: :norm %mm% " mark the line with the matching bracket :pu! =line('.').','.line(\"'m\") " write the line numbers to preceeding line <C-V><C-M><C-X><C-X>J " convert to 0-based counting and join lines :v/\[/d " remove all non-opening bracket lines |%s/\[//g " remove brackets  <C-V> is 0x16. <C-M> is 0x0d. <C-X> is 0x18. Try it online! ## QBasic (QB64), 137127 112 bytes INPUT a for i=0to len(a) c=mid(a,i+1,1) if"["=cthen b(n)=i n=n+1 elseif"]"=cthen n=n-1 ?b(n),i endif next  We need four two bytes because the challenge requires 0-indexing. My first QBasic post, feedback is appreciated. • 10 bytes thanks to steenbergh • 3 bytes thanks to Erik the Outgolfer • 12 bytes by saving in unix file format (\r\n -> \n) Looks like this when executed: • Nice one. Couple of pointers: use ? instead of print (the compiler auto-expands this to print), you don't need the spaces between the quoted strings and THEN in the IFs, and you can drop the i after NEXT. – steenbergh Jun 7 '18 at 18:25 • @steenbergh Huh, seems I forgot to remove whitespace ... but I removed the one between 0 and to? I'm confused ... – wastl Jun 7 '18 at 19:06 • Not sure about QB64, but I think if c="[" can become if"["=c, elseif c="]" can become elseif"]"=c, end if can become endif, and, with a slight change in the output, ?b(n),i can become ?b(n)i (QBasic 1.1 is what I use, your case might be different). – Erik the Outgolfer Jun 8 '18 at 11:42 • @EriktheOutgolfer all but ?b(n)i worked – wastl Jun 8 '18 at 12:11 # Pyth, 26 bytes VQIqN\[=+YZ)IqN$,.)YZ)=hZ  Try it here ### Explanation VQIqN$=+YZ)IqN$,.)YZ)=hZ VQ =hZ For each character in the input (indexed by Z)... IqN$=+YZ) ... if the character is [, add the index to Y... IqN$,.)YZ) ... if the character is ], output the previous index and current index.  • Nice! My naïve approach was 36 bytes, C,x"[" MQ #.e*qb$t+lhfSI/LT"[]"._>Q. Edit: I succeeded golfing mine quite a bit too, I'm now below 30. – Mr. Xcoder Jun 7 '18 at 17:17 # R, 141 133 115 112 108 bytes function(y,x=utf8ToInt(y)){for(i in seq(x)){if(x[i]==91)F=c(i,F);if(x[i]==93){T=c(T,F[1],i);F=F[-1]}};T[-1]}  Try it online! Nothing special. 1-indexed, because I said so. R doesn't really have stacks, so I originally used c, head, and tail to get the same literal effect. Ungolfed original version (updates using utf8ToInt to remove some bytes, using the start of the vector as the top of the stack, and abusing T and F builtins to avoid initializing the stacks.): f <- function(y, x=el(strsplit(y,""))) { p <- l <- NULL for(i in seq_along(x)) { if(x[[i]]=='[') { p <- c(p, i) } if(x[[i]]==']') { l <- c(l, tail(p, 1), i) p <- head(p, -1) } } l # Because I said so. Change to l-1 if you want to check the test cases. }  • Save some bytes by abusing built-ins T and F – JayCe Jun 8 '18 at 19:21 • and 1:nchar(y) is shorter than seq_along(x). Very nice solution btw :) – JayCe Jun 8 '18 at 19:23 • I wonder if gregexpr is the way to go. – ngm Jun 8 '18 at 19:53 • I had originally tried to leverage this approach but I am not sure if this is the right way here. – JayCe Jun 9 '18 at 13:32 • JayCe solution is flawed (check the result, it returns 22 28 22 instead of 22 28 21) probably the (ab)use of T/F is not really safe :D. This is shorter and seems to work --> Try it online! – digEmAll Jun 9 '18 at 13:53 # Forth (gforth), 75 bytes : f 0 do dup i + c@ dup 91 = if i s>f then 93 = if f>s . i . cr then loop ;  Try it online! Abuses the floating-point stack, but allows using a do loop since the code doesn't (manually) touch the return stack. ### Explanation 1. Loop through characters in string 2. Check each character 1. If equal to [, put on floating point stack 2. if equal to ] pop from floating point stack and output with current position ### Code Explanation 0 do \ start a loop from 0 to string-length dup \ duplicate the starting address to avoid losing it i + c@ \ get the address of the current position and retrieve the character dup \ duplicate the character, to allow checking twice 91 = if \ if char = [ i s>f \ store the current address on the floating point stack then \ end the if-statement 93 = if \ if char = ] f>s . \ pop the starting position from the float-stack and print i . \ print the current position cr \ output a newline then \ end the if-statement loop \ end the loop  # Retina, 36 bytes Lv\[((\[)|(?<-2>])|[^]])* .,.>  Try it online! Explanation: L  Generate a list from the match results.   Use the following substitution to generate the list instead of the matches. v  Allow matches to overlap. \[((\[)|(?<-2>])|[^]])*  This is an application of .NET's balancing groups. The [ is matched literally, then as many characters as possible are consumed. As each subsequent [ is matched, the match is added to the 2 stack. If that stack isn't empty, we can then match a ], removing the match from the stack. Otherwise, we can match anything that's not a ] (the [ was already matched earlier). The match stops when it meets the matching ] for the [, since the 2 stack is (now) empty at that point. .,.>  The substiution consists of two variables separated by a comma. The . indicates that the length of the variable, rather than its value, be used. The > indicates that the variable should be evaluated in terms of the right-hand separator rather than the match. The  variable refers to the prefix of the match, which means . gives the position of the [; the > modifier alters this to the prefix of the match's right separator, which gives the position of the matching ]. # Jelly, 22 21 20 19 bytes No doubt it is possible in Jelly in half this byte count :p ... n€Ø[ḅ-µMịÄÐƤi€0ĖƊ’Ä  A monadic link accepting a list of characters which returns a list of lists of integers. As a full program it accepts a string and prints a representation of said list. Try it online! ### How? n€Ø[ḅ-µMịÄÐƤi€0ĖƊ’Ä - Link: list of characters e.g. "[f[o]o!]" Ø[ - list of characters = ['[', ']'] n€ - not equal? for €ach [[0,1],[1,1],[0,1],[1,1],[1,0],[1,1],[1,1],[1,0]] - ...relating to the characters: [ f [ o ] o ! ] ḅ- - convert from base -1 [1,0,1,0,-1,0,0,-1] - ...i.e.: 1 where '['; -1 where ']'; and 0 elsewhere µ - start a new monadic chain with that as the argument, say V Ɗ - last 3 links as a monad (function of V): ÐƤ - for post-fixes: Ä - cumulative sum [[1,1,2,2,1,1,1,0],[0,1,1,0,0,0,-1],[1,1,0,0,0,-1],[0,-1,-1,-1,-2],[-1,-1,-1,-2],[0,0,-1],[0,-1],-1] i€0 - 1st index of 0 in €ach (or 0) [8,1,3,1,0,1,1,0] Ė - enumerate [[1,8],[2,1],[3,3],[4,1],[5,0],[6,1],[7,1],[8,0]] M - maximal indices of V [1,3] ị - index into [[1,8],[3,3]] ’ - decrement [[0,7],[2,2]] Ä - cumulative sum (vectorises) [[0,7],[2,4]]  • I was trying to use œ¿ and it's relatives but couldn't find a solution. This was closest I got. – dylnan Jun 7 '18 at 19:47 • Yes, it can be shorter, but I only managed one measly byte, not half the bytes. It still feels too long. :( – Erik the Outgolfer Jun 7 '18 at 20:04 • @EriktheOutgolfer there was an easy 1-byte save here too – Jonathan Allan Jun 7 '18 at 20:45 # SWI-Prolog 254 bytes d([']'|T],I,[S|Z],M,R):-J is I+1,d(T,J,Z,[',','(',S,',',I,')'|M],R). d(['['|T],I,S,M,R):-J is I+1,d(T,J,[I|S],M,R). d([_|T],I,S,M,R):-J is I+1,d(T,J,S,M,R). d(_,_,_,R,R). m(X):-atom_chars(X,A),d(A,0,[],[']'],[_|R]),atomic_list_concat(['['|R],S),print(S).  Example: ?- m('!^45sdfd[hello world[[djfut]%%357]sr[jf]s][srtdg][]'). '[(49,50),(42,48),(8,41),(36,39),(20,33),(21,27)]' true  # C (gcc), 87 bytes f(char*Z){for(char*z=Z,*q=z;*z;*z++-93||printf("%d,%d;",*--q,z-1-Z))*z-91||(*q++=z-Z);}  Try it online! # Explanation To keep track of opening bracket's string indices, the input string is overwritten and used as a stack. f(char*Z){ // take mutable input string for(char*z=Z,*q=z; // copy pointer to current string index, current stack index *z; // loop through the entire string *z++-93|| // if z == ']' printf("%d,%d;", // decrement stack pointer, *--q,z-1-Z)) // write bracket pair position *z-91|| // if z == '[' (*q++=z-Z);} // write bracket position onto stack, increment stack pointer  Try it online! # Jelly, 20 bytes =©ⱮØ[_/aÄ+®ŻĠḊẎ_2s2  Try it online! It has a side-effect on the register, hope it's allowed to be a function. • It's reusable, so I think it's fine. BF answers don't typically leave the tape blank – dylnan Jun 7 '18 at 20:48 # Japt v1.4.5, 23 bytes ;Ë¥']?ApENo):D¥'[©NpE A  Try it online! ### Unpacked & How it works ;UmDE{D==']?ApENo):D=='[&&NpE A ; Use alternative set of initial variables A = [] is used here UmDE{ Map over each char of input string... D==']? If the char is closing bracket... ApENo) Push the current index and N.pop() to A :D=='[&& Otherwise, if the char is opening bracket... NpE Push the current index to N A Output A  The output is a flattened array of [closing index, opening index]. If the reversed order is not desired, adding w at the end does the job (+1 bytes). ## Common Lisp, 95 bytes (lambda(u &aux s)(dotimes(p(length u))(case(elt u p)(#\[(push p s))(#$(print(,(pop s),p))))))  Long version (defun par (string &aux stack) (dotimes (pos (length string)) (case (char string pos) (#$(push pos stack)) (#$ (print (list (pop stack) pos))))))  Tests ((lambda(u &aux s)(dotimes(p(length u))(case(elt u p)(#$(push p s))(#$(print(,(pop s),p)))))) "!^45sdfd[hello world[[djfut]%%357]sr[jf]s][srtdg][] ")  prints: (21 27) (20 33) (36 39) (8 41) (42 48) (49 50)  # K (ngn/k), 38 37 bytes {b@0N 2#,/=(|':+\-/a)b:&|/a:"[]"=\:x}  Try it online! { } function with argument x "[]"=\:x two boolean lists for the occurrences of "[" and "]" a: assign to a |/ boolean "or" of the two lists & where (at which indices) are the brackets? b: assign to b -/ a list with 1 for "[", -1 for "]", and 0 everywhere else +\ partial sums |': pairwise maxima (each element max'ed with the previous one, the initial element remains the same) This represents bracket depth for each character. We index it with b (juxtaposition is indexing) and get bracket depth only for the brackets. = "group by" - a dictionary mapping depths to the indices at which they occur ,/ concatenate the values in the dictionary, ignoring the keys 0N 2# reshape to a 2-column matrix (list of lists) b@ index b with each element of the matrix # Jelly, 20 18 bytes Saved 1 byte thanks to @user202729 informing me that µ€ is ) ẹⱮØ[µ³ḣċþØ[_/Ụị)Z’  Try it online! After wrestling with this for several hours just to get it working... I'm honestly surprised that it's gotten this short :-) ### Explanation ẹⱮØ[µ³ḣċþØ[_/Ụị)Z’ Main link. Argument: s (string) '[a[b]c[]][d]' Ø[ Shortcut for the string "[]". Ɱ For each char in the "[]": ẹ Find the indices of each occurrence in the input. For our example, this gives the array [[1, 3, 7, 10], [5, 8, 9, 12]]. µ Begin a new monadic chain, with said array as its argument. ) For each of the two sub-arrays q within the array: [[1, 3, 7, 10], [5, 8, 9, 12]] ³ḣ For each item n in q, take the first n chars of the input. [['[', '[a[', '[a[b]c[', '[a[b]c[]]['], ['[a[b]', '[a[b]c[]', '[a[b]c[]]', '[a[b]c[]][d]']] þØ[ For each string s in this, and each char c in "[]": ċ Count the occurrences of c in s. [[[1, 0], [2, 0], [3, 1], [4, 3]], [[2, 1], [3, 2], [3, 3], [4, 4]]] _/ Reduce each pair by subtraction. This is the number of open brackets at each position. [[1, 2, 2, 1], [1, 1, 0, 0]] U Sort the indices by their values, using position as a tiebreaker. [[1, 4, 2, 3], [3, 4, 1, 2]] ị Index these values back into q. [[1, 10, 3, 7], [9, 12, 5, 8]] ) Start a new monadic chain with the result as its argument. Z Zip; transpose rows and columns. [[1, 9], [10, 12], [3, 5], [7, 8]] ’ Decrement; switch to 0-indexing. [[0, 8], [9, 11], [2, 4], [6, 7]]  # CJam, 25 bytes 0q{"[]"#"_ \p_p "S/=~)}/;  Surprisingly competitive - loses only to Japt and Jelly [Edit: and Charcoal and Stax :(] Try it online! ## Explanation 0 Push 0. q Push the input. { }/ For each character in the input: "[]"# Find index of this character in the string "[]" (or -1 if not found). = Use this index to choose " "S/ one of the following snippets ~ and execute it: _ If it was 0 ('['), duplicate the number on the stack. \p_p If it was 1 (']'), print the current number and the one under it. If it was -1, do nothing. ) Increment the number on top of the stack. ; Delete the number.  # Python 2, 109 bytes def a(s,r=[],i=0): o=[] while i<len(s):exec["r+=[i]","o+=[(r.pop(),i)]",'']['[]'.find(s[i])];i+=1 return o  Try it online! # Pyth, 28 26 bytes {I#.e,t+lhfSI/LTY+._>Qk$$


Test suite.

At the moment it's longer than Mnemonic's approach, but I feel like I can golf this down a little and this fortunately also doesn't use Pythonically-imperative structures like V. The initial version was 36 bytes and also had numerous bugs.

### How it works

{I#.e,t+lhfSI/LTY+._>Qk\] – Full program. Takes a quoted string Q from STDIN.
.e                      – Enumerated map. k = iteration index, b = current element.
>Qk   – Get the elements of Q at indices greater than k.
._      – Generates all the prefixes of this.
+     \] – And append an "]" (for handling some edge-cases).
f                – Filter over this list, with T = current element.
L Y             – For each character in str([]), "[]"...
/ T               – ... Count the occurrences of it in T.
SI                  – And check if the values are sorted increasingly.
h                 – Head. Retrieve the first element.
+l                  – Get the length of this + k.
t                    – Decrement (by 1).
,                     – And pair this value with k. Returns [i, k] where i is
the index of the corresponding ] and k is that of [.
#                        – Filter this list by:
{I                             – The pair is invariant over deduplicating.

• {I#.e,t+lhfSI/LTY._>Q aaalmost works for 22 bytes... – Mr. Xcoder Jun 7 '18 at 17:45

# Perl 5, 53 bytes

say"$-[0] ".($+[0]-1)while s/$[^][]*$/1x length\$&/e


Run as perl -nE '<above code snippet>'. Takes input through stdin.

As usual, the optimal Perl solution to the problem is a regular expression. We attempt to match any pair of brackets which does not contain any pairs within it using a rather silly-looking character class (s/$[^][]*$/.../). If the match is successful, we replace the matched text with the digit 1 over and over again so that we don't accidentally match those brackets again, and we print out the indices of the match. Rinse and repeat.

# Stax, 13 bytes

é√p(l▓1½\á²ë(


Run and debug it

It uses the input stack to track open brace pairs. Here's the program unpacked, ungolfed, and commented.

F       iterate over input characters
.][I   get the index of the character in the string "[]", or -1
^|cv   skip the rest of this iteration if index was -1
i~     push the current iteration index to the input stack
C      skip the rest of this iteration if index was 0
\      form a pair with the top two items from the input stack
JP     join with space, and print


Run this one

# Charcoal, 20 bytes

ＦＬθ≡§θι[⊞υι]«Ｉ⊟υ,Ｉι⸿


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

ＦＬθ


Loop over the implicit range of the length of the input string.

≡§θι


Switch on the current character.

[⊞υι


If it's a [ then push the current index to the predefined array variable.

]«Ｉ⊟υ,Ｉι⸿


If it's a ] then pop the latest index from the array variable and print it and the current index separated by a comma and start a new line. Alternate output formats, if acceptable, would save some bytes: ]Ｉ⟦⊟υιω saves 2 bytes but prints each index on a separate line, double-spacing the pairs of indexes; ]Ｉ⟦⊟υι` simply prints the indexes on separate lines, making it hard to distinguish them.