20
\$\begingroup\$

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

\$\endgroup\$
  • 2
    \$\begingroup\$ Possible duplicate of Fix unbalanced brackets \$\endgroup\$ – FUZxxl Dec 2 '15 at 11:09
  • 9
    \$\begingroup\$ @FUZxxl That looks like a much harder challenge. I feel like there is another dupe somewhere though. \$\endgroup\$ – Martin Ender Dec 2 '15 at 11:17
  • \$\begingroup\$ @MartinBüttner Yes, it can. I've added some testcases. And did you find the duplicate you were looking for? \$\endgroup\$ – ghosts_in_the_code Dec 2 '15 at 16:56
  • 1
    \$\begingroup\$ @MartinBüttner: This challenge might be what you were thinking of. \$\endgroup\$ – Ilmari Karonen Dec 2 '15 at 22:52
  • 1
    \$\begingroup\$ I think we should close the other question as a duplicate of this; this is better because it has fewer bonuses. \$\endgroup\$ – lirtosiast Dec 3 '15 at 3:55

10 Answers 10

5
\$\begingroup\$

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.

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

Retina, 34

Firstly, credit where credit is due:

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
$ 
\$\endgroup\$
  • \$\begingroup\$ @ThomasKwa See the test output. I believe the code is correct and all testcases are passing. Was there a particular problem you see in the code, or particular testcase you think will fail? \$\endgroup\$ – Digital Trauma Dec 3 '15 at 3:58
  • \$\begingroup\$ @ThomasKwa I didn't port their code, because I have no clue what any piece of ESMIN does. I just wrote this code based on what it looked like it would do, so I don't think there's any reason this should have the same bug. \$\endgroup\$ – Martin Ender Dec 3 '15 at 10:44
  • \$\begingroup\$ Wow, @MartinBüttner, you got it right! Yeah, I thought that recursively replacing matching brackets inside-out was most logical. A quick tweak to fit the code specs made it work. \$\endgroup\$ – Mama Fun Roll Dec 4 '15 at 3:45
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ See my comment on molarmanful's answer for the Retina version of the exact same solution (at 34 bytes; printing 0 or 1). I can't say who should post it, but it should probably be one of the two of you. \$\endgroup\$ – Martin Ender Dec 2 '15 at 17:50
3
\$\begingroup\$

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

𝔼𝕊𝕄𝕚𝕟, 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:

!ïċ/⁅⬮[\]{}]⌿)ė`⬮”ė`{}”ė`[]”
\$\endgroup\$
  • \$\begingroup\$ Ohhh, are you removing the matching parentheses from inside out? That would be a mere 34 bytes in Retina: pastebin.com/bU77LzbR \$\endgroup\$ – Martin Ender Dec 2 '15 at 14:49
2
\$\begingroup\$

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

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ You can omit the space in char* s \$\endgroup\$ – Cyoce Feb 23 '17 at 17:28
  • \$\begingroup\$ Didn't know that - thanks \$\endgroup\$ – dj0wns Feb 28 '17 at 22:51
1
\$\begingroup\$

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.

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

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=='')
\$\endgroup\$
1
\$\begingroup\$

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