Napisz program, który pobiera (za pomocą standardowego wiersza poleceń lub wiersza poleceń) ciąg znaków w formie rekurencyjnej

PREFIX[SUFFIXES]

gdzie

• PREFIX może być dowolnym ciągiem małych liter (az), w tym pustym ciągiem, oraz
• SUFFIXESmoże być dowolną sekwencją ciągów z PREFIX[SUFFIXES]połączoną rekurencyjną formą , w tym pustą sekwencją.

Wygeneruj listę ciągów liter pisanych małymi literami na podstawie danych wejściowych, rekurencyjnie oceniając listę ciągów znaków w każdym z przyrostków i dołączając je do przedrostka. Wyprowadza na standardowe ciągi na tej liście w dowolnej kolejności, po jednym w wierszu (plus opcjonalny końcowy znak nowej linii).

Przykład

Jeśli dane wejściowe to

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

to jest prefiks cati i przyrostki są s[up[][]], [], ch[e[r[]s[]]], i a[maran[]comb[]pult[[]ing[]]]. Każdy sufiks ma swój własny prefiks i sufiksy z kolei.

Wynikiem będą te 9 słów w dowolnej kolejności

catsup
cats
cat
catcher
catches
catamaran
catacomb
catapult
catapulting

ponieważ dane wejściowe kodują to drzewo

a każde z 9 słów wyjściowych można utworzyć, przechodząc przez drzewo od korzenia do liścia.

Notatki

• Pamiętaj, że przedrostek może być pustym ciągiem, więc coś w rodzaju

  [donut[][]cruller[]]
  

  jest poprawnym wejściem, którego wyjściem byłoby (w dowolnej kolejności)

  donut
  
  cruller
  

  gdzie pusta linia jest pustym ciągiem, do którego pasuje drugi sufiks.

• Sekwencja sufiksów może być również pusta, więc trywialny przypadek wejściowy

  []
  

  ma jeden pusty wiersz jako wynik:

• Możesz założyć, że dane wejściowe wygenerują tylko unikalne słowa wyjściowe.
  • np. hat[s[]ter[]s[]]byłoby niepoprawne wejście, ponieważ hatsjest kodowane dwukrotnie.
  • Podobnie [[][]]jest niepoprawny, ponieważ pusty ciąg jest kodowany dwukrotnie.
• Być może nie przyjąć, że wejście jest tak krótki, jak to możliwe lub sprężone.
  • np. 'e'węzeł w powyższym głównym przykładzie można połączyć z 'ch'węzłem, ale to nie znaczy, że dane wejściowe są nieprawidłowe.
  • Podobnie [[[[[]]]]]jest poprawny, pomimo zakodowania pustego łańcucha tylko w sposób nieoptymalny.
• Zamiast programu możesz napisać funkcję, która przyjmuje ciąg wejściowy jako argument i drukuje dane wyjściowe normalnie lub zwraca je jako ciąg znaków lub listę.

Najkrótszy kod w bajtach wygrywa.

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}

Przykład

Wypróbuj: http://ideone.com/NW0CNB

Opis

Program pobiera dane wejściowe ze standardowego wejścia i przekazuje wynik na standardowe wyjście.

Przechodzi przez drzewo, utrzymując bieżącą gałąź w stosie. Istnieje również inny stos, zwany, weightsktóry śledzi liczbę dzieci każdego węzła. Jest to potrzebne, aby ustalić, czy węzeł jest tak naprawdę liściem, czy miał dzieci w przeszłości.

Czytelny program:

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

Haskell, 125 bajtów

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

Funkcja ta t(dla przejścia):

λ: 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 "[[[[[]]]]]"
[""]

Java, 206 bajtów

Definiuje funkcję, która akceptuje ciąg jako argument i zwraca listę ciągów. Dla dodatkowej premii zwraca ciągi w tej samej kolejności, co pytanie.

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;}

Przykładowe użycie:

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;}
}

Rozszerzony:

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;
}

Jutro dodam wyjaśnienie.

Python, 212 znaków

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,

Miałem nadzieję, że będę miał mniej niż 200 lat, ale nadal jestem z tego całkiem zadowolony.

JavaScript ES6, 142 bajty

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))

P: 70 bajtów

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

definiuje funkcję f, która akceptuje ciąg i zwraca listę ciągów (słów)

Jako lambda (funkcja anonimowa) upuszczamy pierwsze 2 znaki f :, więc długość wynosi 68 bajtów

Test

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[]]"

(„pączek”; „”; „cruller”)

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

, „”

Notatki

, „” oznacza listę ciągów zawierających tylko ciąg pusty

Symbole są atomowe. Wciśnij / pop symbol na stosie to prosta operacja, na którą nie ma wpływu długość symbolu (patrz wyjaśnienie)

Wyjaśnienie

Q jest kuzynem APL (kx.com)

Pseudo kod:

• Dzieli ciąg (arg x) na znak „[”. Wynik (lista ciągów) w w
• Liczy znaki „]” w każdym elemie. z w. Wynik w b
• Zmienia każdy element w, aby odfiltrować znak „]” i konwertuje każdy ciąg znaków na symbol
• Generuje logiczną sekwencję (bitmapę) do oznaczenia pozycji> 0 w b
• Iteruje ponad wynikami cząstkowymi ze stosem: jeśli element jest zaznaczony, musimy upuścić jeden lub więcej symboli (zgodnie z wartością w b). Zawsze dołączaj rzeczywisty symbol do stosu
• Po iteracji mamy wszystkie pośrednie stany stosu. Wybieramy wcześniej zaznaczone stany
• wreszcie dla każdego wyniku konwertujemy symbole na ciągi i łączymy je

Kobra - 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''