Golf A Parentheses Matching Algorithm

Question

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 code-golf, so the shortest code in bytes for each programming language wins.

Answer 1

Brain-Flak Classic, 108 bytes

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

Try it online!

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

Answer 2

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!

Answer 3

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

Answer 4

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[]_[]=[]

Answer 5

QBasic (QB64), 137 127 112 bytes

INPUT a$
for i=0to len(a$)
c$=mid$(a$,i+1,1)
if"["=c$then
b(n)=i
n=n+1
elseif"]"=c$then
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:

Answer 6

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)

Answer 7

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!

Answer 8

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.

Answer 9

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

Answer 10

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]]

Answer 11

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

Answer 12

Retina, 36 bytes

L$v`\[((\[)|(?<-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 ].

Answer 13

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 

Answer 14

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

Answer 15

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!

Answer 16

Jelly, 20 bytes

=©ⱮØ[_/aÄ$+®ŻĠḊẎ_2s2

Try it online!

It has a side-effect on the register, hope it's allowed to be a function.

Answer 17

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

Answer 18

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)

Answer 19

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.

Answer 20

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]]

Answer 21

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!

Answer 22

Pyth,  28  26 bytes

{I#.e,t+lhfSI/LT`Y+._>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/LT`Y+._>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.

Answer 23

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.

Answer 24

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

Answer 25

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.