# Prefix Tree Traversal

Write a program that takes in (via stdin or command line) a string with the recursive form

PREFIX[SUFFIXES]


where

• PREFIX may be any string of lowercase letters (a-z), including the empty string, and
• SUFFIXES may be any sequence of strings with the recursive form PREFIX[SUFFIXES] concatenated together, including the empty sequence.

Generate a list of lowercase lettered strings from the input by recursively evaluating the list of strings in each of the suffixes and appending them to the prefix. Output to stdout the strings in this list in any order, one per line (plus an optional trailing newline).

### Example

If the input is

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


then the prefix is cat and and the suffixes are s[up[][]], [], ch[e[r[]s[]]], and a[maran[]comb[]pult[[]ing[]]]. Each suffix has its own prefix and suffixes in turn.

The output would be these 9 words in any order

catsup
cats
cat
catcher
catches
catamaran
catacomb
catapult
catapulting


because the input encodes this tree

and each of the 9 output words can be formed by traversing the tree from root to leaf.

### Notes

• Remember that the prefix may be the empty string, so something like

[donut[][]cruller[]]


is valid input whose output would be (in any order)

donut

cruller


where the empty line is for the empty string that the second suffix matches.

• The suffix sequence can also be empty, so the trivial input case

[]


has a single empty line as its output:



• You may assume that the input will only produce unique output words.
• e.g. hat[s[]ter[]s[]] would be invalid input because hats is encoded twice.
• Similarly, [[][]] is invalid because the empty string is encoded twice.
• You may not assume that the input is as short or compressed as possible.
• e.g. the 'e' node in the main example above could be combined with the 'ch' node, but that's doesn't mean the input is invalid.
• Similarly, [[[[[]]]]] is valid, despite only encoding the empty string in a sub-optimal way.
• Instead of a program you may write a function that takes the input string as an argument and prints the output normally or returns it as a string or list.

The shortest code in bytes wins.

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


### Example

Try it: http://ideone.com/NW0CNB

### Description

The program gets the input from stdin and outputs the result to stdout.

It traverses the tree keeping the current branch in a stack. There's also a different stack, called weights which keeps track of the number of children of each node. This is needed in order to determine if a node is really a leaf, or it had children in the past.

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


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  The function is t (for 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 "[[[[[]]]]]" [""]  • Your code is 124 bytes, not 125 :) – Cristian Lupascu Aug 16 '15 at 10:58 • i think the pattern (a,(_:t)) can be (a,_:t) instead – proud haskeller Aug 20 '15 at 22:52 # Java, 206 bytes Defines a function that accepts a string as an argument and returns a list of strings. For an added bonus it returns strings in the same order as the question does. 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;}  ### Example usage: 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;} }  ### Expanded: 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; }  I will add an explanation tomorrow. # Python, 212 chars 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,  I was hoping to get under 200, but still I am pretty happy with this. # Javascript ES6, 142 bytes 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))  ## Q: 70 Bytes f:{,/'$({(z_x),y}\[();{\$x@&~x="]"}'w;-b])@-1+&0<b:(+/"]"=)'w:"["\:x}


defines a function f that accepts a string and return a list of strings (words)

As a lambda (anonymous function) we drop the first 2 chars f:, so length is 68 Bytes

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


("donut";"";"cruller")

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


,""

Notes

,"" indicates a list of strings that contains only has an empty string

Symbols are atomic. Push/pop a symbol on the stack is a simple operation not affected by the lenght of the symbol (see explanation)

Explanation

Q is a cousin of APL (kx.com)

Pseudocode:

• Splits string (arg x) at "[" char. Result (list of strings) in w
• Counts "]" chars in each elem. of w. Result in b
• Modifies each item in w to filter out character "]" and converts each string to a symbol
• Generates a logical sequence (bitmap) to mark items >0 in b
• Iterates over partial results with a stack: if item marked we must drop one of more symbols (according to value in b). Always append actual symbol to stack
• After iterating we have all intermediate states of stack. We select previously marked states
• finally for each result we convert symbols to strings and concatenate them

# 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''
`
• If the downvoter would leave a comment saying what is wrong with this, that would be appreciated. – Οurous Aug 21 '15 at 22:35