Fix the Braces, etc

Question

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 code-golf, shortest program wins. Standard loopholes are banned, of course.

Answer 1

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

Answer 2

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 {[([{}])]}{[]}