How to enum the patterns

How to generate all patterns in the following rule:

# as a separator, { and } means choose a string between { and }.

For example:

开发者_如何学JAVA

Input: a string
{a # b} c {d # e {f # g}}

Output should be:

a c d
b c d
a c e f
a c e g

---

First, parse the input string into a tree using any standard parsing algorithm. The tree-form expression for your example above would be something like (C = concatenate, S = select)

 C(S(a,b),C(c,S(d,C(e,S(f,g)))))

Now then implement a procedure that recursively evaluates this tree (or expression, as you might call it) and returns a set of strings as the result of evaluation any subexpression. Then the evaluation goes like this

 S(f,g) == "f", "g"
 C(e,S(f,g)) == "ef", "eg"
 S(d,C(e,S(f,g))) = "d", "ef", "eg"
 C(c,S(d,C(e,S(f,g)))) = "cd", "cef", "ceg"
 S(a,b) = "a", "b"
 C(S(a,b),C(c,S(d,C(e,S(f,g))))) = "acd", "bcd", "acef", "bcef", "aceg", "bceg"

(by the way, you are missing bcef and bceg from your example)

The evaluation rules are:

S(X,Y) : evaluate X and Y and take the union of the sets

C(X,Y) : evaluate X and Y and form all concatenations from taking one string from set X and one string from set Y