56
\$\begingroup\$

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.

  • You may assume the input will only contain printable ASCII.

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Related. \$\endgroup\$ – Martin Ender Apr 5 '16 at 6:42
  • 7
    \$\begingroup\$ 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. \$\endgroup\$ – Martin Ender Apr 5 '16 at 6:55
  • \$\begingroup\$ Is [} a match? And if not, where is it excluded by these rules? \$\endgroup\$ – user207421 Apr 5 '16 at 13:13
  • 2
    \$\begingroup\$ @EJP No, it is not. Each pair of brackets has the correct opening and closing bracket and in the right order. \$\endgroup\$ – DJMcMayhem Apr 5 '16 at 13:17
  • 6
    \$\begingroup\$ I will upvote the first solution in Brackets \$\endgroup\$ – leo Apr 5 '16 at 14:27

32 Answers 32

17
\$\begingroup\$

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! (slightly modified because the above version is deprecated).

\$\endgroup\$
  • 1
    \$\begingroup\$ Nicely golfed ! \$\endgroup\$ – SamyQc Apr 7 '16 at 13:00
  • 1
    \$\begingroup\$ Was this before õ was added? \$\endgroup\$ – Zacharý Sep 10 '17 at 17:20
  • \$\begingroup\$ @Zacharý Yes, that is correct \$\endgroup\$ – Adnan Sep 10 '17 at 17:21
33
\$\begingroup\$

Brain-Flak, 1101, 1085, 981 bytes

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

Try it online!

This is 980 bytes of source code, and +1 for the -a flag allowing ASCII input (but decimal output)

This is an answer I've been wanting to write for a very very long time. At least 6 months. I waited to post this because I knew that answering this challenge would be extra hard in brain-flak. But it's worth it for one very important reason: The source code itself is a truthy input, which is the entire point of this language itself.

And as I wrote about here, this question was what inspired me to write brain-flak.

Shortly after I wrote Are the brackets fully matched?, it made me wonder how much information you can store with only matched brackets. One thing that stood out to me, was that even though you only have 4 "atoms" of sorts:

(){}[]<>

you really have 8 units of information to convey, since each of these bracket types can be empty, or have other brackets in between, which are fundamentally different pieces of information. So, I decided to write a language that only allowed for matched brackets, and where empty brackets convey something different than brackets with other brackets inside of them.

This answer took roughly two hours to write. I'll admit it's pretty poorly golfed, mostly because a lot of the code is repeated for each bracket type. But I'm mostly amazed that I was able to write an answer at all, especially given that Brain-Flak is

A minimalist esolang designed to be painful to use

I'm going to attempt to golf it down later, but I wanted to get this out there anyway.

I have a detailed explanation, but it's about 6 thousand characters long, so I think it would not be wise to paste the entire thing into this answer. You can read through it here if you want. I'll add a shorter explanation here.

The basic idea, is that we repeat the following steps for every character on the stack:

  • We check each character to see if it matches any bracket. If it is an opening bracket, we push a number onto the other stack according to the following mapping:

    ( = 1
    < = 2
    [ = 3
    { = 4
    
  • Then we check to see if it matches any closing bracket. If it does, we push the equivalent number onto the alternate stack, just like for opening brackets. Then, we check if the top two numbers are equal. If they are, the both get popped and the program continues as normal. If they are not, we clear both stacks (to stop the looping) and push a one onto the alternate stack. This is essentially a "break" statement.

  • After checking the 8 bracket types, we push the value of this run through the loop. Since we zero out most of it, the only snippets that have any value are the conditionals when we compare against brackets. So if any bracket is matched, the whole loop has a value of 1. If none of them did, the whole loop has a value of 0. In this case, we will clear both stacks and push a 0 onto the alternate stack. Again, this is like a "break" statement.

After this main loop is running, the rest is fairly simple. We are on the (empty) main stack, and the alternate stack is empty (if the brackets were matched) or non-empty if they were not. So we run this:

#Toggle to the alternate stack
<>

#Push this stack-height onto main-stack
([]<>)

#Logical not
({}<(())>){((<{}{}>))}{}

This will push a 0 or a 1 onto the main-stack, and when the program ends it is implicitly printed.


  • Thanks to @WheatWizard for coming up with a good stack-clean "equals" and "logical not" snippet, and for regularly updating the github wiki with useful examples.

  • Thanks to @ASCII-only for writing an online integer metagolfer which helped immensely in writing this program


revisions

  • Removed some push pop redundancy

  • Changed my zero counter logic

\$\endgroup\$
  • 1
    \$\begingroup\$ Awwwwwweeeeesommmmeeeee! \$\endgroup\$ – Arjun Mar 29 '17 at 2:29
23
\$\begingroup\$

Brain-Flak, 204 196 190 bytes

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

Try it online!

-8 bytes thanks to Wheat Wizard. -6 bytes thanks to Jo King.

Explanation

This program stores the character codes of all current unclosed brackets on the second stack. The bracket pairs <>, [], and {} each have character codes that differ by exactly 2, so there is no need to check for them specifically. The pair () only differs by 1, so we check for ( specifically, and effectively decrement that byte (actually increment every other byte) before continuing.

# While there are bytes left to process
{

 # Move byte to second stack
 ({}<>)<>

 # Push 40, 0, 40, 60, 91, 123: (, then null, then all four opening brackets
 ((((()()()()()){})(({}){})())({}(({})((({}){})(<()>))))())

 ((

   # For each opening bracket type:
   {

    # Evaluate as zero
    <

     # Compute difference between bracket type and input byte
     ({}<>[({})])

    >

    # Evaluate loop iteration as -1 if equal, 0 otherwise
    [()]{()(<{}>)}{}<>

   }

   # Remove the 0 that was inserted to terminate that loop
   {}

   # Add 1 to result
   ()

   # Evaluate rest of this expression as zero
   <

    # Determine whether the byte is open parenthesis
    ({}<>[({})])

    # If not:
    {

     # Add 1 to byte and break if
     (<{}({}())>)

    }{}

    # Return to main stack
    <>

   >

 # Push result twice (0 if matched an opening bracket, 1 otherwise)
 ))

 # If byte was not an opening bracket:
 {

  # Push zero to break out of if
  (<

    # Push (open bracket + 2 - byte) below that zero
    ({}{}<>[{}]{}<>)

  >)

 }{}

 # If byte was neither an opening bracket nor the appropriate closing bracket:
 {

  # Clear alternate stack and stay there to break out of main loop early
  <>{{}}

 }{}

# End of main loop
}

# If a prefix was invalid, the top of the other stack is the same nonzero value
# that made us break out in the first place. If the string was a valid prefix,
# the other stack contains every unclosed bracket.  If the string is balanced,
# there are none of these. Thus, the other stack is empty if the
# brackets are balanced, and has a nonzero value on top otherwise.

# Push 1 on other stack if empty, and 0 on current stack otherwise
<>((){[()]<>})
\$\endgroup\$
  • \$\begingroup\$ "logical not of difference" (also known as equals) could be shorter as ([{}]<>({}))((){[()](<{}>)}{}) \$\endgroup\$ – Sriotchilism O'Zaic Sep 9 '17 at 3:54
  • \$\begingroup\$ I think you can replace that last check with ({<>[()]}()) for -6 bytes \$\endgroup\$ – Jo King Apr 27 '18 at 1:02
  • \$\begingroup\$ @JoKing Thanks. I don't think I ever would have spotted that. \$\endgroup\$ – Nitrodon Apr 27 '18 at 1:42
  • \$\begingroup\$ Yeah, I figured it out in my own answer and realised it was applicable to yours as well \$\endgroup\$ – Jo King Apr 27 '18 at 1:47
13
\$\begingroup\$

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.

\$\endgroup\$
11
\$\begingroup\$

Retina, 20 bytes

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

^$

Try it online

\$\endgroup\$
11
\$\begingroup\$

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 ()<>[]{}.

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Mooing Duck Apr 6 '16 at 23:20
  • 1
    \$\begingroup\$ @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 [...]. \$\endgroup\$ – Martin Ender Apr 7 '16 at 7:11
10
\$\begingroup\$

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.

\$\endgroup\$
8
\$\begingroup\$

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 %                                                                         :(
\$\endgroup\$
7
\$\begingroup\$

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)

\$\endgroup\$
  • \$\begingroup\$ Welcome to Programming Puzzles and Code Golf! \$\endgroup\$ – Adnan Apr 5 '16 at 12:07
  • \$\begingroup\$ @Adnan Thank you ! This is my first golf ! \$\endgroup\$ – FliiFe Apr 5 '16 at 12:08
  • \$\begingroup\$ 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 :) \$\endgroup\$ – FryAmTheEggman Apr 5 '16 at 12:50
  • \$\begingroup\$ @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 >.<) \$\endgroup\$ – FliiFe Apr 5 '16 at 13:50
  • 3
    \$\begingroup\$ Generally, if it's posted in a comment then the comment author wants you to use it. So go right ahead! :) \$\endgroup\$ – FryAmTheEggman Apr 5 '16 at 13:53
6
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

Javascript ES6, 54 bytes

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

Uses a recursive replace implementation. Simple enough.

\$\endgroup\$
4
\$\begingroup\$

Regex (PCRE flavor), 41 37 bytes

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

Just a standard solution with recursive regex.

Thanks jimmy23013 for shaving off 4 bytes

\$\endgroup\$
4
\$\begingroup\$

Perl, 34 33 bytes

Includes +2 for -lp

Run with input on STDIN:

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

brackets.pl:

#!/usr/bin/perl -lp
s/\(\)|\[]|<>|{}//&&redo;$_=!$_

Finds the first bracket pair without anything between them and removes it as long as there are any. Then checks if the final string is empty.

\$\endgroup\$
  • \$\begingroup\$ Wouldn't s/\(\)|\[]|<>|{}//&&redo;$_=!$_ work? :) \$\endgroup\$ – Dada Jan 11 '17 at 10:47
  • \$\begingroup\$ It would be great if you can provide explanation also. \$\endgroup\$ – Prashant Pokhriyal Dec 3 '17 at 15:55
  • \$\begingroup\$ @Dada Of course. I must be getting senile.. \$\endgroup\$ – Ton Hospel Feb 5 '18 at 20:04
4
\$\begingroup\$

Brain-Flak, 204 bytes

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

Try it online!

Not quite as short as Nitroden's answer, but uses a very different approach. This one runs through the input repeatedly, removing neighbouring matching pairs of brackets each time until there are none left. At that point if there is anything left on the stack, then the string was not fully matched.

Explanation:

(())  Push 1 to simulate the check at the start of the loop
{  While check
	{}           Pop check
	{({}<>)<>}<> Reverse input
	({           Loop over input
		< Don't push the values of these calculations
		(<(({})<>)>)  Create a copy of the top of the input and push to the other stack
		(((((
		((([(())()()()]){}){}){}())
		(()))
		(((())()){}()){})
		){})          Push the differences in values of the end brackets 
		(({<(({}<>{}[()]))>(){[()](<{}>)}{}<>}{}))  If the copy is the same as any of these, push the difference between the other bracket twice
		<>{}<>  Pop copy
		{  If this character is a start bracket
			{}({}[({})]<>({}))  Check if the next character is the end bracket
			{(<>)(<>)}{}          If not, push a 0 to each stack as buffer
			{}       Pop the top of the input stack, either the start bracket if they matched or the buffer 0
			(<>)     Push 0 to other stack to end check
		}{}>
		{}   Pop the top of the other stack
		         If the character was not an end bracket, pop the copy of check, which is 0
		         If it was, but didn't match the next character, pop the buffer 0
		         If the brackets matched, pop the end bracket and add it to the loop total
	<>}	Repeat with the rest of the input
	<>)	Push the loop total
		If any brackets were matched, the loop total is non zero
}{}
((){<>[()]}) If there is anything left on the stack, push 0 to the other stack, otherwise push 1
\$\endgroup\$
3
\$\begingroup\$

Brainfuck, 132 bytes

+>,[[<->>+>[-]<<-]<[>+>[<+<+>>>+<-]+++++[>--------<-]>[<<+>++++[>-----<-]>[<++++
+[>------<-]>-[<++++[>--------<-]>[,>]]]]<],]<<[>]>.

Formatted:

+>,
[
  [<-> >+>[-]<<-]
  <
  [
    not matching closing bracket
    >+>[<+<+>> >+<-]
    +++++[>--------<-]
    >
    [
      not open paren
      <<+>
      ++++[>-----<-]>
      [
        not open angle bracket
        <+++++[>------<-]>-
        [
          not open square bracket
          <++++[>--------<-]>
          [
            not open brace
            ,>
          ]
        ]
      ]
    ]
    <
  ]
  ,
]
<<[>]
>.

Expects input without a trailing newline. Prints \x00 for false and \x01 for true.

Try it online.

Approach: Maintain a stack starting with \x01, and push the corresponding closing bracket whenever an opening bracket is encountered. Before checking whether the current character is an opening bracket, first check whether it's equal to the closing bracket at the top of the stack, and if so pop it. If it's neither the proper closing bracket nor an opening bracket, consume the rest of the input while moving the pointer to the right. At the end, check whether the pointer is next to the initial \x01.

\$\endgroup\$
2
\$\begingroup\$

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

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.

\$\endgroup\$
2
\$\begingroup\$

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

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.

\$\endgroup\$
  • \$\begingroup\$ 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);}. \$\endgroup\$ – xsot Apr 6 '16 at 10:45
  • \$\begingroup\$ @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. \$\endgroup\$ – mIllIbyte Apr 6 '16 at 12:04
  • \$\begingroup\$ 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|=!strchr("()[]{}<>",c);putchar(48+!i*!k);} \$\endgroup\$ – xsot Apr 6 '16 at 13:10
  • \$\begingroup\$ @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 = ". \$\endgroup\$ – mIllIbyte Apr 6 '16 at 16:21
  • \$\begingroup\$ @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+=!strchr("()[]{}<>",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. \$\endgroup\$ – mIllIbyte Apr 6 '16 at 16:59
2
\$\begingroup\$

Java 7, 156 151 bytes

class A{public static void main(String[]a){for(int i=0;i<-1>>>1;++i,a[0]=a[0].replaceAll("<>|\\[]|\\(\\)|\\{}",""));System.out.print(a[0].isEmpty());}}

I'm not expecting this to win any awards but I didn't see a Java answer yet. Additionally, I like to lurk around PPCG and I would enjoy being able to vote/comment on other answers.

Input is given as program parameters. This follows the same format as many other answers here in that it preforms a regex replacement in a loop. Originally I had it loop N times where N is the length of the original string but looping to Integer.MAX_VALUE is shorter :]. This should be ok because Integer.MAX_VALUE is the maximum length of a String in Java so there's an implicit assumption that the length of input is something that is handle-able by Java. The runtime is pretty bad (took about 20 minutes on my lappytop) on account of the loop but I didn't see any restriction on that.

\$\endgroup\$
2
\$\begingroup\$

Haskell, 151 bytes

infix 1#
'(':x#y=x#')':y
'<':x#y=x#'>':y
'[':x#y=x#']':y
'{':x#y=x#'}':y
')':x#')':y=x#y
'>':x#'>':y=x#y
']':x#']':y=x#y
'}':x#'}':y=x#y
""#""=1
_#_=0

Try it online!

\$\endgroup\$
  • \$\begingroup\$ A few things: As the function (#) needs to be called with the empty string as second argument, you need to count (#"") towards your byte count. Also only True and False are considered truthy/falsy, see the Guide to Golfing Rules. \$\endgroup\$ – Laikoni Feb 6 '18 at 7:56
  • 1
    \$\begingroup\$ However the four lines with the closing parentheses can be replaced by a:x#b:y|a==b=x#y, bringing the bytes down to 113: Try it online! \$\endgroup\$ – Laikoni Feb 6 '18 at 7:56
  • 2
    \$\begingroup\$ 109 bytes: Try it online! \$\endgroup\$ – Laikoni Feb 6 '18 at 8:08
2
\$\begingroup\$

Python 2.7, 96 bytes

def r(s):i=max(map(s.find,['()','[]','{}','<>']));return not len(s)if i<0 else r(s[:i]+s[i+2:])
\$\endgroup\$
  • 2
    \$\begingroup\$ Welcome to the site! \$\endgroup\$ – DJMcMayhem Jun 18 '18 at 4:41
1
\$\begingroup\$

Python 2, 80 bytes

def m(s,i=0):exec's=s.replace("[({<])}>"[i%4::4],"");i+=1;'*4*len(s);return"">=s
\$\endgroup\$
1
\$\begingroup\$

Julia, 51 bytes

~z=z==(n=replace(z,r"\(\)|\[]|{}|<>",""))?z=="":~n

The least insane of several options. Unsurprisingly, leveraging the power of regex is the shortest path to string matching, but this really only applies if the pattern to match is regular. Trying to do PCRE recursive patterns ends up ballooning the size of the code, either by seeing if the whole string is the match or by anchoring the ends and then creating a construct to specify the inner body for regex recursion. Neither of which are pretty or conducive to code golf.

Explanation:

~z=                            # Define ~z to be the following:
    z==(                       # If z is equal to                                     
        n=replace(z,           # z with the replacement of 
            r"\(\)|\[]|{}|<>", # adjacent matching brackets ((),[],{}, or <>)
            ""                 # with empty strings
        )                      # (which is assigned to n)
    )?z==""                    # whether z is an empty string
    :~n                        # else ~ applied to the substituted string

The function repeatedly removes adjacent pairs of parentheses from its only argument, and returns true if it can derive an empty string this way.

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

sed, 39 36 bytes (34 for code, 2 for -r)

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

Try it online!

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

Saved 3 bytes thanks to Cows quack

\$\endgroup\$
  • \$\begingroup\$ You can remove the a is :a and ta to save bytes \$\endgroup\$ – Kritixi Lithos Apr 29 '17 at 17:48
  • \$\begingroup\$ @KritixiLithos Apparently that was a bug in GNU sed that was removed in 4.3. I'd probably drop those characters if this entry was close enough to the leader for it to have a chance of winning, but since it isn't, I'll just leave it in the more portable form so it doesn't stop working as more systems upgrade to 4.3. \$\endgroup\$ – Ray May 1 '17 at 20:34
  • 1
    \$\begingroup\$ Looking back at this, I'm sure you can drop the q from /./ and drop the braces there too. Try it online! This is because of how change works \$\endgroup\$ – Kritixi Lithos Jun 18 '18 at 12:02
  • \$\begingroup\$ @Cowsquack Thanks. Edited. \$\endgroup\$ – Ray Jun 18 '18 at 17:46
0
\$\begingroup\$

05AB1E, 9 bytes

žu2ôõ:g2Q

Input is given in quotes.

Try it online!

Explanation:

žu          # Push "()<>[]{}"
  2ô        # Split into pieces of size 2
    õ       # Push empty string
            # Implicit input
      :     # Infinite replacement
       g2Q  # Is length equal to 2?
            # Implicit print
\$\endgroup\$
0
\$\begingroup\$

Clojure, 153 bytes

Longer than even C and Brainfuck answers :o

(defn f[[s & r]](if s(let[[a b](split-at(.indexOf(reductions + 1(for[c r](get(zipmap[s({\(\)\[\]\{\}\<\>}s)][1 -1])c 0)))0)r)](and(not=()a)(f(butlast a))(f b))))1)

Doesn't use regex, instead uses the first character to determine what the closing tag is and finds the first index where that bracket is balanced (cumulative sum is zero). Then iteratively checks that what is within brackets and after brackets are valid.

Gotta see if there is a better approach...

\$\endgroup\$
0
\$\begingroup\$

Lua, 295 bytes

f = false g = string.gsub t=table s={}b=io.read()for c in b:gmatch('.')do if c:find("[%[<{%(]")then s[#s + 1] = g(g(g(g(c,"<",">"),"{","}"),"%[","]"),"%(",")")elseif c:find("[%]>}%)]")then if t.remove(s)~=c then print(f)return end else print(f)return end end if#s>0 then print(f)else print(1)end

Ungolfed Version

f = false
g = string.gsub
t=table
s={} --Define a stack of opening brackets
b=io.read() --get the input
for c in b:gmatch('.') do   --for every character
    if c:find("[%[<{%(]") then
        s[#s + 1] = g(g(g(g(c,"<",">"),"{","}"),"%[","]"),"%(",")") --if the current character is an opening bracket, push the closing bracket onto the stack
    elseif c:find("[%]>}%)]") then
        if t.remove(s)~=c then
            print(f) --if the character is a closing bracket, pop the closing bracket off the stack and test if they match, if not print false
            return
        end
    else 
        print(f) --if the character is not a bracket print false
        return
    end
end
if #s>0 then
    print(f) --if there are still brackets on the stack print false
else
    print(1) --print 1 there are no brackets on the stack
end

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Japt v2.0a0 -!, 16 bytes

e/\[]|<>|\(\)|{}

Try it

\$\endgroup\$
0
\$\begingroup\$

R, 298

function(.){s=strsplit;u=paste0;.=s(.,"")[[1]];p=s("><)(}{][","")[[1]];.[!.%in%p]="§";for(i in 1:4*2){.[.==p[i]]=sprintf("S('%s',{",p[i]);.[.==p[i-1]]=sprintf("},'%s');",p[i])};S=function(H,B,T)if(H!=T)stop();r=try(eval(parse(,,u(.,collapse=""))),1);if(inherits(r,"try-error"))FALSE else TRUE}

The approach here is to convert the sequence into R code, and then try to parse and evaluate it. If that gives an error, then return FALSE.

But there is a minor problem ... R's rules for brackets are different, so < and > are not brackets at all, and the other types have rules of their own. This is solved by a revolutionary approach -- a squeaking function, whose only function is to signal an error if its head and tail squeak in different ways.

For example, [] is transformed into S('[', {}, ']'), where S is defined as ...

S=function(H,B,T)if(H!=T)stop() 

Because the head squeak and tail squeak match, no error is thrown.

A few other examples (the left part is a sequence of brackets and right part is its transformation into valid R code that can be evaluated):

[}     -->  S('[', {}, '}')     # squeaks an error
[()]   -->  S('[', {S('(',{},'(')}, "[")
({[]}) -->  S('(',{S('{',{S('[',{},'[');},'{');},'(');

Some other sequences of brackets will result in parse errors:

[[)    -->   S('[',{S('[',{},'('); 

So the remaining part just catches the errors and returns FALSE if there are any, and TRUE if there are none.

The human-readble code:

 sqk <- function(.){
   s=strsplit;u=paste0
   .=s(.,"")[[1]]            # break the argument up into 1-character pieces
   p=s("><)(}{][","")[[1]]   # vector of brackets
   .[!.%in%p]="§"            # replace anything besides brackets by § (--> error)
   for(i in 1:4*2){     
     .[.==p[i]]=sprintf("S('%s',{",p[i])    # '<' -->   S('<',{     ... etc
     .[.==p[i-1]]=sprintf("},'%s');",p[i])  # '>' -->   },'<');     ... etc  
   }
   S=function(H,B,T)if(H!=T)stop()          # define the working horse
   r=try(eval(parse(,,u(.,collapse=""))),1) # evaluate the sequence
   if(inherits(r,"try-error"))FALSE else TRUE   # any errors?
   }

Applying it on sample cases:

truthy<-readLines(textConnection("()
[](){}<>
(((())))
({[<>]})
[{()<>()}[]]
[([]{})<{[()<()>]}()>{}]"))
falsy<-readLines(textConnection("(
}
(<2)>
(()()foobar)
[({}<>)>
(((()))"))
> sapply(truthy,sqk)
                      ()                 [](){}<>                 (((()))) 
                    TRUE                     TRUE                     TRUE 
                ({[<>]})             [{()<>()}[]] [([]{})<{[()<()>]}()>{}] 
                    TRUE                     TRUE                     TRUE 
> sapply(falsy,sqk)
           (            }        (<2)> (()()foobar)     [({}<>)>      (((())) 
       FALSE        FALSE        FALSE        FALSE        FALSE        FALSE 
\$\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.