Napisz program, który zastępuje spacjami nawiasy klamrowe w przypadkach, gdy nawiasy klamrowe w miejscach powodują zastój

17

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.

Absynt
źródło
Ups, nasze zmiany kolidowały tam. : P Wszystko powinno być teraz naprawione.
Klamka
Nawiasem mówiąc, dzięki za to. Nie wiem jak zatrzymać SE od wycierania przestrzenie.
absynt
Czy mamy do czynienia z ucieczką rzeczy w literałach łańcuchowych (np. ("foo (\") bar"))?
Klamka
1
Argumentowałbym, że poprawne wyjście {{(})powinno być { } równoważne, ponieważ scenariusz otwierający sugeruje, że kod działał od samego początku i {(})liczy się jako niedopasowane nawiasy w każdym języku programowania, który znam (tj. „Powoduje zastój” ??). Ale już napisałem odpowiedź, więc jestem stronniczy.
DLosc
3
Widzę. Chyba nie jestem wystarczająco niekompetentny. ;)
DLosc

Odpowiedzi:

6

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
Klamka
źródło
To naprawdę imponujące. Jedno pytanie: czy nadal będzie działać w przypadku takiego wejścia (("string"/*comment*/)"string"? Jeśli poprawnie czytam (wersję bez golfa), zastępujesz ciągi i komentarze ich indeksem w unparsedtablicy, co prowadziłoby do podstawienia, ((12)3a następnie szukania nieistniejącego indeksu 12(lub 11). Widzę, że po prostu shiftgra w golfa , ale czy nadal nie może mieć podobnego problemu?
DLosc
4

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)

DLosc
źródło
Podoba mi się ten, ponieważ faktycznie znajduje najmniejsze usunięcie i tworzy poprawnie zagnieżdżone wyrażenia, ale ostatni komentarz @vonilya sugeruje, że prawidłowe zagnieżdżanie nie jest ważne. Jest jednak bardzo powolny, jeśli trzeba usunąć wiele nawiasów klamrowych.
rici
2

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 ()

Markuz
źródło
2

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.

rici
źródło
Dobrze zagrane, dobrze zagrane. Udało mi się zejść do 317, ale myślę, że powinieneś być w stanie przejść to dość łatwo. (Tymczasem mój program wciąż rezygnuje z twojego przykładowego wejścia ...)
DLosc
@DLosc: Nie wstrzymuj oddechu :). Wykonanie wersji tego wzoru z 6 otwartymi parenami zajęło mojej maszynie 58 minut. Aby rozwiązać zastój, zanim wszechświat osiągnie śmierć z powodu upałów, musisz powtórzyć kolejkę; w przeciwnym razie powstanie O(n!!)rozwiązanie, a nie O(n!). (Mój golf jest O(n*2^n)zamiast O(2^n), ponieważ ofaktycznie produkuje wszystkie wzory aż do rusunięcia, zamiast dokładnie rusuwania. Łatwy do naprawy, ale kosztowałby kilka znaków.)
rici