Awalan Pohon Traversal

13

Tulis program yang menerima (melalui stdin atau baris perintah) string dengan bentuk rekursif

PREFIX[SUFFIXES]

dimana

  • PREFIX mungkin sembarang string huruf kecil (az), termasuk string kosong, dan
  • SUFFIXESdapat berupa urutan string apa pun dengan bentuk rekursif yang PREFIX[SUFFIXES]disatukan, termasuk urutan kosong.

Buat daftar string huruf kecil dari input dengan mengevaluasi secara berulang daftar string di masing-masing sufiks dan menambahkannya ke awalan. Output ke stdout string dalam daftar ini dalam urutan apa pun, satu per baris (ditambah satu baris tambahan opsional).

Contoh

Jika inputnya

cat[s[up[][]][]ch[e[r[]s[]]]a[maran[]comb[]pult[[]ing[]]]]

maka awalan adalah catdan dan akhiran yang s[up[][]], [], ch[e[r[]s[]]], dana[maran[]comb[]pult[[]ing[]]] . Setiap sufiks memiliki awalan dan sufiks pada gilirannya.

Outputnya adalah 9 kata ini dalam urutan apa pun

catsup
cats
cat
catcher
catches
catamaran
catacomb
catapult
catapulting

karena input mengkodekan pohon ini

diagram pohon

dan masing-masing dari 9 kata keluaran dapat dibentuk dengan melintasi pohon dari akar ke daun.

Catatan

  • Ingat bahwa awalan mungkin berupa string kosong, jadi kira-kira seperti itu

    [donut[][]cruller[]]
    

    adalah input yang valid yang hasilnya akan (dalam urutan apa pun)

    donut
    
    cruller
    

    di mana baris kosong adalah untuk string kosong yang cocok dengan sufiks kedua.

  • Urutan akhiran juga bisa kosong, jadi kasus input sepele

    []
    

    memiliki satu baris kosong sebagai hasilnya:

    
    
  • Anda dapat mengasumsikan bahwa input hanya akan menghasilkan kata-kata keluaran unik.
    • mis. hat[s[]ter[]s[]]akan menjadi input yang tidak valid karena hatsdikodekan dua kali.
    • Demikian pula, [[][]]tidak valid karena string kosong dikodekan dua kali.
  • Anda tidak boleh berasumsi bahwa inputnya sesingkat atau sekompresi mungkin.
    • misal 'e'simpul dalam contoh utama di atas dapat dikombinasikan dengan 'ch'simpul tersebut, tetapi itu tidak berarti bahwa input tidak valid.
    • Demikian pula, [[[[[]]]]]ini valid, meskipun hanya pengkodean string kosong dengan cara yang tidak optimal.
  • Alih-alih program Anda dapat menulis fungsi yang mengambil string input sebagai argumen dan mencetak output secara normal atau mengembalikannya sebagai string atau daftar.

Kode terpendek dalam byte menang.

Hobi Calvin
sumber

Jawaban:

2

Ruby, 119 115

t=['']
l=[0]
gets.chars{|c|c<?]?t<<''&&(l<<0)[-2]+=1:c<?^?(x=l.pop;t.pop==''&&(puts t*''if x<1;t[-1]='')):t[-1]<<c}

Contoh

Cobalah: http://ideone.com/NW0CNB

Deskripsi

Program mendapatkan input dari stdin dan mengeluarkan hasilnya ke stdout.

Itu melintasi pohon menjaga cabang saat ini di tumpukan. Ada juga tumpukan yang berbeda, yang disebutweights yang melacak jumlah anak dari setiap node. Ini diperlukan untuk menentukan apakah sebuah simpul benar-benar daun, atau memiliki anak di masa lalu.

Program yang dapat dibaca:

stack = ['']
weights = [0]

gets.chars do |c|
  case c
  when '['
    weights[-1] += 1
    stack << ''
    weights << 0
  when ']'
    last_weight = weights.pop

    if stack.pop == ''
      puts stack.join if last_weight < 1
      stack[-1] = ''
    end
  else
    stack[-1] << c
  end
end
Cristian Lupascu
sumber
6

Haskell, 125 byte

t=tail.p
p=g.break(=='[')
g(a,(_:t))=(:)&(map(a++).z)$t#[]
z[]=[""];z x=x
(']':u)#a=u:a
s#a=(#)&(a++)$p s
(g&f)(x:y)=g x$f y

Fungsi ini t(untuk traversal):

λ: t "cat[s[up[][]][]ch[e[r[]s[]]]a[maran[]comb[]pult[[]ing[]]]]"
["catsup","cats","cat","catcher","catches","catamaran","catacomb","catapult","catapulting"]
λ: t "[donut[][]cruller[]]"
["donut","","cruller"]
λ: t "[[[[[]]]]]"
[""]
MtnViewMark
sumber
Kode Anda adalah 124 byte, bukan 125 :)
Cristian Lupascu
saya pikir polanya (a,(_:t))bisa (a,_:t)sebaliknya
haskeller bangga
2

Java, 206 byte

Menentukan fungsi yang menerima string sebagai argumen dan mengembalikan daftar string. Untuk bonus tambahan, ia mengembalikan string dalam urutan yang sama seperti pertanyaannya.

int c,i;List a(String a){String b=a.substring(c,c=a.indexOf(91,c));List d=new ArrayList();for(;a.charAt(++c)!=93;)d.addAll(a(a));if(d.isEmpty())d.add("");for(i=0;i<d.size();)d.set(i,b+d.get(i++));return d;}

Contoh penggunaan:

class A{
    public static void main(String[] args){
        System.out.println(new A.a("cat[s[up[][]][]ch[e[r[]s[]]]a[maran[]comb[]pult[[]ing[]]]]"));
    }

    int c,i;List a(String a){String b=a.substring(c,c=a.indexOf(91,c));List d=new ArrayList();for(;a.charAt(++c)!=93;)d.addAll(a(a));if(d.isEmpty())d.add("");for(i=0;i<d.size();)d.set(i,b+d.get(i++));return d;}
}

Diperluas:

int c, i;
List a(String a){
    String b = a.substring(c, c = a.indexOf(91, c));
    List d = new ArrayList();
    for(; a.charAt(++c) != 93 ;)
        d.addAll(a(a));
    if (d.isEmpty())
        d.add("");
    for (i = 0; i < d.size();)
        d.set(i, b + d.get(i++));
    return d;
}

Saya akan menambahkan penjelasan besok.

TheNumberOne
sumber
0

Python, 212 karakter

def p(t,f="",o="",d=0):
 if[]==t:return
 b=[""]
 for c in t:d+=c=="[";b[-1]+=c;d-=c=="]";b+=[""]*(d==0)*(c=="]")
 for r in b[:-1]:i=r.index("[");w,s=f+r[:i],r[i:][1:-1];p(s,w);o+= ["",w+"\n"][""==s]
  if o:print o,

Saya berharap untuk di bawah 200, tetapi saya masih cukup senang dengan ini.

Loovjo
sumber
0

Javascript ES6, 142 byte

s=>(o=[],x=_=>s[0]==']'?s=s.slice(1):0,(g=d=>{while(s&&!x())[o[d],s]=s.split(/\[(.*)/).concat``,x()?console.log(o.join``):g(d+1),o.pop()})(0))
Dendrobium
sumber
0

T: 70 Bytes

f:{,/'$({(z_x),y}\[();{`$x@&~x="]"}'w;-b])@-1+&0<b:(+/"]"=)'w:"["\:x}

mendefinisikan fungsi f yang menerima string dan mengembalikan daftar string (kata-kata)

Sebagai lambda (fungsi anonim) kita menjatuhkan 2 karakter pertama f :, jadi panjangnya adalah 68 Bytes

Uji

f "cat[s[up[][]][]ch[e[r[]s[]]]a[maran[]comb[]pult[[]ing[]]]]"

("catsup"; "cats"; "cat"; "catcher"; "catches"; "catamaran"; "catacomb"; "catapult"; "catapulting")

f "[donut[][]cruller[]]"

("donat"; ""; "cruller")

f "[[[[[]]]]]"

, ""

Catatan

, "" menunjukkan daftar string yang hanya berisi string kosong

Simbol adalah atom. Push / pop simbol pada stack adalah operasi sederhana yang tidak terpengaruh oleh panjang simbol (lihat penjelasan)

Penjelasan

Q adalah sepupu APL (kx.com)

Kodesemu:

  • Pisahkan string (arg x) di karakter "[". Hasil (daftar string) di w
  • Menghitung karakter "]" di setiap elem. dari w. Menghasilkan b
  • Mengubah setiap item dalam w untuk menyaring karakter "]" dan mengubah setiap string menjadi simbol
  • Menghasilkan urutan logis (bitmap) untuk menandai item> 0 dalam b
  • Iterasikan lebih dari hasil parsial dengan tumpukan: jika item ditandai, kita harus menjatuhkan salah satu simbol lainnya (sesuai dengan nilai dalam b). Selalu tambahkan simbol yang sebenarnya untuk ditumpuk
  • Setelah iterasi, kita memiliki semua status intermediate stack. Kami memilih negara yang sebelumnya ditandai
  • akhirnya untuk setiap hasil kami mengonversi simbol ke string dan menyatukannya
J. Sendra
sumber
-1

Cobra - 181

def f(s='')as String*
    for m in RegularExpressions.Regex.matches(s,r'(\w*)\[((?:(?<B>\[)|\w|(?<-B>]))*)](?(B)(?!))'),for r in.f('[(u=m.groups)[2]]'),yield'[u[1]]'+r
    if''==s,yield''
Suram
sumber
Jika downvoter akan meninggalkan komentar mengatakan apa yang salah dengan ini, itu akan dihargai.
Οurous