1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
export default function expand(s: string): string[] {    if (s.includes("{")) {        const m = parse(s);
        if (typeof m === "string") return [m];        return evaluate(m).sort();    } else {        return [s];    }}export type Expression = AddExpression | MultExpression;
export interface AddExpression {    type: "AddExpression";    children: (Expression | string)[];}export interface MultExpression {    type: "MultExpression";    children: (Expression | string)[];}
export function parse(s: string): Expression | string {    const m = s.match(/\,|\{|\}|[a-z]+/g) ?? [];    if (!m || !m.length) return { type: "AddExpression", children: [] };
    let i = 0;
    function dfs(): Expression | string {        const a: (string | Expression)[] = [];
        while (i < m.length) {            const value = m[i];            if (value === "{") {                i++;                a.push(dfs());            } else if (value === "}") {                i++;                break;            } else {                a.push(value);                i++;            }        }
        if (a.length == 1) {            return a[0];        }        return a.includes(",")            ? splitAdd(a)            : { type: "MultExpression", children: a };    }    const r = dfs();    return r;}
function splitAdd(a: (string | Expression)[]): Expression | string {    const e: AddExpression = { type: "AddExpression", children: [] };    if (a.length === 1) return a[0];    const index = a.indexOf(",");    if (index < 0) return { type: "MultExpression", children: a };
    if (index === 1) {        e.children.push(a[0]);    } else {        e.children.push({            type: "MultExpression",            children: a.slice(0, index),        });    }    e.children.push(splitAdd(a.slice(index + 1)));    if (e.children.length == 1) {        return e.children[0];    }    return e;}export function evaluate(m: Expression | string): string[] {    if (typeof m === "string") return [m];
    if (m.type === "MultExpression") {        return m.children.reduce((p: string[], c): string[] => {            const left = p;            const right = typeof c === "string" ? [c] : evaluate(c);            if (p.length === 0) return right;            return left.map((v) => right.map((r) => v + r)).flat();        }, [] as string[]);    } else {        return m.children.map(evaluate).flat();    }}