The Missing Match

Question

You are given a string of unknown length that contains a varied amount of (, {, [ and their respective closing parentheses (in this context all referred to as brackets).

With one exception, all the brackets are all balanced, meaning an opening one has a corresponding closing one somewhere afterwards in the string.
The brackets may not be "interpolated" with each other, i.e. opening bracket b which is inside opening bracket a must close before bracket a closes, so ([)], {[(]}), and ({[(])}())[()] are invalid, but ([]), {[()]}, and ({[()]})()[()] are valid.

Challenge

The task is, inside the string there is a single unbalanced bracket, i.e. an opening bracket that does not have a closing one. You must insert the closing bracket where it is the farthest distance apart from the opening bracket, but not interpolated with other brackets, then return the modified (or new) string.

Test cases

^ added to point out where a bracket was added.

"("                        --> "()"
                                 ^
"[(]"                      --> "[()]"
                                  ^
"{[({}()([[[{}]]])]{[]}}"  --> "{[({}()([[[{}]]]))]{[]}}"
                                                 ^
"[[[]]"                    --> "[[[]]]"
                                     ^
"{[[]([(()){[[{}]()]})]}"  --> "{[[]([(()){[[{}]()]}])]}"
                                                    ^

Scoring

This is code-golf, so shortest code wins.

Difference from "possible dupes":

1. This one only wants to see if the brackets are matched; nothing else
2. Quite similar, but in that question is the possibility that one must add multiple braces, which I would approach quite differently in answering

Answer 1

Python 3, 185 167 154 bytes

This is probably more golfable, but I figured I'd try a more logical approach than the brute force attempts of the other answers:

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

Edit -18 bytes: saved some space with a for loop, and found a better solution to adding a potential missing closing bracket to the end of the string than the if I was using. (Bonus: this code can be made to work for an arbitrary number of unclosed brackets, at a cost of only +8 bytes, by changing b+=f(str(*u)) to while u:b+=f(u.pop())

Edit -13 bytes: all thanks to some clever golfs by @ovs

Try it online!

Ungolfed code + Explanation

Instead of brute force checking each combination, this program loops through the string, and wherever it finds a closing bracket that doesn't match the last unclosed opening bracket, it adds the missing closing bracket.

def M(a):
    u=[] ## List being used as a stack holding the unmatched brackets
    b="" ## Result string that gets built up
    f=lambda s:s.translate(")] } "*25) ## Lambda that swaps each opening bracket for its closing version
    for x in a: ## loop through the characters in the input
        if x in "([{": ## "pop" the first char to x, check if its an opening bracket
            u.append(x) ## if so, just push it onto the list of unmatched brackets
        elif x!=f(y:=u.pop()): ## if its a closing bracket, check if it matches the most recently opened bracket
            b+=f(y) ## if it doesn't, add the bracket that would close that one
            u.pop() ## and then pop the bracket x actually closes
        b+=x ## stick this loops x onto the output
        a=a[1:] ## because you cant .pop() a str in python, we dont actually remove the first char until here
    b+=f(str(*u)) ## if theres anything left unclosed, flip it and stick it on the end
    return b

Answer 2

x86-64 machine code, 26 24 bytes

AA 04 01 0D 01 C3 31 C0 50 AC A8 0B 7B F2 59 88 0F AE 75 FA E3 EF EB F1

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes in RDI an address at which to place the result, as a null-terminated byte string; and the address of the input, as a null-terminated byte string, in RSI. The starting point is after the first 6 bytes.

-2 with some overlapping of instructions.

Note the binary representations of the brackets' ASCII codes:

( 00101000
) 00101001
[ 01011011
] 01011101
{ 01111011
} 01111101

In assembly:

o:  stosb       # (For left brackets) Add AL to the output string, advancing the pointer.
    add al, 1   # Add 1 to AL.
    .byte 0x0D, 0x01    # These two bytes combine with the next two instructions
                        #  to produce 'or eax, 0xC031C301'.
                        # The effect on AL (which is the low byte of EAX) is
                        #  to set its low bit to 1.
                        # This produces the corresponding right bracket.
e:  ret     # Return.   
f:  xor eax, eax            # (Start here) Set RAX to 0.
    push rax        # Push RAX onto the stack.
s:  lodsb           # Load a byte from the input string into AL, advancing the pointer.
    test al, 0x0B   # Set flags from its bitwise AND with binary 1011.
    jpo o           # Jump if that has an odd number of 1 bits -- true for left brackets.
c:  pop rcx         # (For right brackets and 0) Pop from the stack into RCX.
                    # The low byte is the expected character for balanced brackets.
    mov [rdi], cl   # Add that byte to the output string.
    scasb           # Compare that byte with AL, advancing the pointer.
    jne c           # Jump back if they are not equal, to continue popping.
    jrcxz e         # Jump, to return, if RCX is 0.
    jmp s           # Jump back to process the next byte.

Answer 3

Python 3, 167 bytes

Golfed Code

def f(s):
 S="";B="a"
 for c in s+B:
  if c in"({[":S+=c;B+=c
  elif abs(ord(c)-(b:=ord(B[-1])))>2:B=B[:-2];S+=chr(b+(1,2)[b>40])+c
  else:B=B[:-1];S+=c
 return S[:-1]

Try it online! Note that TIO has an old version of Python which doesn't allow assignment expressions, so the linked code is slightly longer than the real code.

Explanation

Similar to the other python answer in its basic approach - instead of brute forcing, it loops through the string, adding in the missing bracket when it finds a closing bracket that does not match the last unclosed opening bracket. However, the code is quite different.

• def f(s): Defines a function that accepts a parameter s, which will be the input string.

• S="";B="a": Creates two variables S and B. S is the new string with the extra bracket inserted, which gets added to in the for loop. B is a string to store unclosed opening brackets.

  An extra character gets added to B (I chose "a" but it could be anything) because an extra run of the loop must be done to check if there is an unclosed bracket at the end of the string, and this would cause an error if B were empty.

• for c in s+B: Loops through the characters in the input string.

  An extra character is added to the end of the string so that an extra run of the loop is done at the end. This is to check if there is still an unclosed bracket at the end of the string. Since B is currently equal to a string with one character, s+B can be used instead of e.g. s+"a", saving two bytes.

• if c in"({[":S+=c;B+=c: If the current character is an opening bracket, adds it to both S (the new string), and B (the string of unclosed opening brackets).

• elif abs(ord(c)-(b:=ord(B[-1])))>2:B=B[:-2];S+=chr(b+(1,2)[b>40])+c: Only gets run if the current character is not an opening bracket (in which case it is of course a closing bracket).

  abs(ord(c)-(b:=ord(B[-1]))>2) is True if the closing bracket does not correspond to the last unclosed opening bracket. This is because the ASCII codes of closing brackets are always either 1 or 2 larger than those of their corresponding opening brackets (ord("(")==40, ord(")")==41, ord("[")==91, ord("]")==93, ord("{")==123, ord("}")==125).

  The b:= also assigns the ASCII code of the last unclosed opening bracket to a variable b, used later in the line to determine which closing bracket should be added. This is the bit TIO complains about, because it was only added in Python 3.8.

  B=B[:-2] removes the last two characters of B (the list of unclosed opening brackets).

  S+=chr(b+(1,2)[b>40])+c adds the missing closing bracket, and then the current character, to S (the new string). This once again uses the ASCII codes of the brackets.

• else:B=B[:-1];S+=c: Only runs if the character is a closing bracket, and it matches the last unclosed opening bracket. B=B[:-1] removes the last character from the B; S+=c adds the character to the new string.

• return S[:-1]: Returns the new string. Due to the extra run of the loop, it will have an extra character at the end. The [:-1] removes this character.

Answer 4

J, 80 bytes

[:;@({~a:i:~<@(rplc&(,_2;&''\'()[]{}')^:_)@;"1)[:,/')}]';&.(1&|.)"0 1/<\,.<@}.\.

Try it online!

Simple approach:

• Construct every possible solution:
  • Insert each of ), ], and } into every possible position.
  • This turns out to be verbose because J lacks an "insert at" verb.
• For each candidate solution, repeatedly reduce it by replacing (), [], and {} with the empty string.
  • Valid solutions will have reduced to the empty string.
• Of the valid solutions, pick the one whose insertion point was farthest to the right.

Answer 5

Jelly,  33  22 bytes

;⁶ȧ®ṪOịʋ;ɼȧ$e?€“] } )”

A monadic Link that accepts a list of characters (from (){}[]) and yields a list of characters (with one of )}} inserted/appended),

Try it online!

How?

Forms a string by keeping open brackets and closing the last, as yet unclosed, open bracket when a close bracket (or the end of the string) is encountered.

;⁶ȧ®ṪOịʋ;ɼȧ$e?€“] } )” - Link: list of (){}[] characters, A:
;⁶                     - concatenate a space
                          - will be identified as a closing bracket later
               “] } )” - set the right argument to "] } )"
              €        - for each in the augmented A:
             ?         -   if...
            e          -   ...condition: exists in "] } )"?
       ʋ               -   ...then: last four links as a dyad:
  ȧ®                   -     logical AND with the register
    Ṫ                  -     tail (last, as yet unclosed opening bracket)
     O                 -     ordinal
      ị                -     index into "] } )" (1-indexed & modular)
                              - gives the matching closing bracket
           $           -   ...else: last two links as a monad:
         ɼ             -         apply to register (initially 0)
        ;              -         concatenate
          ȧ            -         logical AND (to get back the single bracket)

Answer 6

Retina 0.8.2, 101 bytes

+T`()[]{}`d`\(\d*\)|\[\d*]|{\d*}
\(\d*(?=]|}|$)
$&)
\[\d*(?=\)|}|$)
$&]
{\d*(?=\)|]|$)
$&}
T`d`()[]{}

Try it online! Link includes test cases. Explanation:

+T`()[]{}`d`\(\d*\)|\[\d*]|{\d*}

Repeatedly substitute matched brackets with digits, where matched brackets are either (), [], {}, or any of the three pairs separated by an arbitrary number of digits, e.g. [()] would be substituted twice, first to [01], then to 2013.

\(\d*(?=]|}|$)
$&)
\[\d*(?=\)|}|$)
$&]
{\d*(?=\)|]|$)
$&}

Find an unmatched bracket and insert its match.

T`d`()[]{}

Substitute matched brackets back from their digits.