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\$
  • \$\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 '15 at 20:40
  • \$\begingroup\$ @Rainbolt The former no (sandbox), the latter yes \$\endgroup\$ – durron597 May 27 '15 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\$ – NinjaBearMonkey May 27 '15 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\$ – NinjaBearMonkey May 27 '15 at 22:29
  • \$\begingroup\$ I would consider it different enough. Voted to reopen. \$\endgroup\$ – nderscore May 28 '15 at 2:39
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\$
  • \$\begingroup\$ How is that 198 bytes? \$\endgroup\$ – Zacharý Dec 1 '16 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 '16 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\$ – Zacharý Dec 1 '16 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.