# Are the brackets fully matched?

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.

• Related. Apr 5 '16 at 6:42
• 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. Apr 5 '16 at 6:55
• @EJP No, it is not. Each pair of brackets has the correct opening and closing bracket and in the right order. Apr 5 '16 at 13:17
• I will upvote the first solution in Brackets
– leo
Apr 5 '16 at 14:27
• When I saw the title I thought knew exactly who would be posting it, because DJMcMayhem invented Brain-flak. But I was surprised that this challenge was posted by James instead ...
– user92069
Feb 23 '20 at 7:59

# Husk, 23 18 bytes

Edit -5 bytes thanks to Leo

¬ωḞσøC2"()[]{}<>


Try it online!

How?

¬ωλ◄Lmλσ⁰ø²)C2"()[]{}<>
¬                     # logical NOT of (note NOT of a non-empty string is 0):
ωλ                   # result of repeating the following operation
# until it reaches a periodic (in this case fixed) resut:
Ḟ                 # fold over
C2           # each pair x from
"()[]{}<>  # the string "()[]{}<>",
# with starting value equal to the (implicit) input,
# and using the function:
σø             # substitute x to null in the last value

• Very nice! You can save a bunch of bytes by folding over the list rather than mapping and then taking the shortest result, and by getting rid of the lambdas with some clever flips tio.run/##yygtzv6f@6ip8f@hNec7Ex7umJdwvvnwDmcjJQ3N6NjqWhu7////…
– Leo
Jan 25 at 2:45
• @Leo - that's fantastic! Thanks! The flips are definitely clever (subtext: I'm still scratching my head to really understand them...). Jan 25 at 23:05

# Stax, 19 12 bytes

æöT┴S○♂èα ôG


Run and debug it

-7 using a brackets builtin.

## Explanation

c%{Vb2/{z:rF}*!
c%              get the input's length
{         }*  execute this block that many times:
Vb           take the brackets
2/         groups of 2
{   F    for each:
z:r     replace the brackets with nothing
! logical not


## 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...

# 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
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!

# Japt v2.0a0 -!, 16 bytes

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


Try it

# Pascal (FPC), 137 126 bytes

var s,t:string;i:word;begin read(s);repeat t:=s;for i:=1to 4do Delete(s,pos('([{<'[i]+')]}>'[i],s),2)until s=t;write(s='')end.


Try it online!

## Unix TMG, 83 bytes

Another compiler-compiler solution (in addition to Yacc).

p:s parse((any(!<<>>)|={<1>}));s:b s/d;d:;b:<[>x<]>|<{>x<}>|<(>x<)>|<<>x<>>;x:s|();


Unlike Yacc, it works by recursive-descent parsing. It outputs "1" on success, nothing – otherwise.

Expanded:

p: s parse((any(!<<>>)|={<1>}));
s: b s/d;d:;
b: <[>x<]>|<{>x<}>|<(>x<)>|<<>x<>>;
x: s|();


f x=let g z x=case x of{[]->z;a:b->if a==z!!0then g(tail z)b else g(case a of{'('->')';'['->']';'{'->'}';'<'->'>';_->' '}:z)b}in" "==g" "x

de-golfed:

f x=                                                                      --define a function f
let g z x=case x of{                                                    --define a function which takes two parameters: z (the remaining input) x (the characters that need to be matched)
[]->z;                                                                --handle end of input
a:b->if a==z!!0                                                       --if the input matches the characters that need to be matched
then g (tail z) b                                                   --calls itself for the remaining input
else g (case a of{'('->')';'['->']';'{'->'}';'<'->'>';_->' '} : z) b--otherwise adds the character to the list of ones that need to be matched
}
in g " " x == " "                                                       --runs the matching function


# R, 104 bytes

f=function(x,y=x)if(nchar(x),{for(e in c("{}","[]","()","<>"))y=gsub(e,"",y,f=T)
if(y==x,F,f(y))},T)


Try it online!

# Vyxal, 15 bytes

λkḂ2ẇk<J(no);Ẋ¬


Try it Online!

λ           ;Ẋ  # While result changes
(  )    # For each of
kḂ2ẇk<J        # Pairs of brackets
no     # Remove it
¬ # If something remains, it's unbalanced.