Prefix Tree Traversal
Haskell, 125 bytes
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 "[[[[[]]]]]"
[""]
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.
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.
The readable 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