Bracket balancing

Question

You will be given a (possibly empty) string containing brackets ([{()}]) and any other characters (A-Z, a-z, 0-9, punctuation). You need to check if it adheres to the following rules:

• Non-bracket characters are ignored.
• Every open bracket [{( has a closing bracket )}]. So []( is not allowed.
• Brackets are nested properly. [(]) is not allowed.
• Curly brackets cannot contain square brackets within them. Simple brackets cannot contain either curly or square brackets within them. So [({})], [{[]}] and ({}) are not allowed. Brackets can be nested with similar brackets, so [[{((()))}{{(())}}]()]{()} is allowed.

Output is a single truthy/falsey value as per your choice.

Shortest code wins.

---

Test cases

b[[a{(/)}(())+={{}-}],] -> Valid

([h][e][l][l][o]) -> Invalid

[///[{(\/(arg()))}1{{((-)-2)}}]()]{()} -> Valid

hi -> Valid

Answer 1

Retina, 84 bytes

^([^][}{)(]|()\(|(?<-2>)\)|(?!\2)((){|(?<-4>)}|(?!\4)(()\[|(?<-6>)])))*$(?!\2|\4|\6)

Try it online.

This is a fairly straight-forward (but golfed) extension of the basic parentheses-checking .NET regex.

While this is quite possible with balancing groups, Perl's recursion definitely has the edge here. However, either approach is beaten by ditching the elegance of a single regex match in favour of reducing the input gradually via repeated substitutions, as Digital Trauma's sed answer does. This can be implemented in 34 bytes in Retina, but I'm hesitant to post the code myself, as I didn't come up with the idea.

Answer 2

Retina, 34

Firstly, credit where credit is due:

• @ןnɟuɐɯɹɐןoɯ who first posted this approach.
• @MartinBüttner who suggested this exact answer but was too good of a sportsman not to post it himself.

I independently (later) came up with the same approach in sed, so I hope I'm not treading on any toes (big or otherwise) by posting this:

[^][(){}]

+`\(\)

+`{}

+`\[]

^$

So now with a sudo apt-get install mono-complete and git clone https://github.com/mbuettner/retina.git I have a working retina on my Ubuntu VM. Here's the test output:

$ while read; do echo "Input: \"$REPLY\", Ouput: $( mono Retina.exe -s brbal.ret <<< "$REPLY" )" ; done < ../brbal.txt 
Input: "[[{((()))}{{(())}}]()]{()}", Ouput: 1
Input: "b[[a{(/)}(())+={{}-}],]", Ouput: 1
Input: "[///[{(/(arg()))}1{{((-)-2)}}]()]{()}", Ouput: 1
Input: "hi", Ouput: 1
Input: "", Ouput: 1
Input: "", Ouput: 1
Input: "([h][e][l][l][o])", Ouput: 0
Input: "[](", Ouput: 0
Input: "[(])", Ouput: 0
Input: "[({})]", Ouput: 0
Input: "[{[]}]", Ouput: 0
Input: "({})", Ouput: 0
$ 

Answer 3

, 43 chars / 62 bytes

!Մ(Մ(Մ(ïċ/⁅⬮[\]{}]⌿),`⬮`,⬯),`{}`,⬯),`[]`,⬯)

Try it here (Firefox only).

Nope.

---

However, if I use newly implemented features, I can get down to 28 chars / 47 bytes:

!ïċ/⁅⬮[\]{}]⌿)ė`⬮”ė`{}”ė`[]”

Answer 4

Sed, 53

s/[^][(){}]//g
:;s/()//;t
:b;s/{}//;tb
:c;s/\[\]//;tc

Here I am claiming that since sed does not really have a concept of truthy/falsey, then I am defining the empty string to mean truthy and all other strings to mean falsey.

If that is not acceptable, then we can add a couple of lines, thus:

Sed, 66

s/[^][(){}]//g
:;s/()//;t
:b;s/{}//;tb
:c;s/\[\]//;tc
/./c0
/^$/c1

This outputs 0 for false and 1 for true.

Answer 5

CJam, 27 26 bytes

"(){}[]"q1$f&_,@2/e*{/s}/!

This prints 1 (truthy) or 0 (falsy). Try it online! or verify all test cases.

How it works

"(){}[]"                    Push that string.
        q                   Read all input and push it on the stack.
         1$                 Copy the bracket string.
           f&               Intersect each input character with the bracket string.
                            This pushes an array of singleton and empty strings.
             _,             Get the length of the array (L), i.e., the number of
                            characters in the original input.
               @            Rotate the bracket string on top of the stack.
                2/          Split it into ["()" "{}" "[]"].
                  e*        Repeat each character pair L times.
                    {  }/   For each character pair.
                     /      Split the string on the stack at occurrences of that
                            character pair. This dosn't work properly the first
                            time, since there's a string array on the stack.
                      s     Flatten the resulting array of strings.
                         !  Apply logical NOT.

Answer 6

Japt, 42 37 bytes

Saved 5 bytes with a feature I didn't realize my own language had... Thanks for adding it, @Downgoat!

Japt really needs better RegExp support...

!Uo"()[\\]\{}" e"\\(\\)" e"\{}" e"\\[]

Try it online!

How it works

               // Implicit: U = input string
Uo"()[\\]\{}"  // Remove all non-bracket.
e"\\(\\)"      // Recursively remove all pairs of simple brackets.
e"\{}"         // Recursively remove all pairs of curly brackets.
e"\\[]         // Recursively remove all pairs of square brackets.
!              // Return the Boolean NOT of the result.
               // (true for empty string, false for anything else)
               // Implicit: output last expression

Answer 7

C99, 226 208 207 Bytes

This is my first time ever trying to golf something

#define S s[i]
t(s,i)char*s;{int a[]={['[']=0,['{']=0,['(']=0};for(i=0;S*!(S=='{'&a['(']|S=='['&(a['(']|a['{'])|S==']'&(a['(']|a['{'])|S=='}'&a['(']);i++)a[S]++,a[S-S/90-1]--;return !(a['[']+a['{']+a['(']);}

Readable:

int t(char* s){
    int a[265]={['[']=0,['{']=0,['(']=0};
    for(int i=0;s[i]&&!((s[i]=='{'&a['(']>0)|(s[i]=='['&(a['(']>0|a['{']>0))|(s[i]==']'&(a['(']>0|a['{']>0))|(s[i]=='}'&a['(']>0));i++){
        a[s[i]]++;
        a[s[i]-(s[i]/90+1)]--;
    }
    return !(a['[']+a['{']+a['(']);
}

There is a buffer overflow but it doesnt seem to affect anything - I believe this is due to alignment.

Answer 8

Python 3, 196 170 160 154 bytes

Awkwardly long, thanks to Mego for saving 6 bytes:

d=y=""
for C in input():
 for a in "[](){}":y+=C*(C==a)
 y=y.replace("()",d)
x=y
for r in y:x=x.replace("{}",d)
for s in y:x=x.replace("[]",d)
print(x==d)

Answer 9

Perl, 50 + 1 = 51 bytes

$_=/^((([^][)(}{]|\((?3)*\))|{(?2)*})|\[(?1)*])*$/

Requires the -p flag and prints 1 for truthy and nothing for falsy results. I'm counting -p as one, because it can be combined with -e:

> perl -pe '$_=/^((([^][)(}{]|\((?3)*\))|{(?2)*})|\[(?1)*])*$/'

The code is basically just a plain regex match against the input, using Perl's nifty recursive regex feature.

Thanks to Dennis for helping me test this and golf the Perl boilerplate.

Answer 10

Python 3 : 120 bytes

Building on @Adnan's answer, re proved shorter to use:

import re
x=re.sub('[^[\](){}]','',input())  
for i in('()','{}','[]'):  
 while x.find(i)>=0:x=x.replace(i,'')  
print(x=='')