15
\$\begingroup\$

Your mission, should you choose to accept it, is to add the minimum number of parentheses, braces, and brackets to make a given string (containing only parentheses, braces, and brackets) have correct brace matching. Ties of symbols added must be broken by having the maximum distance between paired braces. You must return only one correct answer that matches these two rules; Further ties, should they exist, may be broken any way you see fit.

Examples:

input      output
                          // Empty String is a legal input
[          []             // Boring example
[()]       [()]           // Do nothing if there's nothing to be done
({{        ({{}})         // NOT (){}{} (0 + 0 + 0). Maximum distance is 4 + 2 + 0, ({{}})
[([{])]}   {[([{}])]}     // NOT [([])]{[([])]} or similar

You may write a program or function, receives the input via STDIN as a string argument to your function, which returns the output as a string or prints it to STDOUT (or closest alternative). You may optionally include a single trailing newline in the output.

You may assume the input string consists only of the following 6 characters (or lack thereof): [](){} (You do not need to support <>)

This is , shortest program wins. Standard loopholes are banned, of course.

\$\endgroup\$
7
  • \$\begingroup\$ Did you mean to repeat the title directly underneath the actual title, or repeat the tag directly above the actual tags? Just asking in case you copy pasted from Sandbox and forgot to remove them. \$\endgroup\$
    – Rainbolt
    May 27, 2015 at 20:40
  • \$\begingroup\$ @Rainbolt The former no (sandbox), the latter yes \$\endgroup\$
    – durron597
    May 27, 2015 at 20:47
  • 1
    \$\begingroup\$ @AlexA. I can see how they're different in minor ways, but I think they're too similar to be considered separate questions. \$\endgroup\$ May 27, 2015 at 22:22
  • \$\begingroup\$ Fair enough. It's certainly not cut-and-dry, and I won't pursue getting it closed if others decide not to. \$\endgroup\$ May 27, 2015 at 22:29
  • \$\begingroup\$ I would consider it different enough. Voted to reopen. \$\endgroup\$
    – nderscore
    May 28, 2015 at 2:39

3 Answers 3

2
\$\begingroup\$

Python 3, 211 207 198 bytes

After some work on this variation of this question (matching the brackets given exactly 1 unclosed opening bracket, with no possible unopened closing brackets), I realized that my answer to that could be adapted to this problem (which was linked as a possible duplicate).

f=lambda s:s[::-1].translate(" ] [)(} {"*14)
def m(a):
 *u,b="",
 for x in a:
  if x in"([{":u+=x
  elif u and x!=f(y:=u.pop()):b+=f(y);*u,_=u
  b+=x
 return b+f("".join(u))
M=lambda a:f(m(f(m(a))))

Edit -4 bytes: inspired by some golfs on my answer on the other post by @ovs

Edit -9 bytes: We have tied the old python2 answer here!! I knew there had to be some way to golf the closing of any trailing unclosed brackets onto the return statement, and after trying a lot of nonsense involving map() I realized that if I just .join(u) with the empty string, I can reverse it with f() at the same time as flipping the brackets

Try it online!

Explanation and ungolfed code:

This answer takes my answer to the other problem, which loops through a string and adds a missing closing bracket to properly match an unclosed opening bracket, adapts it slightly to ensure it works for multiple unclosed brackets, and then applies it to the string twice, flipping the string in-between.

f=lambda s:s[::-1].translate(" ] [)(} {"*14) ## lambda that flips a string, and reverses all the brackets in it
def m(a): ## function that takes a string and matches every unclosed opening bracket (ignores unopened closing brackets)
    u=[] ## list holding all currently unclosed brackets
    b="" ## string that the result is build in
    for x in a: ## loop through the input
        if x in"([{": ## if its an opening bracket
            u+=[x] ## add it to the unclosed list
        elif u and x!=f(y:=u.pop()): ## if there are unclosed brackets and this bracket doesnt close the last opened one
            b+=f(y); ## add the necessary closing bracket
            u.pop() ## pop the extra opening bracket that x closes
        b+=x ## no matter what, add this character to the result
    return b+f("".join(u)) ## join the remaining unclosed brackets into a single string, flip it with f(), and add it to the result
M=lambda a:f( ## Flip the final string back to the correct order
         m(f( ## Flip the string and apply m again to match the unopened closing brackets
         m(a)))) ## Apply the above function to the result to match all unclosed opening brackets
\$\endgroup\$
1
\$\begingroup\$

Python 2 - 198

I was hoping to get some of the comprehensions down a bit more but don't have a lot of time right now to really test different ways of doing things.

s="()[]{}";f=s.find
def F(S):
 r=m=""
 for c in S:
    i=f(c)^1
    if i%2:m=c+m;r+=c
    else:
     for d in m:
        if d==s[i]:break
        r+=s[f(d)^1]
     else:r=s[i]+r+c
     m=m[1:]
 for c in m:r+=s[f(c)^1]
 return r

The OP did not include an example like {[([{}])]}{[ (with adjacent groups), but whether or not this functionality is required this outputs the correct {[([{}])]}{[]}

\$\endgroup\$
3
  • \$\begingroup\$ How is that 198 bytes? \$\endgroup\$
    – Adalynn
    Dec 1, 2016 at 21:35
  • \$\begingroup\$ @ZacharyT, tabs (\t) get formatted as 4 spaces on stack overflow but I am actually alternating tabs and spaces (you can do this for indentation levels in Python 2, not 3) so first level is [space] second is [tab] third is [tab][space] forth is [tab][tab]. Entering the code in with spaces gives me 227 from here mothereff.in/byte-counter, and I count 10 tabs so 227 - (3 * 10) = 197. Huh, I guess I actually over-counted by 1 way back when I posted this. \$\endgroup\$
    – KSab
    Dec 1, 2016 at 22:14
  • \$\begingroup\$ DANG! That's a really good trick. (Enter at end of line). You can combine the bottom for-loop and the return-statement to return r+[s[f(c)^1]for c in m]to save bytes. \$\endgroup\$
    – Adalynn
    Dec 1, 2016 at 22:23
1
\$\begingroup\$

Haskell, 513

The function h. Previous version did not give correct answers for "({{)[" and "({{)}}"

import Control.Monad

m '('=')'
m '['=']'
m '{'='}'
m ')'='('
m ']'='['
m '}'='{'

data B=B Char[B]|N[B]|Z B Char[B]
instance Eq B where(==)a b=q a==q b
instance Ord B where(<=)a b=q a<=q b

w(B o s)=o:(s>>=w)++[m o]
v(N k)=k>>=w
n(B _ k)=(sum$n<$>k)+1
q(N k)=sum$n<$>k

u(Z(Z g pc pk) c k)=Z g pc(pk++[B c k])
u(Z(N pk) c k)=N(pk++[B c k])
t(N k)=N k
t z=t$u z

f z c|elem c "([{"=[Z z c[]]
f z@(Z p o k) c|m c==o=[u z]|2>1=(u$Z(Z p o [])(m c)k):f(u z)c
f (N k)c=[Z(N[])(m c)k]

h s=v.minimum$t<$>foldM f(N [])s
\$\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.