Penyeimbangan braket

20

Anda akan diberi string (mungkin kosong) yang berisi tanda kurung ( [{()}]) dan karakter lainnya ( A- Z, a- z, 0- 9, tanda baca). Anda perlu memeriksa apakah mematuhi aturan berikut:

  • Karakter non-braket diabaikan.
  • Setiap braket terbuka [{(memiliki braket penutup )}]. Jadi [](tidak diijinkan.
  • Kurung bersarang dengan benar. [(])tidak diizinkan.
  • Kurung keriting tidak dapat berisi kurung kotak di dalamnya. Kurung sederhana tidak bisa mengandung kurung keriting atau bujur sangkar di dalamnya. Jadi [({})], [{[]}]dan ({})tidak diijinkan. Kurung dapat disarangkan dengan kurung serupa, jadi [[{((()))}{{(())}}]()]{()}diizinkan.

Output adalah nilai kebenaran / falsey tunggal sesuai pilihan Anda.

Kode terpendek menang.


Uji kasus

b[[a{(/)}(())+={{}-}],] -> Valid

([h][e][l][l][o]) -> Tidak Valid

[///[{(\/(arg()))}1{{((-)-2)}}]()]{()} -> Valid

hi -> Valid

ghosts_in_the_code
sumber
2
Kemungkinan duplikat kurung Perbaiki tidak seimbang
FUZxxl
9
@FUZxxl Sepertinya itu tantangan yang jauh lebih sulit. Saya merasa seperti ada korban penipuan lain di suatu tempat.
Martin Ender
@ MartinBüttner Ya, itu bisa. Saya telah menambahkan beberapa testcases. Dan apakah Anda menemukan duplikat yang Anda cari?
ghosts_in_the_code
1
@ MartinBüttner: Tantangan ini mungkin apa yang Anda pikirkan.
Ilmari Karonen
1
Saya pikir kita harus menutup pertanyaan lain sebagai duplikat dari ini; ini lebih baik karena memiliki bonus lebih sedikit.
lirtosiast

Jawaban:

5

Retina , 84 byte

^([^][}{)(]|()\(|(?<-2>)\)|(?!\2)((){|(?<-4>)}|(?!\4)(()\[|(?<-6>)])))*$(?!\2|\4|\6)

Cobalah online.

Ini adalah ekstensi yang cukup lurus ke depan (tetapi golf) dari .NET kurung dasar memeriksa .NET regex .

Meskipun ini sangat mungkin dengan kelompok penyeimbang, rekursi Perl pasti memiliki keunggulan di sini . Namun, kedua pendekatan tersebut dikalahkan dengan membuang keanggunan pertandingan regex tunggal demi mengurangi input secara bertahap melalui penggantian yang berulang, seperti yang dijawab Digital Trauma . Ini dapat diimplementasikan dalam 34 byte di Retina, tapi saya ragu untuk memposting kode sendiri, karena saya tidak datang dengan ide.

Martin Ender
sumber
5

Retina, 34

Pertama, kredit yang harus dibayar:

Saya secara mandiri (nanti) datang dengan pendekatan yang sama di sed , jadi saya harap saya tidak menginjak-injak jari kaki ( besar atau sebaliknya) dengan memposting ini:

[^][(){}]

+`\(\)

+`{}

+`\[]

^$

Jadi sekarang dengan sudo apt-get install mono-completedan git clone https://github.com/mbuettner/retina.gitsaya memiliki retina yang berfungsi pada VM Ubuntu saya. Inilah hasil tesnya:

$ while read; do echo "Input: \"$REPLY\", Ouput: $( mono Retina.exe -s brbal.ret <<< "$REPLY" )" ; done < ../brbal.txt 
Input: "[[{((()))}{{(())}}]()]{()}", Ouput: 1
Input: "b[[a{(/)}(())+={{}-}],]", Ouput: 1
Input: "[///[{(/(arg()))}1{{((-)-2)}}]()]{()}", Ouput: 1
Input: "hi", Ouput: 1
Input: "", Ouput: 1
Input: "", Ouput: 1
Input: "([h][e][l][l][o])", Ouput: 0
Input: "[](", Ouput: 0
Input: "[(])", Ouput: 0
Input: "[({})]", Ouput: 0
Input: "[{[]}]", Ouput: 0
Input: "({})", Ouput: 0
$ 
Trauma Digital
sumber
@ThomasKwa Lihat hasil tes. Saya percaya kode itu benar dan semua testcas lewat. Apakah ada masalah khusus yang Anda lihat dalam kode, atau testcase tertentu yang Anda pikir akan gagal?
Trauma Digital
@ThomasKwa Saya tidak mem-porting kode mereka, karena saya tidak tahu apa yang dilakukan ESMIN. Saya hanya menulis kode ini berdasarkan apa yang kelihatannya akan dilakukan, jadi saya tidak berpikir ada alasan mengapa ini memiliki bug yang sama.
Martin Ender
Wow, @ MartinBüttner, Anda benar! Ya, saya pikir mengganti kurung yang cocok secara rekursif adalah yang paling logis. Tweak cepat agar sesuai dengan spesifikasi kode membuatnya berfungsi.
Mama Fun Roll
3

Sed, 53

s/[^][(){}]//g
:;s/()//;t
:b;s/{}//;tb
:c;s/\[\]//;tc

Di sini saya mengklaim itu sejak itu sed tidak benar-benar memiliki konsep kebenaran / falsey, maka saya mendefinisikan string kosong untuk berarti kebenaran dan semua string lainnya berarti falsey.

Jika itu tidak dapat diterima, maka kita dapat menambahkan beberapa baris, dengan demikian:

Sed, 66

s/[^][(){}]//g
:;s/()//;t
:b;s/{}//;tb
:c;s/\[\]//;tc
/./c0
/^$/c1

Ini menghasilkan 0 untuk false dan 1 untuk true.

Trauma Digital
sumber
Lihat komentar saya pada jawaban molarmanful untuk versi Retina dari solusi yang sama persis (pada 34 byte; pencetakan 0atau 1). Saya tidak bisa mengatakan siapa yang mempostingnya, tetapi mungkin Anda berdua.
Martin Ender
3

CJam, 27 26 byte

"(){}[]"q1$f&_,@2/e*{/s}/!

Ini mencetak 1 (benar) atau 0 (salah). Cobalah online! atau verifikasi semua kasus uji.

Bagaimana itu bekerja

"(){}[]"                    Push that string.
        q                   Read all input and push it on the stack.
         1$                 Copy the bracket string.
           f&               Intersect each input character with the bracket string.
                            This pushes an array of singleton and empty strings.
             _,             Get the length of the array (L), i.e., the number of
                            characters in the original input.
               @            Rotate the bracket string on top of the stack.
                2/          Split it into ["()" "{}" "[]"].
                  e*        Repeat each character pair L times.
                    {  }/   For each character pair.
                     /      Split the string on the stack at occurrences of that
                            character pair. This dosn't work properly the first
                            time, since there's a string array on the stack.
                      s     Flatten the resulting array of strings.
                         !  Apply logical NOT.
Dennis
sumber
3

𝔼𝕊𝕄𝕚𝕟, 43 karakter / 62 byte

!Մ(Մ(Մ(ïċ/⁅⬮[\]{}]⌿),`⬮`,⬯),`{}`,⬯),`[]`,⬯)

Try it here (Firefox only).

Nggak.


Namun, jika saya menggunakan fitur yang baru diimplementasikan, saya bisa turun ke 28 karakter / 47 byte:

!ïċ/⁅⬮[\]{}]⌿)ė`⬮”ė`{}”ė`[]”
Mama Fun Roll
sumber
Ohhh, apakah Anda menghapus tanda kurung yang cocok dari dalam ke luar? Itu akan menjadi hanya 34 byte di Retina: pastebin.com/bU77LzbR
Martin Ender
2

Japt , 42 37 byte

Disimpan 5 byte dengan fitur yang saya tidak sadari bahasa saya miliki ... Terima kasih telah menambahkannya, @Downgoat!

Japt benar-benar membutuhkan dukungan RegExp yang lebih baik ...

!Uo"()[\\]\{}" e"\\(\\)" e"\{}" e"\\[]

Cobalah online!

Bagaimana itu bekerja

               // Implicit: U = input string
Uo"()[\\]\{}"  // Remove all non-bracket.
e"\\(\\)"      // Recursively remove all pairs of simple brackets.
e"\{}"         // Recursively remove all pairs of curly brackets.
e"\\[]         // Recursively remove all pairs of square brackets.
!              // Return the Boolean NOT of the result.
               // (true for empty string, false for anything else)
               // Implicit: output last expression
Produksi ETH
sumber
2

C99, 226 208 207 Bytes

Ini adalah pertama kalinya saya mencoba bermain golf

#define S s[i]
t(s,i)char*s;{int a[]={['[']=0,['{']=0,['(']=0};for(i=0;S*!(S=='{'&a['(']|S=='['&(a['(']|a['{'])|S==']'&(a['(']|a['{'])|S=='}'&a['(']);i++)a[S]++,a[S-S/90-1]--;return !(a['[']+a['{']+a['(']);}

Dapat dibaca:

int t(char* s){
    int a[265]={['[']=0,['{']=0,['(']=0};
    for(int i=0;s[i]&&!((s[i]=='{'&a['(']>0)|(s[i]=='['&(a['(']>0|a['{']>0))|(s[i]==']'&(a['(']>0|a['{']>0))|(s[i]=='}'&a['(']>0));i++){
        a[s[i]]++;
        a[s[i]-(s[i]/90+1)]--;
    }
    return !(a['[']+a['{']+a['(']);
}

Ada buffer overflow tetapi tampaknya tidak mempengaruhi apa pun - saya percaya ini karena perataan.

dj0wns
sumber
1
Anda dapat menghilangkan spasi dichar* s
Cyoce
Tidak tahu itu - terima kasih
dj0wns
1

Perl, 50 + 1 = 51 byte

$_=/^((([^][)(}{]|\((?3)*\))|{(?2)*})|\[(?1)*])*$/

Membutuhkan -pbendera dan cetakan 1untuk hasil yang benar dan tidak ada yang palsu. Saya menghitung -psebagai satu, karena dapat dikombinasikan dengan -e:

> perl -pe '$_=/^((([^][)(}{]|\((?3)*\))|{(?2)*})|\[(?1)*])*$/'

Kode ini pada dasarnya hanya pencocokan regex biasa terhadap input, menggunakan fitur regex rekursif bagus Perl.

Terima kasih untuk Dennis yang telah membantu saya menguji ini dan bermain golf di boiler boiler.

Martin Ender
sumber
1

Python 3: 120 byte

Membangun pada jawaban @ Adnan , terbukti lebih pendek untuk digunakan:

import re
x=re.sub('[^[\](){}]','',input())  
for i in('()','{}','[]'):  
 while x.find(i)>=0:x=x.replace(i,'')  
print(x=='')
karhell
sumber
1

Python 3, 196 170 160 154 byte

Sangat canggung, terima kasih kepada Mego karena telah menghemat 6 byte:

d=y=""
for C in input():
 for a in "[](){}":y+=C*(C==a)
 y=y.replace("()",d)
x=y
for r in y:x=x.replace("{}",d)
for s in y:x=x.replace("[]",d)
print(x==d)
Adnan
sumber