前缀树遍历

Question

编写一个程序(通过stdin或命令行)接收带有递归形式的字符串。

PREFIX[SUFFIXES]

哪里

• PREFIX可以是任何小写字母( and )字符串，包括空字符串，以及
• SUFFIXES可以是任何具有递归形式PREFIX[SUFFIXES]连接在一起的字符串序列，包括空序列。

通过递归计算每个后缀中的字符串列表并将它们附加到前缀中，从输入中生成小写字母字符串列表。输出以任意顺序输出此列表中的字符串，每行一个字符串(加上可选的尾随换行符)。

如果输入是cat[s[upundefined][]ch[e[r[]s[]]]a[maran[]comb[]pult[[]ing[]]]]，那么前缀是cat，后缀是s[up[][]]、[]、ch[e[r[]s[]]]和a[maran[]comb[]pult[[]ing[]]]。每个后缀都有自己的前缀和后缀。输出的是这9个单词，按任意顺序排列，猫捕手捕获双体船，弹射器，弹射器，因为输入编码了这棵树。

而这9个输出词中的每一个都可以从根到叶遍历树形成。

Notes

• 请记住，前缀可能是空字符串，因此类似于[ donut undefinedcruller[]]这样的输入是有效的输入，其输出将是(按任何顺序)甜甜圈规则器，其中空行为第二个后缀匹配的空字符串。
• 后缀序列也可以是空的，因此平凡的输入情况[]只有一个空行作为输出：
• 您可能会假设输入只会产生唯一的输出字。
  • 例如，hat[s[]ter[]s[]]将是无效输入，因为hats被编码了两次。
  • 同样，[[][]]是无效的，因为空字符串被编码了两次。

• 您可能不会假设输入是尽可能短的或压缩的。
  • 例如，上面主要示例中的'e'节点可以与'ch'节点组合，但这并不意味着输入无效。
  • 同样，[[[[[]]]]]是有效的，尽管只以次优的方式编码空字符串。

• 您可以编写一个函数，将输入字符串作为参数并正常打印输出，或者将其作为字符串或列表返回，而不是编写程序。

以字节为单位的最短代码获胜.

Answer 1

Java，206个字节

定义接受字符串作为参数并返回字符串列表的函数。作为额外的奖励，它以与问题相同的顺序返回字符串。

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

示例用法：

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

扩展：

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

我明天再加一个解释。

Answer 2

Python，212个字符

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,

我本来希望能在200岁以下，但我还是对此很满意。

Answer 3

Javascript ES6,142个字节

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