57
\$\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\$
9
  • 1
    \$\begingroup\$ Related. \$\endgroup\$ Apr 5 '16 at 6:42
  • 8
    \$\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\$ Apr 5 '16 at 6:55
  • 3
    \$\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
  • 7
    \$\begingroup\$ I will upvote the first solution in Brackets \$\endgroup\$
    – leo
    Apr 5 '16 at 14:27
  • 1
    \$\begingroup\$ 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 ... \$\endgroup\$
    – user92069
    Feb 23 '20 at 7:59

40 Answers 40

1
2
1
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ 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////… \$\endgroup\$
    – Leo
    Jan 25 at 2:45
  • \$\begingroup\$ @Leo - that's fantastic! Thanks! The flips are definitely clever (subtext: I'm still scratching my head to really understand them...). \$\endgroup\$ Jan 25 at 23:05
1
\$\begingroup\$

Stax, 19 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
\$\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\$

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!

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

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|();
\$\endgroup\$
0
\$\begingroup\$

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

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!

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

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

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.