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

0
\$\begingroup\$

K (ngn/k), 32 bytes

~#{x@&~||':|4=9-':"([{<)]}>"?x}/

Try it online!

{ } a function with argument x

"([{<)]}>"?x find the indices of the elements of x in the given string, i.e. replace "(" in x with 0, "[" with 1, "{" with 2, etc

9-': differences between each element and its prior element, use 9 as a value before the first

4= boolean (0 1) mask of where the 4s occur

| reverse

|': boolean "or" of each element and its prior

| reverse again

~ not

& where are the 1s in the boolean mask? return a list of indices

x@ index x with those indices

{ }/ keep applying the function until convergence

~# not (~) of the count (#) - is the final result empty?

\$\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\$

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.