Problem Statement

Brace expansion is a type of parameter expansion made popular by Unix shells, where it allows users to specify multiple similar string parameters without having to type them all out. E.g. the parameter enable_{audio,video} would be interpreted as if both enable_audio and enable_video had been specified.

Write a function that can perform brace expansion on any input string, according to the following specification. Demonstrate how it would be used, and that it passes the four test cases given below. In the input string, balanced pairs of braces containing comma-separated substrings (details below) represent alternations that specify multiple alternatives which are to appear at that position in the output. In general, one can imagine the information conveyed by the input string as a tree of nested alternations interspersed with literal substrings, as shown in the middle part of the following diagram: This tree can in turn be transformed into the intended list of output strings by, colloquially speaking, determining all the possible ways to walk through it from left to right while only descending into one branch of each alternation one comes across (see the right part of the diagram). When implementing it, one can of course combine the parsing and expansion into a single algorithm, but this specification discusses them separately for the sake of clarity. Expansion of alternations can be more rigorously described by these rules: Parsing the input string involves some additional complexity to deal with escaped characters and "incomplete" brace pairs: For every possible input string, your implementation should produce exactly the output which this specification mandates. Please comply with this even when it's inconvenient, to ensure that all implementations are comparable. However, none of the above should be interpreted as instructions (or even recommendations) for how to implement it. Try to come up with a solution that is idiomatic in your programming language. (See #Perl for a reference implementation.)

Let's start with the solution:

var getGroup // forward declaration

var getItem = Fn.new { |s, depth|
    var out = [""]
    while (s != "") {
        var c = s[0]
        if (depth > 0 && (c == "," || c == "}")) return [out, s]
        var cont = false
        if (c == "{") {
            var x = getGroup.call(s[1..-1], depth+1)
            if (!x[0].isEmpty) {
                var t = []
                for (a in out) {
                    for (b in x[0]) {
                        t.add(a + b)
                    }
                }
                out = t
                s = x[1]
                cont = true
            }
        }
        if (!cont) {
            if (c == "\\" && s.count > 1) {
                c = c + s[1]
                s = s[1..-1]
            }
            out = out.map { |a| a + c }.toList
            s = s[1..-1]
        }
    }
    return [out, s]
}

getGroup = Fn.new { |s, depth|
    var out = []
    var comma = false
    while (s != "") {
        var t = getItem.call(s, depth)
        var g = t[0]
        s = t[1]
        if (s == "") break
        out.addAll(g)
        if (s[0] == "}") {
            if (comma) return [out, s[1..-1]]
            return [out.map { |a| "{" + a + "}" }.toList, s[1..-1]]
        }
        if (s[0] == ",") {
            comma = true
            s = s[1..-1]
       }
    }
    return [[], ""]
}

var inputs = [
     "~/{Downloads,Pictures}/*.{jpg,gif,png}",
    "It{{em,alic}iz,erat}e{d,}, please.",
    "{,{,gotta have{ ,\\, again\\, }}more }cowbell!",
    "{}} some }{,{\\\\{ edge, edge} \\,}{ cases, {here} \\\\\\\\\\}"
]
for (input in inputs) {
    System.print(input)
    for (s in getItem.call(input, 0)[0]) System.print("    " + s)
    System.print()
}