Isi Bracks

18

Kurung Normal ( (), [], <>dan {}) bagus dan tidak ambigu, namun seseorang berpikir itu akan menjadi ide yang baik untuk menggunakan karakter non bracket sebagai tanda kurung. Karakter-karakter ini, |dan ", bersifat ambigu. Misalnya tidak

""""

sesuai dengan

(())

atau

()()

Tidak mungkin dikatakan.

Hal-hal mulai menjadi menarik ketika Anda mencampur jenis kurung ambigu, misalnya

"|""||""|"

Bisa salah satu dari yang berikut ini

([(([]))]),([()[]()]),([()][()])

Tugas

Tugas Anda adalah mengambil string yang terbuat dari karakter yang ambigu dan menghasilkan semua string seimbang yang mungkin dimaksudkan penulis.

Lebih konkret Anda keluaran semua string yang seimbang yang dapat dibuat mengganti |dengan baik [atau ]dan "dengan baik (atau ). Anda seharusnya tidak menghasilkan string seimbang dua kali.

IO

Sebagai input, Anda harus mengambil string yang terdiri dari |dan ". Jika Anda ingin memilih dua karakter berbeda selain |dan "berfungsi sebagai pengganti, Anda dapat melakukannya. Anda harus menghasilkan wadah string yang seimbang. Anda dapat memilih untuk mengganti []dan ()di output dengan dua pasang braket lainnya ( (), [], <>atau {}) yang Anda inginkan. Format output Anda harus konsisten di seluruh proses.

Mencetak gol

Ini adalah sehingga jawaban akan dicetak dalam byte dengan lebih sedikit byte yang lebih baik.

Uji kasus

"" -> ["()"]
"|"| -> []
||| -> []
"""" -> ["(())","()()"]
""|| -> ["()[]"]
"|"||"|" -> ["([([])])"]    
"|""||""|" -> ["([(([]))])","([()[]()])","([()][()])"]    
Wisaya Gandum
sumber
4
menunggu jawaban
BrainFlak
Bisakah kita menggunakan bilangan bulat sebagai ganti string? Bagaimana dengan daftar angka atau bilangan bulat?
Zgarb
@Zgarb Tentu tidak apa-apa
Wheat Wizard

Jawaban:

7

Python 2 , 135 byte

s=input()
for k in range(2**len(s)):
 try:c=''.join("[]() , ,"[int(c)|k>>i&1::4]for i,c in enumerate(s));eval(c);print c[::2]
 except:0

Cobalah online!

Mengharapkan input seperti 2002bukan "||", dan dibungkus dengan tanda kutip.

Iterasikan semua 2 N kemungkinan penugasan "buka" dan "tutup" ke string, buat string cseperti:

"( [ ( ),],[ ( ),],),( ),"

Jika eval-ing string ini melempar pengecualian, itu tidak cocok. Jika tidak, kami mencetak c[::2], memberikan:

([()][()])()
Lynn
sumber
6

Retina , 59 56 55 byte

0`"
<$%">
}0`'
{$%"}
.+
$&_$&
+m`^_|(<>|{})(?=.*_)

A`_

Cobalah online! Sayangnya pengujian untuk dua set tanda kurung yang melebihi golfiness dari satu .NET regex, sehingga menghemat 15 byte untuk diperiksa secara manual. Sunting: Disimpan 3 4 byte berkat @ H.PWiz. Penjelasan:

0`"
<$%">

Temukan "dan buat dua salinan garis, satu dengan a <dan satu dengan a >. Lakukan ini satu "per satu, sehingga masing-masing "menggandakan jumlah garis.

}0`'
{$%"}

Demikian pula dengan ', {dan }. Kemudian, terus ganti sampai semua "dan 'semua salinan sudah diganti.

.+
$&_$&

Buat duplikat kurung, dipisahkan dengan a _.

+m`^_|(<>|{})(?=.*_)

Dalam duplikat, berulang kali hapus tanda kurung yang cocok, sampai tidak ada yang tersisa, dalam hal ini hapus _juga tanda kurung .

A`_

Hapus semua baris yang masih memiliki a _.

Retina , 74 71 70 byte

0`"
<$%">
}0`'
{$%"}
Lm`^(.(?<=(?=\3)(<.*>|{.*}))(?<-3>)|(.))+(?(3)_)$

Cobalah online! Penjelasan: Dua tahap pertama adalah seperti di atas. Tahap ketiga langsung mencetak hasil pencocokan dua set tanda kurung yang cocok. Ini menggunakan grup penyeimbang .NET. Pada setiap tahap dalam pertandingan, regex mencoba untuk mencocokkan karakter, kemudian mencari kembali sepasang tanda kurung yang cocok, lalu periksa bahwa bagian atas tumpukan cocok dengan braket terbuka. Jika dapat melakukan ini, itu berarti braket menyeimbangkan, dan braket terbuka akan muncul dari tumpukan. Kalau tidak, asumsinya adalah kita berada di braket terbuka yang perlu didorong ke tumpukan. Jika asumsi ini tidak berlaku maka tumpukan tidak akan kosong di akhir dan pertandingan akan gagal.

Pendekatan alternatif, juga 74 71 byte:

Lm`^((?=(<.*>|{.*})(?<=(.))).|\3(?<-3>))+(?(3)_)$

Di sini, kita melihat ke depan untuk <... >atau {... }, lalu melihat ke belakang untuk mendorong braket penutup ke tumpukan. Kalau tidak, kita harus mencocokkan dan membuka braket penutup yang sudah kita tangkap sebelumnya. Dalam versi ini regex bahkan mungkin tidak sampai ke akhir string, tetapi beberapa string seperti <<<>akan menyelinap melalui jaring jika kita tidak memeriksa tumpukan kosong.

Neil
sumber
1
Anda dapat menyimpan beberapa byte untuk keluar dengan menggunakan karakter yang berbeda
H.PWiz
@ H.PWiz Ah, saya pasti telah mengabaikan sedikit tentang menggunakan pasangan braket alternatif, terima kasih!
Neil
Anda juga dapat mengubah |input
H.PWiz
2

Sekam , 19 byte

fo¬ω`ḞoΣx½¨÷₂¨ΠmSe→

Cobalah online! Menggunakan karakter dsdalam input, dan pasangan braket yang sesuai dedan stdalam output.

Penjelasan

Idenya adalah untuk menghasilkan semua tanda kurung yang mungkin dari input dan menjaga mereka yang mengurangi ke string kosong ketika kita berulang kali menghapus tanda kurung yang berdekatan. Ini ¨÷₂¨adalah string terkompresi yang mengembang ke "dest", yang dipilih karena memiliki bentuk terkompresi pendek dan terdiri dari pasangan karakter dengan codepoint yang berdekatan. Dengan demikian program ini setara dengan yang berikut ini.

fo¬ω`ḞoΣx½"dest"ΠmSe→  Implicit input, say "ddssdd".
                 m     Map over the string:
                  Se    pair character with
                    →   its successor.
                       Result: ["de","de","st","st","de","de"]
                Π      Cartesian product: ["ddssdd","ddssde",..,"eettee"]
f                      Keep those strings that satisfy this:
                        Consider argument x = "ddsted".
   ω                    Iterate on x until fixed:
         ½"dest"         Split "dest" into two: ["de","st"]
    `Ḟ                   Thread through this list (call the element y):
        x                 Split x on occurrences of y,
      oΣ                  then concatenate.
                          This is done for both "de" and "st" in order.
                        Result is "dd".
 o¬                    Is it empty? No, so "ddsted" is not kept.
                      Result is ["destde","ddstee"], print implicitly on separate lines.
Zgarb
sumber
2

Perl, 56 55 53 byte

Termasuk +1untukn

digunakan [untuk []dan {untuk{}

perl -nE 's%.%"#1$&,+\\$&}"^Xm.v6%eg;eval&&y/+//d+say for< $_>' <<< "[{[[{{[[{["

Menghasilkan semua 2 ^ N kemungkinan, kemudian menggunakan perl evaluntuk memeriksa apakah string seperti '+ [+ {}]' adalah kode yang valid dan jika demikian hapus +dan cetak hasilnya

Ton Hospel
sumber
1

Bersih , 203 186 179 byte

?['(':l][')':t]= ?l t
?['[':l][']':t]= ?l t
?l[h:t]= ?[h:l]t
?[][]=True
?_ _=False
@['"']=[['('],[')']]
@['|']=[['['],[']']]
@[h:t]=[[p:s]\\[p]<- @[h],s<- @t]
$s=[k\\k<- @s| ?[]k]

Cobalah online!

Hanya menggunakan pencocokan pola dan pemahaman.

Suram
sumber
1

Perl, 56 byte

Termasuk +untukn

Menggunakan input [untuk output [atau]

Menggunakan input {untuk output {atau}

perl -nE '/^((.)(?{$^R.$2})(?1)*\2(?{$^R.=$2^v6}))*$(?{say$^R})^/' <<< "[{[[{{[[{["

Menggunakan regex diperpanjang perl untuk mencocokkan kawat gigi sambil melacak pilihan yang dibuat selama backtracking. Ini bisa menjadi jauh lebih efisien daripada menghasilkan semua kandidat 2 ^ N karena sudah menolak banyak tugas yang tidak mungkin saat setengah jalan melalui string input

Ton Hospel
sumber
0

Kotlin , 240 236 234 byte

fold(listOf("")){r,c->r.flatMap{i->when(c){'"'->"()".map{i+it}
else->"[]".map{i+it}}}}.filter{val d=ArrayList<Char>()
it.all{fun f(c:Any)=d.size>1&&d.removeAt(0)==c
when(it){')'->f('(')
']'->f('[')
else->{d.add(0,it);1>0}}}&&d.size<1}

Yg diperindahkan

    fold(listOf("")) {r,c ->
        r.flatMap {i-> when(c) {
            '"'-> "()".map {i+it}
            else -> "[]".map {i+it}
        }}
    }.filter {
        val d = ArrayList<Char>()
        it.all {
            fun f(c:Any)=d.size>1&&d.removeAt(0)==c
            when(it) {
                ')' -> f('(')
                ']' -> f('[')
                else -> {d.add(0,it);1>0}
            }
        } && d.size<1
    }

Uji

private fun String.f(): List<String> =
fold(listOf("")){r,c->r.flatMap{i->when(c){'"'->"()".map{i+it}
else->"[]".map{i+it}}}}.filter{val d=ArrayList<Char>()
it.all{fun f(c:Any)=d.size>1&&d.removeAt(0)==c
when(it){')'->f('(')
']'->f('[')
else->{d.add(0,it);1>0}}}&&d.size<1}

data class Test(val input: String, val outputs: List<String>)

val tests = listOf(
    Test("""""""", listOf("()")),
    Test(""""|"|""", listOf()),
    Test("""|||""", listOf()),
    Test("""""""""", listOf("(())","()()")),
    Test("""""||""", listOf("()[]")),
    Test(""""|"||"|"""", listOf("([([])])")),
    Test(""""|""||""|"""", listOf("([(([]))])","([()[]()])","([()][()])"))
)

fun main(args: Array<String>) {
    for ((input, output) in tests) {
        val actual = input.f().sorted()
        val expected = output.sorted()
        if (actual != expected) {
            throw AssertionError("Wrong answer: $input -> $actual | $expected")
        }
    }

Suntingan

jrtapsell
sumber
0

C (gcc) , 315 byte

j,b;B(char*S){char*s=calloc(strlen(S)+2,b=1)+1;for(j=0;S[j];b*=(S[j]<62||*--s==60)*(S[j++]-41||*--s==40))S[j]==60?*s++=60:0,S[j]<41?*s++=40:0;return*s>0&*--s<1&b;}f(S,n,k)char*S;{if(n<strlen(S))for(k=2;k--;)S[n]==46-k-k?S[n]=40+k*20,f(S,n+1),S[n]=41+k*21,f(S,-~n),S[n]=46-k-k:0;else B(S)&&puts(S);}F(int*S){f(S,0);}

Cobalah online!


C (gcc) , 334 byte (versi lama)

j,b;B(char*S){char*s=calloc(strlen(S)+2,1)+1;for(b=1,j=0;S[j];j++){if(S[j]==60)*s++=60;if(S[j]<41)*s++=40;b*=!(S[j]>61&&*--s!=60)*!(S[j]==41&&*--s!=40);}return*s>0&*--s<1&b;}f(S,n,k)char*S;{if(n>=strlen(S))return B(S)&&puts(S);for(k=0;k<2;k++)S[n]==46-k-k&&(S[n]=40+k*20,f(S,n+1),S[n]=41+k*21,f(S,-~n),S[n]=46-k-k);}F(char*S){f(S,0);}

Cobalah online!


Penjelasan (versi lama)

j,b;B(char*S){                   // determine if string is balanced
 char*s=calloc(strlen(S)+2,1)+1; // array to store matching brackets
 for(b=1,j=0;S[j];j++){          // loop through string (character array)
  if(S[j]==60)*s++=60;           // 60 == '<', opening bracket
  if(S[j]<41)*s++=40;            // 40 == '(', opening bracket
  b*=!(S[j]>61&&*--s!=60)*       // 62 == '>', closing bracket
   !(S[j]==41&&*--s!=40);}       // 41 == ')', closing bracket
 return*s>0&*--s<1&b;}           // no unmatched brackets and no brackets left to match
f(S,n,k)char*S;{                 // helper function, recursively guesses brackets
 if(n>=strlen(S))                // string replaced by possible bracket layout
  return B(S)&&puts(S);          // print if balanced, return in all cases
 for(k=0;k<2;k++)                // 46 == '.', guess 40 == '(',
  S[n]==46-k-k&&(S[n]=40+k*20,   //  guess 41 == '(', restore
   f(S,n+1),S[n]=41+k*21,        // 44 == ',', guess 60 == '<',
   f(S,-~n),S[n]=46-k-k);}       //  guess 62 == '>', restore
F(char*S){f(S,0);}               // main function, call helper function

Cobalah online!

Jonathan Frech
sumber
Tidak bisakah Anda menggunakan array panjang variabel GCC untuk menyingkirkan calloc?
Ton Hospel
@TonHospel Saya kemudian akan, baik perlu mengubah array ke pointer atau memperkenalkan variabel indeks lain, yang saya tidak tahu apakah itu layak, karena saya gunakan *s++di beberapa tempat.
Jonathan Frech
char S[n],*s=Smasih lebih pendek darichars*s=calloc(n,1)
Ton Hospel
@TonHospel Saya tidak begitu tahu mengapa, meskipun sepertinya tidak berhasil .
Jonathan Frech
@ceilingcat Terima kasih.
Jonathan Frech