Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

You must write a program or function that takes a string of brackets and outputs whether or not that string is fully matched. Your program should print a truthy or falsy value, and IO can be in any reasonable format.

Rules and definitions:

  • For the purpose of this challenge, a "bracket" is any of these characters: ()[]{}<>.

  • A pair of brackets is considered "matched" if the opening and closing brackets are in the right order and have no characters inside of them, such as

    ()
    []{}
    

    Or if every subelement inside of it is also matched.

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

    Subelements can also be nested several layers deep.

    [(){<><>[()]}<>()]
    <[{((()))}]>
    
  • A string is considered "Fully matched" if and only if:

    1. Every single character is a bracket,

    2. Each pair of brackets has the correct opening and closing bracket and in the right order, and

    3. Each bracket is matched.

Test IO

Here are some inputs that should return a truthy value:

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

And here are some outputs that should return a falsy value:

(               Has no closing ')'
}{              Wrong order
(<)>            Each pair contains only half of a matched element
(()()foobar)    Contains invalid characters
[({}<>)>        The last bracket should be ']' instead of '>'
(((()))         Has 4 opening brackets, but only 3 closing brackets.

As usual, this is code-golf, so standard loopholes apply, and shortest answer in bytes wins.

share|improve this question
1  
Related. – Martin Büttner 2 days ago
5  
Note to potential close voters: The challenge I linked also includes a priority order for the bracket types so they cannot be nested in an arbitrary order. I think that makes it sufficiently different. – Martin Büttner 2 days ago
    
Is [} a match? And if not, where is it excluded by these rules? – EJP yesterday
1  
@EJP No, it is not. Each pair of brackets has the correct opening and closing bracket and in the right order. – Dr Green Eggs and Ham DJ yesterday
3  
I will upvote the first solution in Brackets – leo yesterday

17 Answers 17

Retina, 20 bytes

+`\(\)|\[]|{}|<>

^$

Try it online

share|improve this answer

CJam, 25 24 23 21 bytes

Thanks to Sp3000 for saving 2 bytes.
Thanks to jimmy23013 for saving 2 bytes.

q_,{()<>}a`$2/*{/s}/!

Test suite.

Works essentially the same as the other answers: we repeatedly remove (), [], <> and {} from the string and check if we end up with the empty string. To avoid having to check when we're done, we remove the pairs N times where N is the length of the string, which is always sufficient (since each iteration will remove at least two characters, unless we're done). I'm glad to see that this doesn't beat Retina. :) (Although Pyth or Jelly might...)

There's one fun golfing trick here: to get the string ()<>[]{} we use the following:

{()<>}a`$

The, {()<>} is just a block (i.e. a function), which contains the other brackets as code. With a we wrap the block in an array. The ` stringifies that array, which gives "[{()<>}]". Finally, we sort the string with $, which rearranges the brackets to ()<>[]{}.

share|improve this answer
    
I'm not familiar with your language, but your description of your golfing trick makes it sound like ()<>[]{}` would work just as well, and be the same number of bytes, right? – Mooing Duck 8 hours ago
    
@MooingDuck No because ()<> are four operators (decrement, increment, and then comparison or truncation depending on the operands), which would be executed immediately, whereas {} denotes a block (CJam's equivalent of a function), i.e. a piece of code that is just pushed onto the stack without evaluating it immediately. That's why I need {} to wrap the () and <>, but then using a for putting everything in an array is shorter than [...]. – Martin Büttner 1 hour ago

JavaScript (ES6), 52 50 bytes

f=s=>(t=s.replace(/\(\)|\[]|{}|<>/,''))==s?!s:f(t)

Repeatedly remove brackets until the result is the same as the original, then return false unless the string is now empty.

Edit: Saved 2 bytes thanks to @edc65.

share|improve this answer
    
You can safely use a global for t and save 2 bytes : f=s=>(t=s.replace(/\(\)|\[]|{}|<>/,''))==s?!s:f(t) – edc65 26 mins ago

05AB1E, 19 bytes

Input is given in quotes. Code:

"[](){}<>"2÷)"":g2Q

Well crap, a lot of bugs and unimplemented features were found. Explanation:

"[](){}<>"           # Push this string
          2÷         # Split into pieces of two
            )        # Wrap it into an array (which should not be needed)
             ""      # Push an empty string
               :     # Infinite replacement

This is actually a tricky part. What this looks like in pseudocode is:

input().replace(['[]', '()', '{}', '<>'], "")

This is covered by this part from the 05AB1E code:

if type(b) is list:
    temp_string = temp_string_2 = str(a)
    while True:
        for R in b:
            temp_string = temp_string.replace(R, c)
        if temp_string == temp_string_2:
            break
        else:
            temp_string_2 = temp_string
    stack.append(temp_string)

As you can see, this is infinite replacement (done until the string doesn't change anymore). So, I don't have to worry about setting the replacement into a loop, since this is already builtin. After that:

                g    # Take the length of the final string
                 2Q  # Check if equal with 2 (which are the quotes at the end)

Uses CP-1252 encoding. Try it online!

share|improve this answer

Pyth, 31 25 24 bytes

Golfed down to 25 bytes thanks to FryAmTheEggMan Removed 1 byte

VQ=:Q"<>|\[]|{}|\(\)"k;!

Try it here: Test suite !

I'm still a Pyth newbie, any help is appreciated.

Explanation

VQ                         For N in range(0, len(z)), with Q being the evaluated input.
                           Optimal solution would be to use range(0, len(z)/2) instead, but it add two bytes.
  =:Q"<>|\[]|{}|\(\)"k     assign Q without {}, [], <> nor () (regex replacement) to Q
                      ;    End of For loop
                       !   Logical NOT of Q's length (Q is the input, but has gone several times through y, and Q is implicit).
                           This last operation returns True if len(Q) is 0 (which means all brackets were matched), False otherwise

BTW, congrats to the other Pyth answer (which is currently 20 bytes)

share|improve this answer
    
Welcome to Programming Puzzles and Code Golf! – Adnan yesterday
    
@Adnan Thank you ! This is my first golf ! – FliiFe yesterday
    
Nice first golf! With some rearranging and stuff, you can get to 25: Vz=:z"<>|\[]|{}|\(\)"k;!z. Particularly of note, you basically never need to use l if you don't actually need the number, and = automatically guesses the first variable used in an expression. Let me know if you would like me to explain anything else in the Pyth chatroom :) – FryAmTheEggman yesterday
    
@FryAmTheEggman Thanks ! I didn't know l was unnecessary, that's good to know. At first, I declared a function because my logic was different, and forgot to remove it. Shall I include your answer to mine ? (I'm a newbie >.<) – FliiFe yesterday
3  
Generally, if it's posted in a comment then the comment author wants you to use it. So go right ahead! :) – FryAmTheEggman yesterday

Yacc, 119 bytes

Does not use regex/replace.

%%input:r;r:%empty|'['r']'r|'{'r'}'r|'('r')'r|'<'r'>'r;%%yylex(){return getchar();}main(){return yyparse();}yyerror(){}

Ungolfed

%%                              # Grammar in BNF
input:
  r;
r:
  %empty
| '['r']'r
| '{'r'}'r
| '('r')'r
| '<'r'>'r;
%%                              # Minimal parser invocation and lexer
yylex(){return getchar();}
main(){return yyparse();}
yyerror(){}

Compilation

yacc -o bracket.c bracket.y
cc -o bracket bracket.c

Usage

~/ % echo -n "<()[]>" | ./bracket
~/ %
~/ % echo -n "{" | ./bracket
~/ 1 %                                                                         :(
share|improve this answer

Pyth, 20 bytes

!uuscNTc"[](){}<>"2G

Try it online: Test Suite

Repeatedly removes occurrences of [], (), <> and {} by splitting and re-merging. Checks if the resulting string is empty or not.

share|improve this answer

Python, 67 bytes

lambda s:eval("s"+".replace('%s','')"*4%([],(),{},'<>')*len(s))==''

Generates and evals an expression that looks like

s.replace('[]','').replace('()','').replace('{}','').replace('<>','').replace('[]','').replace('()','').replace('{}','').replace('<>','')

and checks if the result is empty.

Sp3000 saved 8 bytes by pointing out that [],(),{} can be subbed in without quotes because they're Python objects, and that two parens were unneeded.

share|improve this answer

Javascript ES6, 54 bytes

f=_=>_.match(x=/\(\)|\[]|{}|<>/)?f(_.replace(x,'')):!_

Uses a recursive replace implementation. Simple enough.

share|improve this answer

Grime v0.1, 34 bytes

M=\(M\)|\[M\]|\{M\}|\<M\>|MM|_
e`M

Prints 1 for a match and 0 for no match. Try it online!

Explanation

Grime is my 2D pattern-matching language designed for this challenge; it can also be used to match 1D strings. This is my first answer with it. I did modify Grime today, but only to change the character of one syntax element (` instead of ,), so it doesn't affect my score.

M=                         Define pattern called M that matches:
\(M\)|\[M\]|\{M\}|\<M\>      a smaller M inside matched brackets,
|MM                          or two smaller Ms concatenated,
|_                           or the empty pattern.
e`M                        Match the entire input against M.
share|improve this answer

Regex (PCRE flavor), 41 37 bytes

^((<(?1)>|{(?1)}|\[(?1)]|\((?1)\))*)$

Just a standard solution with recursive regex.

Thanks jimmy23013 for shaving off 4 bytes

share|improve this answer

Perl, 34 bytes

Includes +2 for -lp

Run with input on STDIN:

./brackets.pl <<< "{<>()}"

brackets.pl:

#!/usr/bin/perl -lp
1while s/\(\)|\[]|<>|{}//;$_=!$_
share|improve this answer

C, 121 122 114 bytes

Shaved of 8 bytes thanks to @xsot!

a[99],i,k;main(c){for(;read(0,&c,!k);c%7&2?k|=a[i--]^c/9:(a[++i]=c/9))k|=!strchr("()[]{}<>",c);putchar(48+!k*!i);}

Uses a stack.

share|improve this answer
    
I like the c%7&2. Actually, you don't need k. Instead, you can simply increment i where you would modify k since you need to check if i is zero eventually anyway. Something like this (untested code): a[99],i;main(c){for(;read(0,&c,1);c%7&2?i+=a[i--]^c/9:(a[++i]=c/9))i+=!strchr("‌​()[]{}<>",c);putchar(48+!i);}. – xsot 21 hours ago
    
@xsot - Will incrementing i work? We also need to avoid subscripting the array with a negative value, so we have to test either i or k in the for. – mIllIbyte 20 hours ago
    
Ah I see. There's still room for improvement though: a[99],i,k;main(c){for(;read(0,&c,!k);c%7&2?k|=a[i--]^c/9:(a[++i]=c/9))k|=!strch‌​r("()[]{}<>",c);putchar(48+!i*!k);} – xsot 19 hours ago
    
@xsot - Thank you! To sum up the savings, read saved 5 bytes, ^ saved one and the middle operand of the conditional operator saved 2. I am surprised that the middle operand of the conditional operator can be an assignment. I thought that there would be an error, something like "missing : before = ". – mIllIbyte 15 hours ago
    
@xsot - I tried incrementing i instead of using k, as you first suggested: a[99],i;main(c){for(;read(0,&c,1);c%7&2?i+=a[i]^c/9?1:-1:(a[++i]=c/9))i+=!strch‌​r("()[]{}<>",c);putchar(48+!i);} But this does not work yet for input like ())), since "popping" from the stack does not actually zero the values in the array. – mIllIbyte 15 hours ago

Python 2, 80 bytes

def m(s,i=0):exec's=s.replace("[({<])}>"[i%4::4],"");i+=1;'*4*len(s);return"">=s
share|improve this answer

sed, 39 bytes

:a
s/\(\)|\[]|<>|\{}//;ta
/./{c0
q}
c1

sed version of what appears to be the standard approach. Requires extended regular expressions (sed -r)

share|improve this answer

Reng v.3.3, 137 bytes, noncompeting

Try it here!

aií0#zl2,q!~1ø
:"]"eq!v:"}"eq!v:">"eq!v:")"eq!v)1z+#z
ve¤[2-2<       <       <     +1<
>]?v$$$zÀ0#z >ðq!vlqv¤l2%[1Ø
   \$2+)1z+#z/   ~n1/

There's a bit more golfing to be done, but at least it works. I added a command ð to keep track of stacks after this challenge in order for this to be remotely possible/easily. I'll explain this in a bit, but it generally keeps track of all strings iterated over and looks for repeats; if there is a repeat, then the string is irreducible. Otherwise, the string will be reduced to the empty string/stack, and will output 1. Otherwise, no output will be produced.

share|improve this answer

PowerShell v2+, 63 62 bytes

param($a)for(;$a-ne$b){$a=($b=$a)-replace"\[\]|\(\)|<>|{}"}!$a

Can't quite catch JavaScript, but is currently edging out the other non-esolangs.

Similar approach as other answers: a simple loop that continues so long as we can remove one of [], (), or <> (with several extraneous characters because we need to escape the regex specials). We use $b as a helper along the way to remember what our previous loop's $a was set as. An uninitialized variable is $null, so the first time the loop is encountered, $a is obviously not equal to $null.

At the end of the loop, $a is either empty or not, and the Boolean-not of that string is either True or False.

Example

PS C:\Tools\Scripts\golfing> .\are-the-brackets-fully-matched.ps1 "[({})]"
True

PS C:\Tools\Scripts\golfing> .\are-the-brackets-fully-matched.ps1 "[({])}"
False
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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