Are the brackets fully matched?

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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|();

Answer 4

K (ngn/k), 32 29 bytes

-3 bytes thanks to @coltim

~#{x{""/y\x}/4 2#"()[]{}<>"}/

Try it online!

{ } a function with argument x

4 2#"()[]{}<>" split to 4 strings of length 2: ("()";"[]";"{}";"<>")

x{..}/ starting with x, go through the list of pairs and apply the function in { } with the previous result as x and the current pair as y

{""/y\x} split x on occurrences of y and join with "" - effectively remove all occurrences of y

# length

~ is 0? (logical not)

Answer 5

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!

Shorter, but sadly much more boring and uninventive than the previous R answer, which I feel more-deserves appreciation... please upvote it instead!

Answer 6

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

Answer 7

Stax, ¹⁹ 12 bytes

æöT┴S○♂èα ôG

Run and debug it

Link is to unpacked code.

-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

Answer 8

JavaScript (Node.js), 97 bytes

Solution without regex, so it can't really compete in terms of shortness.

s=>[...s].every(c=>(i="
([{<)]}>".indexOf(c))<0?0:i<5?a+=i:a%10-i+4==0?a=""+(a/10|0):0,a="")&&a<1

Try it online!

---

This solution uses a string as if it were a stack.
We push by concatenating 1, 2, 3 or 4 for ([{< respectively, we check the last value by using modulo 10, and pop it by dividing by 10 if there is a match between the last opening bracket seen and the current closing bracket (an opening bracket is kept forever in the stack if it's not matched).

If there is any closing bracket that doesn't match or if there is any unauthorized character at all, the entire result will be falsed.

The unprintable SOH character is used as padding to never have a 0 in the stack (OP guaranteed that no unprintable character would be in the input). It's necessary to avoid confusing the empty stack "" with a stack potentially full of zeroes, in the condition below.

The a<1 is to check that all the necessary closing brackets have been encountered (which is equivalent to checking if the stack has been successfully emptied at the end).

Answer 9

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

Answer 10

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!

Answer 11

Japt v2.0a0 -!, 16 bytes

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

Try it

Answer 12

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!

Answer 13

Haskell, 138 Bytes

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

Answer 14

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.

Answer 15

PHP5.4 (84 chars)

Given $argv[1] as a command line argument, it doesn't take a regex to print 0 or 1 :

for($s=$argv[1];"$s"!=$s=str_replace(['()','[]','{}','<>'],'',$s););echo$s===''?1:0;

The same process is 87 chars long using a function :

function f($s){for(;"$s"!=$s=str_replace(['()','[]','{}','<>'],'',$s););return$s==='';}

Try it Online - Usage :

var_dump(f('[([]{})<{[()<()>]}()>{}]')); // bool(true)
var_dump(f('0(()())')); // bool(false)

Info : Only the array declaration break the PHP4 compatibility.

Answer 16

Lexurgy, 38 bytes

While the input changed last iteration, replace pairs of adjacent brackets with an empty string.

a propagate:
{\(\),\[\],\{\},\<\>}=>*

Answer 17

Haskell, 59 bytes

null.foldr(%)""
c%(a:b)|elem(c,a)$zip"([{<"")]}>"=b
c%s=c:s

Try it online!

Answer 18

Rust, 95 bytes

Straightforward recursive solution based on the replacement approach.

fn f(s:String)->bool{s==""||"(),<>,{},[]".split(",").any(|c|s.contains(c)&&f(s.replace(c,"")))}

Try it online!