Tulis sebuah program yang menggantikan dengan kurung kurawal jika kurung kurawal di tempat menyebabkan stasis

17

Anda adalah manajer proyek. Suatu hari, salah satu programmer Anda menjadi gila ( bukan kesalahan Anda ) dan mengambil semua ekspresi dalam basis kode dan menambahkan tanda kurung acak kepada mereka, sebelum berhenti di tempat, mengomel tentang ketidakmampuan Anda ( juga bukan kesalahan Anda ). Ini akan menjadi perbaikan yang mudah, namun, untuk beberapa alasan Anda tidak menggunakan kontrol revisi ( sama sekali bukan kesalahan Anda ). Dan untuk beberapa alasan, tidak ada programmer lain yang ingin melalui setiap ekspresi untuk memperbaiki tanda kurung yang tidak cocok ( omong-omong, itu bukan salah Anda ). Pemrogram hari ini, Anda berpikir untuk diri sendiri. Anda harus melakukannya sendiri. Menyeramkan! Tugas semacam itu seharusnya ada di bawahmu ...

Input akan berupa satu baris, yang akan berisi sejumlah tanda kurung kiri ( ( [ {) dan tanda kurung kanan ( ) ] }). Ini juga dapat, tetapi tidak selalu, berisi komentar ( /* */) dan string literal ( " "atau ' ') dan berbagai angka, huruf, atau simbol.

Akan ada setidaknya satu braket (di luar komentar atau string literal) yang tidak memiliki lawan yang berlawanan (di luar komentar atau string literal). Misalnya, bandel }tanpa pendahuluan {. Contoh lain: (yang tidak memiliki )setelahnya. Program Anda akan menggantikan dengan kurung jumlah kurung minimum yang diperlukan untuk membuat kurung cocok.

Contoh:

(4 + (2 + 3))]==> (4 + (2 + 3)) (braket persegi di akhir)
][][[]]==> [][[]](braket persegi di awal)
("Hel(o!"))==> ("Hel(o!") (tanda kurung di akhir)
( /* )]*/==> /* )]*/ (tanda kurung di awal)
{()]==> () (braket keriting dan braket persegi)

  • Input dapat diambil dari cara mana yang paling nyaman (STDIN, argumen baris perintah, membaca dari file, dll.)
  • Jika ada lebih dari satu cara untuk menyelesaikan ketidakcocokan dengan jumlah pemindahan yang sama, keduanya dapat diterima.
  • Hanya akan ada ketidakcocokan dalam tanda kurung. Literal string dan komentar akan selalu terbentuk dengan benar.
  • Judul berasal dari utas SO ini
  • Tidak akan pernah ada kutipan dalam komentar, kutipan dalam kutipan, komentar dalam komentar, atau komentar dalam kutipan.

Ini adalah kode golf, jadi jumlah minimum byte menang. Ajukan pertanyaan dalam komentar jika spesifikasinya tidak jelas.

Absinth
sumber
Ups, hasil edit kami bertabrakan di sana. : P Semuanya harus diperbaiki sekarang.
Gagang Pintu
@Doorknob Terima kasih untuk itu, omong-omong. Tidak tahu bagaimana untuk menghentikan SE dari menyeka ruang.
absinthe
Apakah kita harus menangani pelarian barang dalam string literal (misalnya ("foo (\") bar"))?
Gagang Pintu
1
Saya berpendapat bahwa output yang benar {{(})harus { } atau setara, karena skenario pembukaan menyiratkan bahwa kode bekerja untuk memulai, dan {(})dianggap sebagai kurung yang tidak cocok dalam setiap bahasa pemrograman yang saya tahu (yaitu "menyebabkan stasis" ??). Tapi, kemudian, saya sudah menulis jawaban, jadi saya bias.
DLosc
3
Saya melihat. Kira saya tidak cukup kompeten. ;)
DLosc

Jawaban:

6

Ruby, 223 karakter

Yang ini ternyata agak lama.

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}

Apa yang dilakukan adalah mengeluarkan string dan komentar terlebih dahulu, sehingga mereka tidak dihitung (dan memasukkannya kembali nanti).

Kemudian, ia melewati karakter string dengan karakter. Ketika menemukan penyangga pembuka, ia menyimpan posisinya. Ketika menemukan kurung kurawal, itu muncul dari masing-masing susunan kurung kurawal terbuka.

Jika popkembali nil(yaitu tidak ada kawat gigi pembuka yang cukup), itu akan menghapus kurung kurawal. Setelah semua ini selesai, itu menghapus sisa kawat pembukaan tambahan (yaitu tidak ada kawat penutup cukup).

Pada akhir program, ini mengembalikan semua string dan komentar serta mengeluarkannya.

Tidak Disatukan:

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
Gagang pintu
sumber
Ini sangat mengesankan. Namun satu pertanyaan: apakah masih akan berfungsi untuk input seperti (("string"/*comment*/)"string"? Jika saya membaca (versi yang tidak di-serigala) dengan benar, Anda mengganti string dan komentar dengan indeks mereka dalam unparsedarray, yang akan mengarah ke substitusi seperti ((12)3dan kemudian mencari indeks yang tidak ada 12(atau 11). Saya melihat versi golf hanya menggunakan shift, tetapi mungkinkah itu masih memiliki masalah yang sama?
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

Mencoba setiap set penghapusan yang mungkin, mulai dari yang lebih kecil, sampai menemukan satu tempat kawat gigi seimbang. (Maksud saya seimbang sepenuhnya benar: {{(})menghasilkan ( ), tidak {(}).)

Versi pertama menggunakan fungsi generator rekursif, yang sangat keren tetapi juga sangat panjang. Versi ini melakukan pencarian pertama yang sederhana menggunakan antrian. (Ya, ini adalah algoritma waktu faktorial. Apa masalahnya?: ^ D)

DLosc
sumber
Saya suka yang ini karena ia benar-benar menemukan paling sedikit penghapusan dan menghasilkan ekspresi bersarang dengan benar, tetapi komentar terakhir oleh @vonilya menunjukkan bahwa bersarang yang benar tidak penting. Namun, itu sangat lambat jika banyak kawat gigi harus dilepas.
rici
2

C - 406

Percobaan dalam C tanpa menggunakan ekspresi reguler.

#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);}

Untuk mengkompilasi dan menjalankan (pada mesin linux):
gcc -o brackets.c
./brackets "[(])"

Dalam kasus yang tidak ditentukan seperti [(]) ia mengembalikan pasangan braket yang valid terakhir ()

Markuz
sumber
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)

Seperti solusi DLosc, ini menyelidiki setiap penghapusan yang mungkin, tetapi menggunakan eksplorasi rekursif dan strategi mundur yang jauh lebih cepat. Saya tahu bahwa kecepatan bukanlah kriteria dalam kode golf, dan pencarian lengkap dalam hal apa pun adalah eksponensial, tetapi yang ini dapat menangani input seperti ({({({({({({({({(}}}}}}}}dalam beberapa detik.

Rici
sumber
Dimainkan dengan baik, dimainkan dengan baik. Saya memang berhasil turun ke 317, tetapi saya pikir Anda harus bisa lulus dengan cukup mudah. (Sementara itu, program saya masih berputar di input contoh Anda ...)
DLosc
@Dosc: Jangan menahan nafasmu :). Butuh mesin saya 58 menit untuk melakukan versi pola itu dengan 6 parens terbuka. Untuk menyelesaikan stasis sebelum alam semesta mencapai panas-mati, Anda harus memoise antrian; jika tidak, Anda akan mendapatkan O(n!!)solusi, bukan O(n!). (Golf saya O(n*2^n)bukan O(2^n), karena obenar-benar menghasilkan semua pola hingga rkepindahan, bukan rkepindahan yang tepat . Mudah diperbaiki, tetapi akan membutuhkan biaya beberapa karakter.)
rici