Prefix Tree Traversal

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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.

Answer 5

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

Answer 6

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

Answer 7

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