Apakah kurung sepenuhnya cocok?

56

Anda harus menulis sebuah program atau fungsi yang mengambil string tanda kurung dan menampilkan apakah string itu benar-benar cocok atau tidak. Program Anda harus mencetak nilai yang benar atau salah , dan IO bisa dalam format yang masuk akal .

Aturan dan definisi:

  • Untuk tujuan tantangan ini, "braket" adalah salah satu karakter: ()[]{}<>.

  • Sepasang tanda kurung dianggap "cocok" jika tanda kurung buka dan tutup berada dalam urutan yang benar dan tidak memiliki karakter di dalamnya, seperti

    ()
    []{}
    

    Atau jika setiap subelemen di dalamnya juga cocok.

    [()()()()]
    {<[]>}
    (()())
    

    Subelemen juga dapat disarungkan beberapa lapisan.

    [(){<><>[()]}<>()]
    <[{((()))}]>
    
  • String dianggap "Sepenuhnya cocok" jika dan hanya jika:

    1. Setiap karakter tunggal adalah braket,

    2. Setiap pasangan braket memiliki braket pembuka dan penutup yang benar dan dalam urutan yang benar, dan

    3. Setiap braket dicocokkan.

  • Anda dapat berasumsi bahwa input hanya akan berisi ASCII yang dapat dicetak .

Tes IO

Berikut adalah beberapa masukan yang harus mengembalikan nilai kebenaran:

()
[](){}<>
(((())))
({[<>]})
[{()<>()}[]]
[([]{})<{[()<()>]}()>{}]

Dan berikut adalah beberapa output yang harus mengembalikan nilai palsu:

(               Has no closing ')'
}{              Wrong order
(<)>            Each pair contains only half of a matched element
(()()foobar)    Contains invalid characters
[({}<>)>        The last bracket should be ']' instead of '>'
(((()))         Has 4 opening brackets, but only 3 closing brackets.

Seperti biasa, ini adalah kode-golf, sehingga celah standar berlaku, dan jawaban tersingkat dalam byte menang.

DJMcMayhem
sumber
1
Terkait.
Martin Ender
7
Catatan untuk calon pemilih dekat: Tantangan yang saya tautkan juga menyertakan urutan prioritas untuk jenis braket sehingga mereka tidak dapat disarangkan dalam urutan acak. Saya pikir itu membuatnya cukup berbeda.
Martin Ender
Apakah [}cocok? Dan jika tidak, di mana itu dikecualikan oleh aturan-aturan ini?
user207421
2
@ EJP Tidak, tidak. Each pair of brackets has the correct opening and closing bracket and in the right order.
DJMcMayhem
6
Saya akan mengunggulkan solusi pertama dalam kurung
leo

Jawaban:

17

05AB1E , 19 byte

Masukan diberikan dalam tanda kutip . Kode:

"[](){}<>"2÷)"":g2Q

Nah omong kosong, banyak bug dan fitur yang tidak diterapkan ditemukan. Penjelasan:

"[](){}<>"           # Push this string
          2÷         # Split into pieces of two
            )        # Wrap it into an array (which should not be needed)
             ""      # Push an empty string
               :     # Infinite replacement

Ini sebenarnya bagian yang sulit. Seperti apa ini dalam pseudocode adalah:

input().replace(['[]', '()', '{}', '<>'], "")

Ini dicakup oleh bagian ini dari kode 05AB1E :

if type(b) is list:
    temp_string = temp_string_2 = str(a)
    while True:
        for R in b:
            temp_string = temp_string.replace(R, c)
        if temp_string == temp_string_2:
            break
        else:
            temp_string_2 = temp_string
    stack.append(temp_string)

Seperti yang Anda lihat, ini adalah penggantian tanpa batas (dilakukan hingga string tidak berubah lagi). Jadi, saya tidak perlu khawatir tentang pengaturan penggantian menjadi satu lingkaran, karena ini sudah builtin. Setelah itu:

                g    # Take the length of the final string
                 2Q  # Check if equal with 2 (which are the quotes at the end)

Menggunakan pengodean CP-1252 . Cobalah online! (sedikit dimodifikasi karena versi di atas sudah usang).

Adnan
sumber
1
Golf yang bagus!
SamyQc
1
Apakah ini sebelum õditambahkan?
Zacharý
@ Zacharý Ya, itu benar
Adnan
33

Brain-Flak , 1101, 1085 , 981 byte

{(<(({}))((((()()()()()){}){}){})({}[{}]<(())>){((<{}{}>))}{}>{({}<>)(<>)}{}<(({
}))((((()()()()()){}){}){}())({}[{}]<(())>){((<{}{}>))}{}>{({}<>)({}[{}](<()>)){
{}{}(<(())>)}{}{<>{{}}<>{{}}((<()>))}{}(<>)}{}<(({}))(((((()()()()()){}){})){}{}
)({}[{}]<(())>){((<{}{}>))}{}>{<({}()<>)>()(<>)}{}<(({}))(((((()()()()()){}){})(
)){}{})({}[{}]<(())>){((<{}{}>))}{}>{<({}()<>)>()({}[{}](<()>)){{}{}(<(())>)}{}{
<>{{}}<>{{}}((<()>))}{}(<>)}{}<(({}))((((()()()){}){}()){({}[()])}{})({}[{}]<(()
)>){((<{}{}>))}{}>{<({}()()<>)>()(<>)}{}<(({}))((((((()()()()()){})){}{}())){}{}
)({}[{}]<(())>){((<{}{}>))}{}>{<({}()()<>)>()({}[{}](<()>)){{}{}(<(())>)}{}{<>{{
}}<>{{}}((<()>))}{}(<>)}{}<(({}))((((((()()()()()){}){}){}())){}{})({}[{}]<(())>
){((<{}{}>))}{}>{<({}()()()<>)>()(<>)}{}<(({}))((((((()()()()()){}){}){}())()){}
{})({}[{}]<(())>){((<{}{}>))}{}>{<({}()()()<>)>()({}[{}](<()>)){{}{}(<(())>)}{}{
<>{{}}<>{{}}((<()>))}{}(<>)}{}<{}>[()]){<>{{}}(<()>)<>{{}}(<()>)}{}}<>([]<>)({}<
(())>){((<{}{}>))}{}

Cobalah online!

Ini adalah 980 byte kode sumber, dan +1untuk -aflag memungkinkan input ASCII (tetapi output desimal)

Ini adalah jawaban yang saya sudah lama ingin menulis untuk sangat sangat lama. Setidaknya 6 bulan. Saya menunggu untuk memposting ini karena saya tahu bahwa menjawab tantangan ini akan sangat sulit di otak. Tapi itu layak untuk satu alasan yang sangat penting: Kode sumber itu sendiri adalah input yang benar, yang merupakan inti dari bahasa ini sendiri.

Dan ketika saya menulis di sini , pertanyaan ini adalah apa yang mengilhami saya untuk menulis kritik.

Tak lama setelah saya menulis Apakah tanda kurung sepenuhnya cocok ?, membuat saya bertanya-tanya berapa banyak informasi yang dapat Anda simpan dengan tanda kurung yang cocok. Satu hal yang menonjol bagi saya, adalah bahwa meskipun Anda hanya memiliki 4 "atom":

(){}[]<>

Anda benar-benar memiliki 8 unit informasi untuk disampaikan, karena masing-masing jenis braket ini dapat kosong, atau memiliki tanda kurung lain di antaranya, yang merupakan bagian informasi yang secara fundamental berbeda. Jadi, saya memutuskan untuk menulis bahasa yang hanya memungkinkan tanda kurung yang cocok, dan di mana tanda kurung kosong menyampaikan sesuatu yang berbeda dari tanda kurung dengan tanda kurung lain di dalamnya.

Jawaban ini membutuhkan sekitar dua jam untuk menulis. Saya akui golfnya buruk, kebanyakan karena banyak kode diulang untuk setiap jenis braket. Tetapi saya sebagian besar kagum bahwa saya bisa menulis jawaban sama sekali, terutama mengingat bahwa Brain-Flak adalah

Esolang minimalis yang dirancang agar menyakitkan untuk digunakan

Saya akan mencoba untuk menurunkannya nanti, tetapi saya tetap ingin mendapatkan ini di luar sana.

Saya punya penjelasan mendetail, tapi panjangnya sekitar 6 ribu karakter, jadi saya pikir tidak bijaksana untuk menyisipkan semuanya ke dalam jawaban ini. Anda dapat membacanya di sini jika Anda mau. Saya akan menambahkan penjelasan singkat di sini.

Ide dasarnya, adalah kita mengulangi langkah-langkah berikut untuk setiap karakter di stack:

  • Kami memeriksa setiap karakter untuk melihat apakah itu cocok dengan braket apa pun. Jika ini adalah braket pembuka, kami mendorong nomor ke tumpukan lain sesuai dengan pemetaan berikut:

    ( = 1
    < = 2
    [ = 3
    { = 4
    
  • Kemudian kami memeriksa untuk melihat apakah cocok dengan braket penutup. Jika ya, kami mendorong nomor yang setara ke tumpukan alternatif, seperti halnya untuk membuka tanda kurung. Kemudian , kami memeriksa apakah dua angka teratas sama. Jika ya, keduanya akan muncul dan program berlanjut seperti biasa. Jika tidak, kami menghapus kedua tumpukan (untuk menghentikan perulangan) dan mendorongnya ke tumpukan alternatif. Ini pada dasarnya adalah pernyataan "istirahat".

  • Setelah memeriksa 8 jenis braket, kami mendorong nilai run ini melalui loop. Karena sebagian besar nol, sebagian besar potongan yang memiliki nilai adalah persyaratan saat kami membandingkannya dengan tanda kurung. Jadi jika ada braket yang cocok, seluruh loop memiliki nilai 1. Jika tidak ada yang melakukannya, seluruh loop memiliki nilai 0. Dalam hal ini, kami akan menghapus kedua tumpukan dan mendorong 0 ke tumpukan alternatif. Sekali lagi, ini seperti pernyataan "istirahat".

Setelah loop utama ini berjalan, sisanya cukup sederhana. Kami berada di tumpukan utama (kosong), dan tumpukan alternatif kosong (jika tanda kurung cocok) atau tidak kosong jika tidak. Jadi kami menjalankan ini:

#Toggle to the alternate stack
<>

#Push this stack-height onto main-stack
([]<>)

#Logical not
({}<(())>){((<{}{}>))}{}

Ini akan mendorong 0 atau 1 ke tumpukan utama, dan ketika program berakhir, dicetak secara implisit.


  • Terima kasih kepada @WheatWizard untuk membuat potongan "equals" dan "logical not" yang bersih, dan untuk memperbarui wiki github secara teratur dengan contoh-contoh yang berguna.

  • Terima kasih kepada @ ASCII-only untuk menulis metagolfer integer online yang sangat membantu dalam menulis program ini


revisi

  • Menghapus beberapa redundansi pop push

  • Mengubah logika penghitung nol saya

DJMcMayhem
sumber
1
Awwwwwweeeeesommmmeeeee!
Arjun
23

Brain-Flak , 204 196 190 byte

{({}<>)<>((((()()()()()){})(({}){})())({}(({})((({}){})(<()>))))())(({<({}<>[({})])>[()]{()(<{}>)}{}<>}{}()<({}<>[({})]){(<{}({}())>)}{}<>>)){(<({}{}<>[{}]{}<>)>)}{}{<>{{}}}{}}<>((){[()]<>})

Cobalah online!

-8 Bytes berkat Wheat Wizard. -6 byte terima kasih kepada Jo King.

Penjelasan

Program ini menyimpan kode karakter semua tanda kurung yang tidak tertutup pada tumpukan kedua. Pasangan bracket <>, []dan {}masing-masing memiliki kode karakter yang berbeda dengan tepat 2, sehingga tidak perlu untuk memeriksa mereka secara khusus. Pasangan ini ()hanya berbeda dengan 1, jadi kami memeriksa secara (khusus, dan secara efektif mengurangi byte tersebut (sebenarnya setiap byte bertambah) sebelum melanjutkan.

# While there are bytes left to process
{

 # Move byte to second stack
 ({}<>)<>

 # Push 40, 0, 40, 60, 91, 123: (, then null, then all four opening brackets
 ((((()()()()()){})(({}){})())({}(({})((({}){})(<()>))))())

 ((

   # For each opening bracket type:
   {

    # Evaluate as zero
    <

     # Compute difference between bracket type and input byte
     ({}<>[({})])

    >

    # Evaluate loop iteration as -1 if equal, 0 otherwise
    [()]{()(<{}>)}{}<>

   }

   # Remove the 0 that was inserted to terminate that loop
   {}

   # Add 1 to result
   ()

   # Evaluate rest of this expression as zero
   <

    # Determine whether the byte is open parenthesis
    ({}<>[({})])

    # If not:
    {

     # Add 1 to byte and break if
     (<{}({}())>)

    }{}

    # Return to main stack
    <>

   >

 # Push result twice (0 if matched an opening bracket, 1 otherwise)
 ))

 # If byte was not an opening bracket:
 {

  # Push zero to break out of if
  (<

    # Push (open bracket + 2 - byte) below that zero
    ({}{}<>[{}]{}<>)

  >)

 }{}

 # If byte was neither an opening bracket nor the appropriate closing bracket:
 {

  # Clear alternate stack and stay there to break out of main loop early
  <>{{}}

 }{}

# End of main loop
}

# If a prefix was invalid, the top of the other stack is the same nonzero value
# that made us break out in the first place. If the string was a valid prefix,
# the other stack contains every unclosed bracket.  If the string is balanced,
# there are none of these. Thus, the other stack is empty if the
# brackets are balanced, and has a nonzero value on top otherwise.

# Push 1 on other stack if empty, and 0 on current stack otherwise
<>((){[()]<>})
Nitrodon
sumber
"logical not of difference" (juga dikenal sebagai sama dengan) bisa lebih pendek sebagai([{}]<>({}))((){[()](<{}>)}{})
Wheat Wizard
Saya pikir Anda dapat mengganti cek terakhir dengan ({<>[()]}())-6 byte
Jo King
@JoKing, terima kasih. Saya pikir saya tidak akan pernah melihatnya.
Nitrodon
Ya, saya menemukan jawabannya dalam jawaban saya sendiri dan menyadari bahwa itu berlaku untuk Anda juga
Jo King
13

JavaScript (ES6), 52 50 byte

f=s=>(t=s.replace(/\(\)|\[]|{}|<>/,''))==s?!s:f(t)

Hapus kurung berulang kali hingga hasilnya sama dengan aslinya, lalu kembalikan salah kecuali string sekarang kosong.

Sunting: Disimpan 2 byte berkat @ edc65.

Neil
sumber
11

CJam, 25 24 23 21 byte

Terima kasih kepada Sp3000 untuk menghemat 2 byte.
Terima kasih kepada jimmy23013 untuk menghemat 2 byte.

q_,{()<>}a`$2/*{/s}/!

Suite uji.

Bekerja pada dasarnya sama dengan jawaban yang lain: kita berulang kali menghapus (), [], <>dan {}dari string dan memeriksa apakah kita berakhir dengan string kosong. Untuk menghindari harus memeriksa kapan kita selesai, kita menghapus pasangan Nkali di mana Npanjang string, yang selalu cukup (karena setiap iterasi akan menghapus setidaknya dua karakter, kecuali kita selesai). Saya senang melihat ini tidak mengalahkan Retina. :) (Meskipun Pyth atau Jelly mungkin ...)

Ada satu trik golf yang menyenangkan di sini: untuk mendapatkan string, ()<>[]{}kami menggunakan yang berikut ini:

{()<>}a`$

The, {()<>}hanyalah sebuah blok (yaitu fungsi), yang berisi tanda kurung lain sebagai kode. Dengan akami bungkus blok dalam sebuah array. The `stringifies bahwa array, yang memberikan "[{()<>}]". Akhirnya, kami mengurutkan string dengan $, yang mengatur ulang tanda kurung ()<>[]{}.

Martin Ender
sumber
Saya tidak terbiasa dengan bahasa Anda, tetapi deskripsi Anda tentang trik golf Anda membuatnya terdengar seperti ()<>[]{}`akan berfungsi dengan baik, dan menjadi jumlah byte yang sama, bukan?
Mooing Duck
1
@ MoooDuck No karena ()<>ada empat operator (penurunan, kenaikan, dan kemudian perbandingan atau pemotongan tergantung pada operan), yang akan dieksekusi segera, sedangkan {}menunjukkan sebuah blok (setara dengan fungsi CJam), yaitu sepotong kode yang hanya didorong ke tumpukan tanpa mengevaluasinya segera. Itu sebabnya saya perlu {}membungkus ()dan <>, tetapi kemudian menggunakan auntuk meletakkan semuanya dalam array lebih pendek dari [...].
Martin Ender
10

Python, 67 byte

lambda s:eval("s"+".replace('%s','')"*4%([],(),{},'<>')*len(s))==''

Menghasilkan dan mengevaluasi ekspresi yang terlihat seperti

s.replace('[]','').replace('()','').replace('{}','').replace('<>','').replace('[]','').replace('()','').replace('{}','').replace('<>','')

dan memeriksa apakah hasilnya kosong.

Sp3000 menyimpan 8 byte dengan menunjukkan bahwa [],(),{}dapat ditubuhkan tanpa tanda kutip karena mereka objek Python, dan bahwa dua parens tidak diperlukan.

Tidak
sumber
8

Yacc, 119 byte

Tidak menggunakan regex / ganti.

%%input:r;r:%empty|'['r']'r|'{'r'}'r|'('r')'r|'<'r'>'r;%%yylex(){return getchar();}main(){return yyparse();}yyerror(){}

Tidak disatukan

%%                              # Grammar in BNF
input:
  r;
r:
  %empty
| '['r']'r
| '{'r'}'r
| '('r')'r
| '<'r'>'r;
%%                              # Minimal parser invocation and lexer
yylex(){return getchar();}
main(){return yyparse();}
yyerror(){}

Kompilasi

yacc -o bracket.c bracket.y
cc -o bracket bracket.c

Pemakaian

~/ % echo -n "<()[]>" | ./bracket
~/ %
~/ % echo -n "{" | ./bracket
~/ 1 %                                                                         :(
Rainer P.
sumber
7

Pyth, 31 25 24 byte

Golf turun menjadi 25 byte berkat FryAmTheEggMan Dihapus 1 byte

VQ=:Q"<>|\[]|{}|\(\)"k;!

Coba di sini: Test suite !

Saya masih pemula Pyth, bantuan apa pun dihargai.

Penjelasan

VQ                         For N in range(0, len(z)), with Q being the evaluated input.
                           Optimal solution would be to use range(0, len(z)/2) instead, but it add two bytes.
  =:Q"<>|\[]|{}|\(\)"k     assign Q without {}, [], <> nor () (regex replacement) to Q
                      ;    End of For loop
                       !   Logical NOT of Q's length (Q is the input, but has gone several times through y, and Q is implicit).
                           This last operation returns True if len(Q) is 0 (which means all brackets were matched), False otherwise

BTW, selamat untuk jawaban Pyth lainnya (yang saat ini 20 byte)

FliiFe
sumber
Selamat Datang di Programming Puzzles dan Code Golf!
Adnan
@ Adnan Terima kasih! Ini golf pertama saya!
FliiFe
Golf pertama yang bagus! Dengan beberapa menata ulang dan hal-hal, Anda bisa mendapatkan 25: Vz=:z"<>|\[]|{}|\(\)"k;!z. Terutama catatan, Anda pada dasarnya tidak perlu menggunakan ljika Anda tidak benar-benar membutuhkan nomor, dan =secara otomatis menebak variabel pertama yang digunakan dalam ekspresi. Beri tahu saya jika Anda ingin saya menjelaskan hal lain di ruang obrolan Pyth :)
FryAmTheEggman
@FryAmTheEggman Terima kasih! Saya tidak tahu litu tidak perlu, itu bagus untuk diketahui. Pada awalnya, saya mendeklarasikan fungsi karena logika saya berbeda, dan lupa menghapusnya. Haruskah saya memasukkan jawaban Anda untuk saya? (Saya seorang pemula>. <)
FliiFe
3
Secara umum, jika itu diposting dalam komentar maka penulis komentar ingin Anda menggunakannya. Jadi silakan saja! :)
FryAmTheEggman
6

Pyth, 20 byte

!uuscNTc"[](){}<>"2G

Cobalah online: Test Suite

Berulang kali menghapus kejadian [], (), <>dan {}oleh pemecahan dan re-penggabungan. Cek apakah string yang dihasilkan kosong atau tidak.

Jakube
sumber
4

Javascript ES6, 54 byte

f=_=>_.match(x=/\(\)|\[]|{}|<>/)?f(_.replace(x,'')):!_

Menggunakan implementasi pengganti rekursif. Cukup sederhana.

Mama Fun Roll
sumber
4

Regex (rasa PCRE), 41 37 byte

^((<(?1)>|{(?1)}|\[(?1)]|\((?1)\))*)$

Hanya solusi standar dengan regex rekursif.

Terima kasih jimmy23013 untuk mencukur 4 byte

n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳
sumber
4

Perl, 34 33 byte

Termasuk +2 untuk -lp

Jalankan dengan input pada STDIN:

./brackets.pl <<< "{<>()}"

brackets.pl:

#!/usr/bin/perl -lp
s/\(\)|\[]|<>|{}//&&redo;$_=!$_

Temukan pasangan braket pertama tanpa apapun di antara mereka dan menghapusnya selama ada. Kemudian periksa apakah string terakhir kosong.

Ton Hospel
sumber
Tidak akan s/\(\)|\[]|<>|{}//&&redo;$_=!$_bekerja :)
Dada
Akan lebih bagus jika Anda bisa memberikan penjelasan juga.
Prashant Pokhriyal
@Dada tentu saja. Aku pasti sudah pikun ..
Ton Hospel
4

Brain-Flak , 204 byte

(()){{}{({}<>)<>}<>({<(<(({})<>)>)(((((((([(())()()()]){}){}){}())(()))(((())()){}()){})){})(({<(({}<>{}[()]))>(){[()](<{}>)}{}<>}{}))<>{}<>{{}({}[({})]<>({})){(<>)(<>)}{}{}(<>)}{}>{}<>}<>)}{}((){<>[()]})

Cobalah online!

Tidak sesingkat jawaban Nitroden , tetapi menggunakan pendekatan yang sangat berbeda. Yang ini berjalan melalui input berulang kali, menghapus pasangan kurung yang cocok setiap kali sampai tidak ada yang tersisa. Pada titik itu jika ada sesuatu yang tersisa di tumpukan, maka string tidak sepenuhnya cocok.

Penjelasan:

(())  Push 1 to simulate the check at the start of the loop
{  While check
	{}           Pop check
	{({}<>)<>}<> Reverse input
	({           Loop over input
		< Don't push the values of these calculations
		(<(({})<>)>)  Create a copy of the top of the input and push to the other stack
		(((((
		((([(())()()()]){}){}){}())
		(()))
		(((())()){}()){})
		){})          Push the differences in values of the end brackets 
		(({<(({}<>{}[()]))>(){[()](<{}>)}{}<>}{}))  If the copy is the same as any of these, push the difference between the other bracket twice
		<>{}<>  Pop copy
		{  If this character is a start bracket
			{}({}[({})]<>({}))  Check if the next character is the end bracket
			{(<>)(<>)}{}          If not, push a 0 to each stack as buffer
			{}       Pop the top of the input stack, either the start bracket if they matched or the buffer 0
			(<>)     Push 0 to other stack to end check
		}{}>
		{}   Pop the top of the other stack
		         If the character was not an end bracket, pop the copy of check, which is 0
		         If it was, but didn't match the next character, pop the buffer 0
		         If the brackets matched, pop the end bracket and add it to the loop total
	<>}	Repeat with the rest of the input
	<>)	Push the loop total
		If any brackets were matched, the loop total is non zero
}{}
((){<>[()]}) If there is anything left on the stack, push 0 to the other stack, otherwise push 1
Jo King
sumber
3

Brainfuck, 132 byte

+>,[[<->>+>[-]<<-]<[>+>[<+<+>>>+<-]+++++[>--------<-]>[<<+>++++[>-----<-]>[<++++
+[>------<-]>-[<++++[>--------<-]>[,>]]]]<],]<<[>]>.

Diformat:

+>,
[
  [<-> >+>[-]<<-]
  <
  [
    not matching closing bracket
    >+>[<+<+>> >+<-]
    +++++[>--------<-]
    >
    [
      not open paren
      <<+>
      ++++[>-----<-]>
      [
        not open angle bracket
        <+++++[>------<-]>-
        [
          not open square bracket
          <++++[>--------<-]>
          [
            not open brace
            ,>
          ]
        ]
      ]
    ]
    <
  ]
  ,
]
<<[>]
>.

Mengharapkan input tanpa baris baru yang tertinggal. Cetakan \x00untuk false dan \x01true.

Cobalah online.

Pendekatan: Pertahankan tumpukan yang dimulai dengan \x01, dan dorong braket penutup yang sesuai setiap kali braket pembuka ditemukan. Sebelum memeriksa apakah karakter saat ini adalah braket pembuka, pertama periksa apakah karakternya sama dengan braket penutup di bagian atas tumpukan, dan jika demikian lepaskan. Jika bukan braket penutup yang tepat atau braket pembuka, konsumsilah sisa input sambil menggerakkan pointer ke kanan. Pada akhirnya, periksa apakah pointer di sebelah inisial \x01.

Mitch Schwartz
sumber
2

Grime v0.1, 34 byte

M=\(M\)|\[M\]|\{M\}|\<M\>|MM|_
e`M

Mencetak 1untuk pertandingan dan 0tanpa pertandingan. Cobalah online!

Penjelasan

Grime adalah bahasa pencocokan pola 2D saya yang dirancang untuk tantangan ini ; itu juga dapat digunakan untuk mencocokkan string 1D. Ini jawaban pertamaku dengannya. Saya memang memodifikasi Grime hari ini, tetapi hanya untuk mengubah karakter satu elemen sintaks ( `bukan ,), jadi itu tidak mempengaruhi skor saya.

M=                         Define pattern called M that matches:
\(M\)|\[M\]|\{M\}|\<M\>      a smaller M inside matched brackets,
|MM                          or two smaller Ms concatenated,
|_                           or the empty pattern.
e`M                        Match the entire input against M.
Zgarb
sumber
2

Reng v.3.3, 137 byte, tidak bersaing

Coba di sini!

aií0#zl2,q!~1ø
:"]"eq!v:"}"eq!v:">"eq!v:")"eq!v)1z+#z
ve¤[2-2<       <       <     +1<
>]?v$$$zÀ0#z >ðq!vlqv¤l2%[1Ø
   \$2+)1z+#z/   ~n1/

Ada sedikit lebih banyak golf yang harus dilakukan, tetapi setidaknya itu berfungsi. Saya menambahkan perintah ðuntuk melacak tumpukan setelah tantangan ini agar ini menjadi mungkin / mudah. Saya akan menjelaskan ini sedikit, tetapi umumnya melacak semua string berulang dan mencari pengulangan; jika ada pengulangan, maka string tidak dapat direduksi. Jika tidak, string akan direduksi menjadi string / stack kosong, dan akan ditampilkan 1. Kalau tidak, output tidak akan diproduksi.

Conor O'Brien
sumber
2

PowerShell v2 +, 63 62 byte

param($a)for(;$a-ne$b){$a=($b=$a)-replace"\[\]|\(\)|<>|{}"}!$a

Tidak bisa cukup menangkap JavaScript, tetapi saat ini sedang menjajaki non-esolang lainnya.

Pendekatan yang sama seperti jawaban lainnya: loop sederhana yang terus selama kita dapat menghapus salah satu [], ()atau <>(dengan beberapa karakter yang asing karena kita perlu untuk melarikan diri spesial regex). Kami menggunakan $bsebagai penolong di sepanjang jalan untuk mengingat apa loop kami sebelumnya $aditetapkan sebagai. Variabel tidak diinisialisasi adalah $null, jadi saat pertama kali loop ditemukan, $ajelas tidak sama dengan $null.

Pada akhir loop, $akosong atau tidak, dan Boolean-bukan dari string itu adalah Trueatau False.

Contoh

PS C:\Tools\Scripts\golfing> .\are-the-brackets-fully-matched.ps1 "[({})]"
True

PS C:\Tools\Scripts\golfing> .\are-the-brackets-fully-matched.ps1 "[({])}"
False
AdmBorkBork
sumber
2

C, 121 122 114 byte

Dicukur 8 byte berkat @xsot!

a[99],i,k;main(c){for(;read(0,&c,!k);c%7&2?k|=a[i--]^c/9:(a[++i]=c/9))k|=!strchr("()[]{}<>",c);putchar(48+!k*!i);}

Menggunakan tumpukan.

mIllIbyte
sumber
Saya suka c%7&2. Sebenarnya, kamu tidak perlu k. Sebagai gantinya, Anda bisa menambahkan di imana Anda akan memodifikasi kkarena Anda perlu memeriksa apakah pada iakhirnya nol. Sesuatu seperti ini (kode belum teruji): a[99],i;main(c){for(;read(0,&c,1);c%7&2?i+=a[i--]^c/9:(a[++i]=c/9))i+=!strchr("()[]{}<>",c);putchar(48+!i);}.
xsot
@ xsot - Apakah penambahan saya akan bekerja? Kita juga perlu menghindari berlangganan array dengan nilai negatif, jadi kita harus menguji i atau k di for.
mIllIbyte
Ah saya mengerti. Masih ada ruang untuk perbaikan:a[99],i,k;main(c){for(;read(0,&c,!k);c%7&2?k|=a[i--]^c/9:(a[++i]=c/9))k|=!strchr("()[]{}<>",c);putchar(48+!i*!k);}
xsot
@ xsot - Terima kasih! Untuk meringkas penghematan, baca simpan 5 byte, ^ simpan satu dan operan tengah dari operator kondisional disimpan 2. Saya terkejut bahwa operan tengah dari operator kondisional dapat menjadi sebuah tugas. Saya pikir akan ada kesalahan, seperti "missing: before =".
mIllIbyte
@ xsot - Saya mencoba incrementing saya daripada menggunakan k, seperti yang pertama kali Anda sarankan: a[99],i;main(c){for(;read(0,&c,1);c%7&2?i+=a[i]^c/9?1:-1:(a[++i]=c/9))i+=!strchr("()[]{}<>",c);putchar(48+!i);}Tapi ini belum berfungsi untuk input seperti ())), karena "popping" dari stack sebenarnya tidak nol nilai-nilai dalam array.
mIllIbyte
2

Java 7, 156 151 byte

class A{public static void main(String[]a){for(int i=0;i<-1>>>1;++i,a[0]=a[0].replaceAll("<>|\\[]|\\(\\)|\\{}",""));System.out.print(a[0].isEmpty());}}

Saya tidak mengharapkan ini untuk memenangkan penghargaan tetapi saya belum melihat jawaban Java Selain itu, saya suka bersembunyi di sekitar PPCG dan saya akan senang bisa memberikan suara / komentar pada jawaban lain.

Input diberikan sebagai parameter program. Ini mengikuti format yang sama dengan banyak jawaban lain di sini yaitu membentuk preforms pengganti regex dalam satu lingkaran. Awalnya saya memilikinya loop N kali di mana N adalah panjang dari string asli tetapi perulangan ke Integer.MAX_VALUElebih pendek:]. Ini harus ok karena Integer.MAX_VALUEpanjang maksimum a Stringdi Jawa sehingga ada asumsi implisit bahwa panjang input adalah sesuatu yang dapat ditangani oleh Java. Runtime sangat buruk (memakan waktu sekitar 20 menit di lappytop saya) karena loop tetapi saya tidak melihat adanya batasan pada itu.

Menyodok
sumber
2

Haskell , 151 byte

infix 1#
'(':x#y=x#')':y
'<':x#y=x#'>':y
'[':x#y=x#']':y
'{':x#y=x#'}':y
')':x#')':y=x#y
'>':x#'>':y=x#y
']':x#']':y=x#y
'}':x#'}':y=x#y
""#""=1
_#_=0

Cobalah online!

Roman Czyborra
sumber
Beberapa hal: Karena fungsi (#)perlu dipanggil dengan string kosong sebagai argumen kedua, Anda perlu menghitung ke (#"")arah jumlah byte Anda. Juga hanya Truedan Falsedianggap benar / salah, lihat Panduan Aturan Golf .
Laikoni
1
Namun empat baris dengan tanda kurung tutup dapat diganti dengan a:x#b:y|a==b=x#y, membawa byte ke 113: Coba online!
Laikoni
2
109 byte: Cobalah secara online!
Laikoni
2

Python 2.7, 96 byte

def r(s):i=max(map(s.find,['()','[]','{}','<>']));return not len(s)if i<0 else r(s[:i]+s[i+2:])
pengguna5983247
sumber
2
Selamat datang di situs ini!
DJMcMayhem
1

Python 2, 80 byte

def m(s,i=0):exec's=s.replace("[({<])}>"[i%4::4],"");i+=1;'*4*len(s);return"">=s
orlp
sumber
1

Julia, 51 byte

~z=z==(n=replace(z,r"\(\)|\[]|{}|<>",""))?z=="":~n

Paling tidak gila dari beberapa opsi. Tidak mengherankan, meningkatkan kekuatan regex adalah jalur terpendek menuju pencocokan string, tetapi ini hanya berlaku jika pola yang cocok adalah biasa. Mencoba melakukan pola rekursif PCRE berakhir membengkak ukuran kode, baik dengan melihat apakah seluruh string cocok atau dengan jangkar ujungnya dan kemudian membuat konstruksi untuk menentukan tubuh bagian dalam untuk rekursi regex. Tak satu pun dari yang cantik atau kondusif untuk kode golf.

Penjelasan:

~z=                            # Define ~z to be the following:
    z==(                       # If z is equal to                                     
        n=replace(z,           # z with the replacement of 
            r"\(\)|\[]|{}|<>", # adjacent matching brackets ((),[],{}, or <>)
            ""                 # with empty strings
        )                      # (which is assigned to n)
    )?z==""                    # whether z is an empty string
    :~n                        # else ~ applied to the substituted string

Fungsi ini berulang kali menghilangkan pasangan kurung yang berdekatan dari satu-satunya argumen, dan mengembalikan true jika ia dapat menurunkan string kosong dengan cara ini.

eaglgenes101
sumber
1

sed, 39 36 bytes (34 untuk kode, 2 untuk -r)

:a
s/\(\)|\[]|<>|\{}//;ta
/./c0
c1

Cobalah online!

versi sed apa yang tampaknya menjadi pendekatan standar. Membutuhkan ekspresi reguler yang diperluas ( sed -r)

Disimpan 3 byte berkat Sapi dukun

sinar
sumber
Anda dapat menghapus ais :adan tamenyimpan byte
Kritixi Lithos
@KritixiLithos Rupanya itu adalah bug di GNU sed yang dihapus pada 4.3 . Saya mungkin akan menjatuhkan karakter-karakter itu jika entri ini cukup dekat dengan pemimpin sehingga memiliki peluang untuk menang, tetapi karena tidak, saya hanya akan membiarkannya dalam bentuk yang lebih portabel sehingga tidak berhenti bekerja karena lebih banyak sistem ditingkatkan ke 4.3.
Ray
1
Melihat kembali ini, saya yakin Anda bisa drop qdari /./dan drop kawat gigi di sana juga. Cobalah online! Ini karena cara ckerja hange
Kritixi Lithos
@Cowsquack Terima kasih. Diedit.
Ray
0

05AB1E, 9 byte

žu2ôõ:g2Q

Masukan diberikan dalam tanda kutip.

Cobalah online!

Penjelasan:

žu          # Push "()<>[]{}"
  2ô        # Split into pieces of size 2
    õ       # Push empty string
            # Implicit input
      :     # Infinite replacement
       g2Q  # Is length equal to 2?
            # Implicit print
Oliver Ni
sumber
0

Clojure, 153 byte

Lebih lama daripada jawaban C dan Brainfuck: o

(defn f[[s & r]](if s(let[[a b](split-at(.indexOf(reductions + 1(for[c r](get(zipmap[s({\(\)\[\]\{\}\<\>}s)][1 -1])c 0)))0)r)](and(not=()a)(f(butlast a))(f b))))1)

Tidak menggunakan regex, melainkan menggunakan karakter pertama untuk menentukan apa tag penutup dan menemukan indeks pertama di mana braket itu seimbang (jumlah kumulatif adalah nol). Kemudian secara iteratif memeriksa bahwa apa yang ada dalam kurung dan setelah kurung valid.

Harus melihat apakah ada pendekatan yang lebih baik ...

NikoNyrh
sumber
0

Lua , 295 byte

f = false g = string.gsub t=table s={}b=io.read()for c in b:gmatch('.')do if c:find("[%[<{%(]")then s[#s + 1] = g(g(g(g(c,"<",">"),"{","}"),"%[","]"),"%(",")")elseif c:find("[%]>}%)]")then if t.remove(s)~=c then print(f)return end else print(f)return end end if#s>0 then print(f)else print(1)end

Versi Tidak Serigala

f = false
g = string.gsub
t=table
s={} --Define a stack of opening brackets
b=io.read() --get the input
for c in b:gmatch('.') do   --for every character
    if c:find("[%[<{%(]") then
        s[#s + 1] = g(g(g(g(c,"<",">"),"{","}"),"%[","]"),"%(",")") --if the current character is an opening bracket, push the closing bracket onto the stack
    elseif c:find("[%]>}%)]") then
        if t.remove(s)~=c then
            print(f) --if the character is a closing bracket, pop the closing bracket off the stack and test if they match, if not print false
            return
        end
    else 
        print(f) --if the character is not a bracket print false
        return
    end
end
if #s>0 then
    print(f) --if there are still brackets on the stack print false
else
    print(1) --print 1 there are no brackets on the stack
end

Cobalah online!

Alex Allen
sumber
0

Japt v2.0a0 -!, 16 byte

e/\[]|<>|\(\)|{}

Cobalah

Shaggy
sumber
0

R, 298

function(.){s=strsplit;u=paste0;.=s(.,"")[[1]];p=s("><)(}{][","")[[1]];.[!.%in%p]="§";for(i in 1:4*2){.[.==p[i]]=sprintf("S('%s',{",p[i]);.[.==p[i-1]]=sprintf("},'%s');",p[i])};S=function(H,B,T)if(H!=T)stop();r=try(eval(parse(,,u(.,collapse=""))),1);if(inherits(r,"try-error"))FALSE else TRUE}

Pendekatan di sini adalah mengubah urutan menjadi kode R, dan kemudian mencoba mengurai dan mengevaluasinya. Jika itu memberikan kesalahan, maka kembali FALSE.

Tetapi ada masalah kecil ... Aturan R untuk tanda kurung berbeda, jadi <dan >sama sekali bukan tanda kurung, dan tipe lainnya memiliki aturan sendiri. Ini diselesaikan dengan pendekatan revolusioner - fungsi mencicit, yang fungsinya hanya untuk memberi tanda kesalahan jika kepala dan ekornya mencicit dengan cara yang berbeda.

Misalnya, []diubah menjadi S('[', {}, ']'), di mana S didefinisikan sebagai ...

S=function(H,B,T)if(H!=T)stop() 

Karena mencicit kepala dan mencicit ekor, tidak ada kesalahan dilemparkan.

Beberapa contoh lain (bagian kiri adalah urutan kurung dan bagian kanan adalah transformasi menjadi kode R yang valid yang dapat dievaluasi):

[}     -->  S('[', {}, '}')     # squeaks an error
[()]   -->  S('[', {S('(',{},'(')}, "[")
({[]}) -->  S('(',{S('{',{S('[',{},'[');},'{');},'(');

Beberapa urutan kurung lain akan menghasilkan kesalahan parse:

[[)    -->   S('[',{S('[',{},'('); 

Jadi bagian yang tersisa hanya menangkap kesalahan dan mengembalikan SALAH jika ada, dan BENAR jika tidak ada.

Kode yang dapat dibaca manusia:

 sqk <- function(.){
   s=strsplit;u=paste0
   .=s(.,"")[[1]]            # break the argument up into 1-character pieces
   p=s("><)(}{][","")[[1]]   # vector of brackets
   .[!.%in%p]="§"            # replace anything besides brackets by § (--> error)
   for(i in 1:4*2){     
     .[.==p[i]]=sprintf("S('%s',{",p[i])    # '<' -->   S('<',{     ... etc
     .[.==p[i-1]]=sprintf("},'%s');",p[i])  # '>' -->   },'<');     ... etc  
   }
   S=function(H,B,T)if(H!=T)stop()          # define the working horse
   r=try(eval(parse(,,u(.,collapse=""))),1) # evaluate the sequence
   if(inherits(r,"try-error"))FALSE else TRUE   # any errors?
   }

Menerapkannya pada kasus sampel:

truthy<-readLines(textConnection("()
[](){}<>
(((())))
({[<>]})
[{()<>()}[]]
[([]{})<{[()<()>]}()>{}]"))
falsy<-readLines(textConnection("(
}
(<2)>
(()()foobar)
[({}<>)>
(((()))"))
> sapply(truthy,sqk)
                      ()                 [](){}<>                 (((()))) 
                    TRUE                     TRUE                     TRUE 
                ({[<>]})             [{()<>()}[]] [([]{})<{[()<()>]}()>{}] 
                    TRUE                     TRUE                     TRUE 
> sapply(falsy,sqk)
           (            }        (<2)> (()()foobar)     [({}<>)>      (((())) 
       FALSE        FALSE        FALSE        FALSE        FALSE        FALSE 
lebatsnok
sumber