De-Parenthesizing a String

25

Diberikan string yang dikurung dengan benar sebagai input, mengeluarkan daftar semua substring kosong dalam tanda kurung yang cocok (atau di luar semua tanda kurung), dengan tanda kurung bersarang dihapus. Setiap substring harus urutan karakter dalam tanda kurung yang sama persis. Substring harus terdaftar dalam urutan kedalaman, dan substring dengan kedalaman yang sama harus terdaftar dalam urutan mereka terjadi dalam string. Asumsikan input selalu dengan tanda kurung benar.

Anda dapat berasumsi bahwa input hanya berisi huruf ASCII dan tanda kurung kecil.

Jawaban Anda harus berupa fungsi yang, ketika diberikan string, mengembalikan daftar string.

Contoh:

                   'a(b)c(d)e' -> ['ace', 'b', 'd']
                   'a(b(c)d)e' -> ['ae', 'bd', 'c']
                  'a((((b))))' -> ['a', 'b']
                        'a()b' -> ['ab']
                            '' -> []
                           'a' -> ['a']
          '(((a(b)c(d)e)f)g)h' -> ['h', 'g', 'f', 'ace', 'b', 'd']
'ab(c(((d)ef()g)h()(i)j)kl)()' -> ['ab', 'ckl', 'hj', 'efg', 'i', 'd']

Bytes paling sedikit menang.

redstonerodent
sumber
Apakah 'i'dan 'd'dalam urutan yang benar dalam test case terakhir?
PurkkaKoodari
@ Pietu1998 ikurang bersarang dibandingkan d.
feersum
@feersum Oh, benar.
PurkkaKoodari
1
Maukah Anda mengizinkan jenis pengajuan standar lainnya juga, khususnya program lengkap? Tidak semua bahasa memiliki konsep fungsi. Untuk konsensus standar, lihat meta.codegolf.stackexchange.com/a/2422/8478 dan meta.codegolf.stackexchange.com/questions/2447/… .
Martin Ender
2
@redstonerodent Kata-kata yang cenderung saya gunakan adalah "Anda dapat menulis sebuah program atau fungsi, mengambil input melalui STDIN (atau alternatif terdekat), argumen baris perintah atau argumen fungsi dan menghasilkan hasilnya melalui STDOUT (atau alternatif terdekat), nilai pengembalian fungsi atau parameter fungsi (keluar). " dan dalam kasus Anda "Outputnya mungkin dalam format daftar datar yang nyaman, tidak ambigu."
Martin Ender

Jawaban:

11

JavaScript ES6, 91 93 104 133 148

Sunting2 2 byte disimpan thx user81655

Edit Menggunakan lebih banyak string dan lebih sedikit array

Tes menjalankan cuplikan di bawah ini di peramban yang mendukung EcmaScript 6

f=s=>[...s].map(c=>l+=c<')'||-(o[l]=(o[l]||'')+c,c<'a'),o=[],l=0)&&(o+'').match(/\w+/g)||[]

// Less golfed

u=s=>{
  o=[]; l=0;
  [...s].map(c=>{
    if (c>'(') // letters or close bracket
      o[l]=(o[l]||'')+c, // add letter or close bracket to current level string
      l-=c<'a' // if close bracket, decrement level
    else
      ++l // open bracket, increment level
  })
  o = o+'' // collapse array to comma separated string
  return o.match(/\w+/g)||[] // fetch non empty strings into an array
}

// TEST
console.log=x=>O.innerHTML+=x+'\n'

;[ 'a(b)c(d)e'                    // ['ace', 'b', 'd']
 , 'a(b(c)d)e'                    // ['ae', 'bd', 'c']
 , 'a((((b))))'                   // ['a', 'b']
 , 'a()b'                         // ['ab']
 , ''                             // []
 , 'a'                            // ['a']
 , '(((a(b)c(d)e)f)g)h'           // ['h', 'g', 'f', 'ace', 'b', 'd']
 , 'ab(c(((d)ef()g)h()(i)j)kl)()' // ['ab', 'ckl', 'hj', 'efg', 'i', 'd']
].forEach(t=>console.log(t +" -> " + f(t)))
<pre id=O></pre>

edc65
sumber
Simpan 2 byte dengan c=>l+=c<')'||-(o[l]=(o[l]||'')+c,c<'a'),.
user81655
@ user81655 bagus, terima kasih
edc65
8

Julia, 117 86 83 byte

v->(while v!=(v=replace(v,r"(\(((?>\w|(?1))*)\))(.*)",s"\g<3> \g<2>"))end;split(v))

Ini solusi regex.

Tidak Disatukan:

function f(v)
  w=""
  while v!=w
    w=v
    v=replace(v,r"(\(((?>\w|(?1))*)\))(.*)",s"\g<3> \g<2>"))
  end
  split(v)
end

r"(\(((?>\w|(?1))*)\))(.*)"adalah (?1)regex rekursif ( grup rekursi 1) yang akan cocok dengan kurung seimbang terluar pertama (yang tidak mengandung kurung tidak seimbang / terbalik), dengan grup kedua berisi segala sesuatu di dalam kurung (tidak termasuk kurung itu sendiri) dan grup ketiga yang mengandung semuanya setelah tanda kurung (sampai akhir string).

replace(v,r"...",s"\g<3> \g<2>")kemudian akan memindahkan grup kedua ke akhir string (setelah spasi, untuk bertindak sebagai pembatas), dengan tanda kurung yang relevan dihapus. Dengan mengulangi hingga v == w, dipastikan bahwa penggantian diulang sampai tidak ada tanda kurung yang tersisa. Karena kecocokan dipindahkan ke akhir, dan kemudian kecocokan berikutnya berlaku untuk tanda kurung pertama, hasilnya adalah string yang dipecah dalam urutan kedalaman.

Kemudian splitmengembalikan semua komponen non-spasi spasi dari string dalam bentuk array string (yang tidak memiliki spasi putih).

Catatan yang w=""digunakan dalam kode ungolfed untuk memastikan bahwa loop sementara berjalan setidaknya sekali (kecuali jika string input kosong, tentu saja), dan tidak diperlukan dalam bentuk golf.

Terima kasih kepada Martin Büttner untuk bantuan dengan menghemat 3 byte.

Glen O
sumber
Rapi, saya tiba di solusi yang sama secara independen di Retina. Itu 44 byte di sana, tetapi karena berdiri solusi program penuh tidak diperbolehkan. : /
Martin Ender
Anda dapat menyimpan tiga byte dengan menggunakan \walih-alih [^()].
Martin Ender
@ MartinBüttner - terima kasih. Aku benar-benar mempertimbangkan hal itu, tetapi aku khawatir bahwa aku mengabaikan sesuatu dan itu akan gagal pada beberapa kasus tepi. Jika Anda mengatakan itu baik-baik saja, maka tidak apa-apa.
Glen O
6

Python, 147 byte

def f(s):
 d=0;r=[['']for c in s]
 for c in s:
  if c=='(':d+=1;r[d]+=['']
  elif c==')':d-=1
  else:r[d][-1]+=c
 return[i for i in sum(r,[])if i]

Tes unit:

assert f('a(b)c(d)e') == ['ace', 'b', 'd']
assert f('a(b(c)d)e') == ['ae', 'bd', 'c']
assert f('a((((b))))') == ['a', 'b']
assert f('a()b') == ['ab']
assert f('') == []
assert f('a') == ['a']
assert f('(((a(b)c(d)e)f)g)h') == ['h', 'g', 'f', 'ace', 'b', 'd']
assert f('ab(c(((d)ef()g)h()(i)j)kl)()') == ['ab', 'ckl', 'hj', 'efg', 'i', 'd']

Saya suka teka-teki ini; ini sangat lucu!

Quuxplusone
sumber
4

Pyth, 32 byte

fTscR)uX0.<GJ-FqLH`()@[Hdk)Jzmkz

Suite uji

Berbasis longgar dari pendekatan @ Quuxplusone. Buat daftar karakter yang dipisahkan oleh spasi di setiap kedalaman, lalu pisahkan dan saring kelompok yang kosong. Daftar kerja diputar untuk menjaga daftar kedalaman saat ini di depan setiap saat.

isaacg
sumber
4

Retina , 44 41 byte

+`\(((\w|(\()|(?<-3>.))*).(.*)
$4 $1
S_` 

Jalankan dengan -sbendera. Perhatikan spasi di akhir baris terakhir.

Saya datang dengan solusi ini secara independen dari Glen O tetapi ternyata identik. Idenya adalah untuk mencocokkan pasangan kurung pertama, menghapusnya, dan menyisipkan isinya di akhir output (berulang kali). Karena kurangnya rekursi .NET di regex, saya harus menggunakan grup penyeimbang yang empat byte lebih lama.

Jika Anda tidak memahami regex pertama, izinkan saya merujuk Anda ke jawaban SO saya tentang menyeimbangkan grup . Karena input dijamin dengan tanda kurung yang benar, kita dapat menyimpan dua byte dengan mencocokkan )dengan .alih - alih \). Maka kita cukup mencocokkan sisa string dengan (.*). $4 $1pertama menulis kembali kata sisa string (menghilangkan kedua kurung dan isinya), dan kemudian isi kurung setelah spasi. The +`memberitahu Retina untuk mengulangi langkah ini sampai string berhenti berubah (yang hanya terjadi setelah semua tanda kurung telah dihapus).

Tanda kurung kosong akan menghasilkan dua spasi berturut-turut, jadi akhirnya kami membagi seluruh string pada spasi ( S`mengaktifkan mode split dan regex adalah spasi tunggal). The _pilihan memberitahu Retina ke bagian kosong omit dari perpecahan, jadi kami tidak termasuk hasil kosong dalam output.

Martin Ender
sumber
3

Common Lisp, 160

(lambda(x)(labels((g(l)(cons(#1=format()"~(~{~A~}~)"(#2=remove-if'listp l))(mapcan #'g(#2#'atom l)))))(remove""(g(read-from-string(#1#()"(~A)"x))):test'equal))))

Ini bisa menjadi empat byte lebih sedikit jika konversi case tidak diperlukan. Idenya adalah menambahkan tanda kurung kiri dan kanan ke setiap sisi dari string input, memperlakukannya sebagai daftar, menulis elemen tingkat atas daftar ke string, dan kemudian memproses sublists dengan cara yang sama.

Joshua Taylor
sumber
2

Haskell, 114 112 111 byte

')'%(h:i:t)=("":i):t++[h]
'('%l=last l:init l
c%((h:i):t)=((c:h):i):t
g x=[a|a<-id=<<foldr(%)(x>>[[""]])x,a>""]

Contoh penggunaan: g "ab(c(((d)ef()g)h()(i)j)kl)()"-> ["ab","ckl","hj","efg","i","d"].

Saya akan mundur melalui string input. Struktur data antara adalah daftar daftar string. Daftar luar adalah per level dan daftar dalam adalah per grup di dalam level, misalnya [["ab"],["ckl"],["hj"],["efg","i"],["d"]](catatan: daftar sebenarnya memiliki banyak string kosong di antaranya). Semuanya dimulai dengan sejumlah string kosong yang sama dengan panjang input - lebih dari cukup, tetapi daftar kosong tetap disaring. Daftar luar berputar pada (/ )atau menambahkan karakter ke elemen depan. )juga memulai grup baru.

Sunting: @Zgarb telah menemukan byte untuk disimpan.

nimi
sumber
1

Sed, 90 byte

:
s/^(\w*)\((.*)\n?(.*)/\1\n\3_\2/M
s/(\n\w*_)(\w*)\)(.*)/\3\1\2/M
t
s/[_\n]+/,/g
s/,$//

Menggunakan regex yang diperluas ( -rbendera), dihitung dengan +1 byte. Juga, ini menggunakan Ekstensi GNU ( Mbendera pada sperintah).

Penggunaan sampel:

$ echo 'ab(c(((d)ef()g)h()(i)j)kl)()' | sed -r -f deparenthesize.sed
ab,ckl,hj,efg,i,d

Penjelasan: Karena sed tidak mendukung hal-hal seperti regex rekursif, pekerjaan manual diperlukan. Ekspresi dibagi menjadi beberapa garis, masing-masing mewakili tingkat kedalaman bersarang. Ekspresi individu pada kedalaman yang sama (dan karenanya pada baris yang sama) dipisahkan oleh a _. Script bekerja melalui string input braket satu per satu Input yang tersisa selalu disimpan di ujung jalur yang sesuai dengan level peneluran saat ini.

matz
sumber
0

Python, 161 byte

Inilah yang saya buat, solusi python fungsional satu baris:

p=lambda s:filter(None,sum([''.join([s[i]for i in range(len(s))if s[:i+1].count('(')-s[:i+1].count(')')==d and s[i]!=')']).split('(')for d in range(len(s))],[]))

Tantangan ini terinspirasi oleh https://github.com/samcoppini/Definition-book , yang menghasilkan string panjang dengan kata yang didefinisikan dalam tanda kurung. Saya ingin menulis kode yang akan memberi saya setiap kalimat, dengan kurung dihapus. Solusi fungsional terlalu lambat untuk menjadi efektif pada string panjang, tetapi solusi imperatif (seperti solusi @ Quuxplusone) jauh lebih cepat.

redstonerodent
sumber