Jesteś kierownikiem projektu. Pewnego dnia jeden z twoich programistów oszalał ( nie twoja wina ) i wziął wszystkie wyrażenia z bazy kodu i dodał do nich losowe nawiasy, zanim odszedł na miejscu, narzekając na twoją niekompetencję ( również nie twoją winę ). Byłoby to łatwe rozwiązanie, jednak z jakiegoś powodu nie używasz kontroli wersji ( całkowicie nie twoja wina ). I z jakiegoś powodu żaden inny programista nie chce przejrzeć każdego wyrażenia, aby naprawić niedopasowane nawiasy ( nawiasem mówiąc, to nie twoja wina ). Programiści w dzisiejszych czasach, myślicie sobie. Musisz to zrobić sam. Horror! Takie zadania miały być pod tobą ...

Wejście będzie pojedynczym wierszem, który będzie zawierał lewy nawias kwadratowy ( ( [ {) i prawy nawias kwadratowy ( ) ] }). Może także, ale nie zawsze, zawierać komentarze ( /* */) i literały łańcuchowe ( " "lub ' ') oraz różne liczby, litery lub symbole.

Będzie co najmniej jeden nawias (poza komentarzem lub dosłownym ciągiem znaków), który nie ma przeciwnej strony (poza komentarzem lub dosłownym ciągiem znaków). Na przykład błąd }bez {uprzedniego. Kolejny przykład: a, (który nie ma )później. Twój program zastąpi spacją minimalną liczbę nawiasów wymaganych do dopasowania nawiasów.

Przykłady:

(4 + (2 + 3))]==> (4 + (2 + 3)) (nawias kwadratowy na końcu)
][][[]]==> [][[]](nawias kwadratowy na początku)
("Hel(o!"))==> ("Hel(o!") (nawias na końcu)
( /* )]*/==> /* )]*/ (nawias na początku)
{()]==> () (nawias klamrowy i nawias kwadratowy)

• Dane wejściowe można pobierać z dowolnej dogodniejszej metody (STDIN, argument wiersza poleceń, odczyt z pliku itp.)
• Jeśli istnieje więcej niż jeden sposób rozwiązania problemu niedopasowania przy takiej samej liczbie usunięć, jest to dopuszczalne.
• Dopuszczalne będą jedynie niedopasowania w nawiasach. Literały ciągów i komentarze zawsze będą poprawnie tworzone.
• Tytuł pochodzi z tego wątku SO
• Nigdy nie będzie żadnych cytatów w komentarzach, cytatów w cytatach, komentarzy w komentarzach ani komentarzy w cytatach.

To jest kod golfowy, więc minimalna liczba bajtów wygrywa. Zadawaj pytania w komentarzach, jeśli specyfikacja nie jest jasna.

Ruby, 223 znaków

Ten okazał się trochę długi.

u,b,i=[],[[],[],[]],-1
s=gets.gsub(/(\/\*|"|').*?(\*\/|"|')|~/){|m|u+=[m];?~}
s.chars{|c|i+=1
(t='{[('.index(c))?b[t].push(i):((t='}])'.index(c))&&(b[t].pop||s[i]=' '))}
b.flatten.map{|l|s[l]=' '}
puts s.gsub(/~/){u.shift}

W pierwszej kolejności usuwa ciągi i komentarze, aby nie były liczone (i odkładały je później).

Następnie przechodzi przez ciąg znaków po znaku. Gdy znajdzie nawias otwierający, zapisuje swoją pozycję. Gdy znajdzie nawias zamykający, wyskakuje z odpowiedniej tablicy pamięci otwartego nawiasu.

Jeśli popzwraca nil(tzn. Nie było wystarczającej liczby nawiasów otwierających), usuwa nawias zamykający. Po wykonaniu tej czynności usuwa pozostałe dodatkowe otwierające nawiasy klamrowe (tj. Nie było wystarczającej liczby nawiasów zamykających).

Pod koniec programu odkłada wszystkie ciągi i komentarze z powrotem i wysyła je.

Nie golfowany:

in_str = gets

# grab strings and comments before doing the replacements
i, unparsed = 0, []
in_str.gsub!(/(\/\*|"|').*?(\*\/|"|')|\d/){|match| unparsed.push match; i += 1 }

# replaces with spaces the braces in cases where braces in places cause stasis
brace_locations = [[], [], []]
in_str.each_char.with_index do |chr, idx|
    if brace_type = '{[('.index(chr)
        brace_locations[brace_type].push idx
    elsif brace_type = '}])'.index(chr)
        if brace_locations[brace_type].length == 0
            in_str[idx] = ' '
        else
            brace_locations[brace_type].pop
        end
    end
end
brace_locations.flatten.each{|brace_location| in_str[brace_location] = ' ' }

# put the strings and comments back and print
in_str.gsub!(/\d+/){|num| unparsed[num.to_i - 1] }
puts in_str

Python 3, 410 322 317

import re;a='([{';z=')]}';q=[re.findall('".*?"|/\*.*?\*/|.',input())]
while q:
 t=q.pop(0);s=[];i=0
 for x in t:
  if x in a:s+=[x]
  try:x in z and 1/(a[z.find(x)]==s.pop())
  except:s=0;break
 if[]==s:print(''.join(t));break
 while 1:
  try:
   while t[i]not in a+z:i+=1
  except:break
  u=t[:];u[i]=' ';q+=[u];i+=1

Próbuje każdego możliwego zestawu usunięć, zaczynając od mniejszych, aż znajdzie taki, w którym nawiasy klamrowe są zrównoważone. (Rozumiem przez to w pełni poprawnie wyważone: {{(})produkuje ( ), a nie {(}).)

Pierwsza wersja używała generatora rekurencyjnego, co było naprawdę fajne, ale także bardzo długie. Ta wersja wykonuje proste pierwsze wyszukiwanie przy użyciu kolejki. (Tak, to algorytm czynnikowy. Jaki jest problem?: ^ D)

C - 406

Próba w C bez użycia wyrażeń regularnych.

#define A if((d==125||d==93||d==41)
char*s;t[256];f(i,m,n,p){while(s[i]!=0){int c=s[i],k=s[i+1],v=1,d;if((c==42&&k==47)||(c==m&&i>n))return i;if(!p||p==2){if((c==39||c==34)||(c==47&&k==42)){i=f(i,c*(c!=47),i,p+1);
c=c==47?42:c;}d=c+1+1*(c>50);A){v=f(i+1,d,i,2);if(!p&&v)t[d]++;if(p==2&&v)i=v;}}d=c;A&&!p){v=!!t[c];t[c]-=v;}if(p<2)putchar(c*!!v+32*!v);i++;}return 0;}main(int c,char*v[]){s=v[1];f(0,0,0,0);}

Aby skompilować i uruchomić (na komputerze z systemem Linux):
gcc -o brackets.c
./brackets „[(])”

W niezdefiniowanych przypadkach, takich jak [(]), zwraca ostatnią prawidłową parę nawiasów ()

Python 3, 320

import re
O=dict(zip('([{',')]}'))
def o(s,r,m=0,t=[]):m+=re.match(r'([^][)({}/"]|/(?!\*)|/\*.*?\*/|".*?")*',s[m:]).end();return r and o(s[:m]+' '+s[m+1:],r-1,m+1,t)or(o(s,r,m+1,t+[O[s[m]]])if s[m]in O else[s[m]]==t[-1:]and o(s,r,m+1,t[:-1]))if s[m:]else not t and s
s=input();i=0;a=0
while not a:a=o(s,i);i+=1
print(a)

Podobnie jak rozwiązanie DLosc, sprawdza to każde możliwe usunięcie, ale wykorzystuje rekurencyjną strategię eksploracji i cofania, która jest znacznie szybsza. Wiem, że prędkość nie jest kryterium w golfie kodu, a wyczerpujące wyszukiwanie jest w każdym przypadku wykładnicze, ale to może obsłużyć dane wejściowe jak ({({({({({({({({(}}}}}}}}za kilka sekund.