19
\$\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\$
8
  • 2
    \$\begingroup\$ Possible duplicate of Fix unbalanced brackets \$\endgroup\$
    – FUZxxl
    Dec 2, 2015 at 11:09
  • 9
    \$\begingroup\$ @FUZxxl That looks like a much harder challenge. I feel like there is another dupe somewhere though. \$\endgroup\$ Dec 2, 2015 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\$ Dec 2, 2015 at 16:56
  • 1
    \$\begingroup\$ @MartinBüttner: This challenge might be what you were thinking of. \$\endgroup\$ Dec 2, 2015 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, 2015 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\$
0
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\$
3
  • \$\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\$ Dec 3, 2015 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\$ Dec 3, 2015 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\$ Dec 4, 2015 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\$
1
  • \$\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\$ Dec 2, 2015 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\$
1
  • \$\begingroup\$ Ohhh, are you removing the matching parentheses from inside out? That would be a mere 34 bytes in Retina: pastebin.com/bU77LzbR \$\endgroup\$ Dec 2, 2015 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\$
2
  • 1
    \$\begingroup\$ You can omit the space in char* s \$\endgroup\$
    – Cyoce
    Feb 23, 2017 at 17:28
  • \$\begingroup\$ Didn't know that - thanks \$\endgroup\$
    – dj0wns
    Feb 28, 2017 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\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.