Как перечислить шаблоны

Question

Как сгенерировать все шаблоны в следующем правиле:

# в качестве разделителя, {и} означает выбор строки между {и}.

Например:

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

Вывод должен быть:

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

Answer 1

Сначала проанализируйте входную строку в дереве, используя любой стандартный алгоритм синтаксического анализа. Выражение в форме дерева для вашего примера выше будет что-то вроде (C = concatenate, S = select)

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

Теперь реализуйте процедуру, которая рекурсивно оценивает это дерево (или выражение, как вы его можете назвать) и возвращает набор строк в результате вычисления любого подвыражения. Тогда оценка идет так:

 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"

(кстати, вам не хватает bcef и bceg из вашего примера)

Правила оценки:

S (X, Y): вычислить X и Y и взять объединение множеств

C (X, Y): вычислить X и Y и сформировать все объединения, взяв одну строку из набора X и одну строку из набора Y