Brace expansion

From Rosetta Code
Task
Brace expansion
You are encouraged to solve this task according to the task description, using any language you may know.

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.


Task

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.

Specification

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:

It{{em,alic}iz,erat}e{d,}
parse 
―――――▶
It




em


alic
iz


erat
e


d


expand 
―――――▶
Itemized
Itemize
Italicized
Italicize
Iterated
Iterate
input string alternation tree output (list of strings)

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:

a


2


1
b


X


Y
X
c
a2bXc
a2bYc
a2bXc
a1bXc
a1bYc
a1bXc
  • An alternation causes the list of alternatives that will be produced by its parent branch to be increased 𝑛-fold, each copy featuring one of the 𝑛 alternatives produced by the alternation's child branches, in turn, at that position.
  • This means that multiple alternations inside the same branch are cumulative  (i.e. the complete list of alternatives produced by a branch is the string-concatenating "Cartesian product" of its parts).
  • All alternatives (even duplicate and empty ones) are preserved, and they are ordered like the examples demonstrate  (i.e. "lexicographically" with regard to the alternations).
  • The alternatives produced by the root branch constitute the final output.

Parsing the input string involves some additional complexity to deal with escaped characters and "incomplete" brace pairs:

a\\{\\\{b,c\,d}
a\\


\\\{b


c\,d
{a,b{c{,{d}}e}f
{a,b{c




{d}
e}f
  • An unescaped backslash which precedes another character, escapes that character (to force it to be treated as literal). The backslashes are passed along to the output unchanged.
  • Balanced brace pairs are identified by, conceptually, going through the string from left to right and associating each unescaped closing brace that is encountered with the nearest still unassociated unescaped opening brace to its left (if any). Furthermore, each unescaped comma is associated with the innermost brace pair that contains it (if any). With that in mind:
    • Each brace pair that has at least one comma associated with it, forms an alternation (whose branches are the brace pair's contents split at its commas). The associated brace and comma characters themselves do not become part of the output.
    • Brace characters from pairs without any associated comma, as well as unassociated brace and comma characters, as well as all characters that are not covered by the preceding rules, are instead treated as literals.

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

Test Cases
Input
(single string)
Ouput
(list/array of strings)

~/{Downloads,Pictures}/*.{jpg,gif,png}

~/Downloads/*.jpg
~/Downloads/*.gif
~/Downloads/*.png
~/Pictures/*.jpg
~/Pictures/*.gif
~/Pictures/*.png

It{{em,alic}iz,erat}e{d,}, please.

Itemized, please.
Itemize, please.
Italicized, please.
Italicize, please.
Iterated, please.
Iterate, please.

{,{,gotta have{ ,\, again\, }}more }cowbell!

cowbell!
more cowbell!
gotta have more cowbell!
gotta have\, again\, more cowbell!

{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}

{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}
{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}


Other tasks related to string operations:
Metrics
Counting
Remove/replace
Anagrams/Derangements/shuffling
Find/Search/Determine
Formatting
Song lyrics/poems/Mad Libs/phrases
Tokenize
Sequences




11l

Translation of: Python
F getitem(=s, depth = 0)
   V out = [‘’]
   L s != ‘’
      V c = String(s[0])
      I depth & (c == ‘,’ | c == ‘}’)
         R (out, s)
      I c == ‘{’
         V x = getgroup(s[1..], depth + 1)
         I !x[0].empty
            out = multiloop(out, x[0], (a, b) -> a‘’b)
            s = x[1]
            L.continue
      I c == "\\" & s.len > 1
         (s, c) = (s[1..], c‘’s[1])
      out = out.map(a -> a‘’@c)
      s = s[1..]
   R (out, s)

F getgroup(=s, depth)
   [String] out
   V comma = 0B
   L s != ‘’
      V gs = getitem(s, depth)
      s = gs[1]
      I s == ‘’
         L.break
      out [+]= gs[0]

      I s[0] == ‘}’
         I comma
            R (out, s[1..])
         R (out.map(a -> ‘{’a‘}’), s[1..])

      I s[0] == ‘,’
         (comma, s) = (1B, s[1..])
   R ([‘’] * 0, ‘’)

L(s) |‘~/{Downloads,Pictures}/*.{jpg,gif,png}
       It{{em,alic}iz,erat}e{d,}, please.
       {,{,gotta have{ ,\, again\, }}more }cowbell!
       {}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}’.split("\n")
   print(([s] [+] getitem(s)[0]).join("\n\t")"\n")
Output:
~/{Downloads,Pictures}/*.{jpg,gif,png}
        ~/Downloads/*.jpg
        ~/Downloads/*.gif
        ~/Downloads/*.png
        ~/Pictures/*.jpg
        ~/Pictures/*.gif
        ~/Pictures/*.png
...
{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}
        {}} some }{,{\\ edge \,}{ cases, {here} \\\\\}
        {}} some }{,{\\ edge \,}{ cases, {here} \\\\\}

AppleScript

This may seem like a cheat, but it is a legitimate and obvious way to tackle the problem with AppleScript in the unlikely event that the need should arise. It adjusts the escape levels in the input text, feeds it as a shell script to macOS's sh shell, and lets it handle the expansion.

use AppleScript version "2.4" -- OS X 10.10 (Yosemite) or later
use framework "Foundation"
use scripting additions

on braceExpansion(textForExpansion)
    -- Massage the text to pass to a shell script: -
    -- Single-quote it to render everything in it initially immune from brace and file-system expansion.
    -- Include a return at the end to get a new line at the end of each eventual expansion.
    set textForExpansion to quoted form of (textForExpansion & return)
    -- Switch to ASObjC text for a couple of regex substitutions.
    set textForExpansion to current application's class "NSMutableString"'s stringWithString:(textForExpansion)
    -- Increase the escape level of every instance of /two/ backslashes (represented by eight in the
    -- AppleScript string for the search regex) and isolate each result inside its own quote marks.
    tell textForExpansion to replaceOccurrencesOfString:("\\\\\\\\") withString:("''$0$0''") ¬
        options:(current application's NSRegularExpressionSearch) range:({0, its |length|()})
    -- UNquote every run of braces and/or commas not now immediately preceded by a backslash.
    tell textForExpansion to replaceOccurrencesOfString:("(?<!\\\\)[{,}]++") withString:("'$0'") ¬
        options:(current application's NSRegularExpressionSearch) range:({0, its |length|()})
    
    -- Pass the massaged text to a shell script to be 'echo'-ed. Since a space will still be inserted
    -- between each expansion, also delete the space after each return in the result.
    -- Return a list of the individual expansions.
    return (do shell script ("echo " & textForExpansion & " | sed -E 's/([[:cntrl:]]) /\\1/g'"))'s paragraphs
end braceExpansion

-- Test:
set output to braceExpansion("~/{Downloads,Pictures}/*.{jpg,gif,png}") & ¬
    braceExpansion("It{{em,alic}iz,erat}e{d,}, please.") & ¬
    braceExpansion("{,{,gotta have{ ,\\, again\\, }}more }cowbell!") & ¬
    braceExpansion("{}} some }{,{\\\\{ edge, edge} \\,}{ cases, {here} \\\\\\\\\\}")
set astid to AppleScript's text item delimiters
set AppleScript's text item delimiters to linefeed
set output to output as text
set AppleScript's text item delimiters to astid

log output -- To see the result without the backslash-escaping.
Output:
(*~/Downloads/*.jpg
~/Downloads/*.gif
~/Downloads/*.png
~/Pictures/*.jpg
~/Pictures/*.gif
~/Pictures/*.png
Itemized, please.
Itemize, please.
Italicized, please.
Italicize, please.
Iterated, please.
Iterate, please.
cowbell!
more cowbell!
gotta have more cowbell!
gotta have\, again\, more cowbell!
{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}
{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}*)

AutoHotkey

;This one is a lot more simpler than the rest
BraceExp(string, del:="`n") {
	Loop, Parse, string
		if (A_LoopField = "{")
			break
		else
		substring .= A_LoopField
	substr := SubStr(string, InStr(string, "{")+1, InStr(string, "}")-InStr(string, "{")-1)
	Loop, Parse, substr, `,
		toreturn .= substring . A_LoopField . del
	return toreturn
}

Msgbox, % BraceExp("enable_{video,audio}")
Msgbox, % BraceExp("apple {bush,tree}")
Msgbox, % BraceExp("h{i,ello}")
Msgbox, % BraceExp("rosetta{code,stone}")
Output:
enable_video
enable_audio

apple bush
apple tree

hi
hello

rosettacode
rosettastone

C

Handles only properly formed input.

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BUFFER_SIZE 128

typedef unsigned char character;
typedef character *string;

typedef struct node_t node;
struct node_t {
    enum tag_t {
        NODE_LEAF,
        NODE_TREE,
        NODE_SEQ,
    } tag;

    union {
        string str;
        node *root;
    } data;

    node *next;
};

node *allocate_node(enum tag_t tag) {
    node *n = malloc(sizeof(node));
    if (n == NULL) {
        fprintf(stderr, "Failed to allocate node for tag: %d\n", tag);
        exit(1);
    }
    n->tag = tag;
    n->next = NULL;
    return n;
}

node *make_leaf(string str) {
    node *n = allocate_node(NODE_LEAF);
    n->data.str = str;
    return n;
}

node *make_tree() {
    node *n = allocate_node(NODE_TREE);
    n->data.root = NULL;
    return n;
}

node *make_seq() {
    node *n = allocate_node(NODE_SEQ);
    n->data.root = NULL;
    return n;
}

void deallocate_node(node *n) {
    if (n == NULL) {
        return;
    }

    deallocate_node(n->next);
    n->next = NULL;

    if (n->tag == NODE_LEAF) {
        free(n->data.str);
        n->data.str = NULL;
    } else if (n->tag == NODE_TREE || n->tag == NODE_SEQ) {
        deallocate_node(n->data.root);
        n->data.root = NULL;
    } else {
        fprintf(stderr, "Cannot deallocate node with tag: %d\n", n->tag);
        exit(1);
    }

    free(n);
}

void append(node *root, node *elem) {
    if (root == NULL) {
        fprintf(stderr, "Cannot append to uninitialized node.");
        exit(1);
    }
    if (elem == NULL) {
        return;
    }

    if (root->tag == NODE_SEQ || root->tag == NODE_TREE) {
        if (root->data.root == NULL) {
            root->data.root = elem;
        } else {
            node *it = root->data.root;
            while (it->next != NULL) {
                it = it->next;
            }
            it->next = elem;
        }
    } else {
        fprintf(stderr, "Cannot append to node with tag: %d\n", root->tag);
        exit(1);
    }
}

size_t count(node *n) {
    if (n == NULL) {
        return 0;
    }

    if (n->tag == NODE_LEAF) {
        return 1;
    }
    if (n->tag == NODE_TREE) {
        size_t sum = 0;
        node *it = n->data.root;
        while (it != NULL) {
            sum += count(it);
            it = it->next;
        }
        return sum;
    }
    if (n->tag == NODE_SEQ) {
        size_t prod = 1;
        node *it = n->data.root;
        while (it != NULL) {
            prod *= count(it);
            it = it->next;
        }
        return prod;
    }

    fprintf(stderr, "Cannot count node with tag: %d\n", n->tag);
    exit(1);
}

void expand(node *n, size_t pos) {
    if (n == NULL) {
        return;
    }

    if (n->tag == NODE_LEAF) {
        printf(n->data.str);
    } else if (n->tag == NODE_TREE) {
        node *it = n->data.root;
        while (true) {
            size_t cnt = count(it);
            if (pos < cnt) {
                expand(it, pos);
                break;
            }
            pos -= cnt;
            it = it->next;
        }
    } else if (n->tag == NODE_SEQ) {
        size_t prod = pos;
        node *it = n->data.root;
        while (it != NULL) {
            size_t cnt = count(it);

            size_t rem = prod % cnt;
            expand(it, rem);

            it = it->next;
        }
    } else {
        fprintf(stderr, "Cannot expand node with tag: %d\n", n->tag);
        exit(1);
    }
}

string allocate_string(string src) {
    size_t len = strlen(src);
    string out = calloc(len + 1, sizeof(character));
    if (out == NULL) {
        fprintf(stderr, "Failed to allocate a copy of the string.");
        exit(1);
    }
    strcpy(out, src);
    return out;
}

node *parse_seq(string input, size_t *pos);

node *parse_tree(string input, size_t *pos) {
    node *root = make_tree();

    character buffer[BUFFER_SIZE] = { 0 };
    size_t bufpos = 0;
    size_t depth = 0;
    bool asSeq = false;
    bool allow = false;

    while (input[*pos] != 0) {
        character c = input[(*pos)++];
        if (c == '\\') {
            c = input[(*pos)++];
            if (c == 0) {
                break;
            }
            buffer[bufpos++] = '\\';
            buffer[bufpos++] = c;
            buffer[bufpos] = 0;
        } else if (c == '{') {
            buffer[bufpos++] = c;
            buffer[bufpos] = 0;
            asSeq = true;
            depth++;
        } else if (c == '}') {
            if (depth-- > 0) {
                buffer[bufpos++] = c;
                buffer[bufpos] = 0;
            } else {
                if (asSeq) {
                    size_t new_pos = 0;
                    node *seq = parse_seq(buffer, &new_pos);
                    append(root, seq);
                } else {
                    append(root, make_leaf(allocate_string(buffer)));
                }
                break;
            }
        } else if (c == ',') {
            if (depth == 0) {
                if (asSeq) {
                    size_t new_pos = 0;
                    node *seq = parse_seq(buffer, &new_pos);
                    append(root, seq);
                    bufpos = 0;
                    buffer[bufpos] = 0;
                    asSeq = false;
                } else {
                    append(root, make_leaf(allocate_string(buffer)));
                    bufpos = 0;
                    buffer[bufpos] = 0;
                }
            } else {
                buffer[bufpos++] = c;
                buffer[bufpos] = 0;
            }
        } else {
            buffer[bufpos++] = c;
            buffer[bufpos] = 0;
        }
    }

    return root;
}

node *parse_seq(string input, size_t *pos) {
    node *root = make_seq();

    character buffer[BUFFER_SIZE] = { 0 };
    size_t bufpos = 0;

    while (input[*pos] != 0) {
        character c = input[(*pos)++];
        if (c == '\\') {
            c = input[(*pos)++];
            if (c == 0) {
                break;
            }
            buffer[bufpos++] = c;
            buffer[bufpos] = 0;
        } else if (c == '{') {
            node *tree = parse_tree(input, pos);
            if (bufpos > 0) {
                append(root, make_leaf(allocate_string(buffer)));
                bufpos = 0;
                buffer[bufpos] = 0;
            }
            append(root, tree);
        } else {
            buffer[bufpos++] = c;
            buffer[bufpos] = 0;
        }
    }

    if (bufpos > 0) {
        append(root, make_leaf(allocate_string(buffer)));
        bufpos = 0;
        buffer[bufpos] = 0;
    }

    return root;
}

void test(string input) {
    size_t pos = 0;
    node *n = parse_seq(input, &pos);
    size_t cnt = count(n);
    size_t i;

    printf("Pattern: %s\n", input);

    for (i = 0; i < cnt; i++) {
        expand(n, i);
        printf("\n");
    }
    printf("\n");

    deallocate_node(n);
}

int main() {
    test("~/{Downloads,Pictures}/*.{jpg,gif,png}");
    test("It{{em,alic}iz,erat}e{d,}, please.");
    test("{,{,gotta have{ ,\\, again\\, }}more }cowbell!");

    //not sure how to parse this one
    //test("{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}");

    return 0;
}
Output:
Pattern: ~/{Downloads,Pictures}/*.{jpg,gif,png}
~/Downloads/*.jpg
~/Pictures/*.gif
~/Downloads/*.png
~/Pictures/*.jpg
~/Downloads/*.gif
~/Pictures/*.png

Pattern: It{{em,alic}iz,erat}e{d,}, please.
Itemized, please.
Italicize, please.
Iterated, please.
Itemize, please.
Italicized, please.
Iterate, please.

Pattern: {,{,gotta have{ ,\, again\, }}more }cowbell!
cowbell!
more cowbell!
gotta have more cowbell!
gotta have\, again\, more cowbell!

C#

This approach turns the string into a tree structure, with Tokens that are either text, a concatenation or an alteration.

Works with: C sharp version 8
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using static System.Linq.Enumerable;

public static class BraceExpansion
{
    enum TokenType { OpenBrace, CloseBrace, Separator, Text, Alternate, Concat }
    const char L = '{', R = '}', S = ',';
    
    public static void Main() {
        string[] input = {
            "It{{em,alic}iz,erat}e{d,}, please.",
            "~/{Downloads,Pictures}/*.{jpg,gif,png}",
            @"{,{,gotta have{ ,\, again\, }}more }cowbell!",
            @"{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}"
        };
        foreach (string text in input) Expand(text);
    }
    
    static void Expand(string input) {
        Token token = Tokenize(input);
        foreach (string value in token) Console.WriteLine(value);
        Console.WriteLine();
    }
    
    static Token Tokenize(string input) {
        var tokens = new List<Token>();
        var buffer = new StringBuilder();
        bool escaping = false;
        int level = 0;
        
        foreach (char c in input) {
            (escaping, level, tokens, buffer) = c switch {
                _ when escaping => (false, level, tokens, buffer.Append(c)),
                '\\' => (true, level, tokens, buffer.Append(c)),
                L => (escaping, level + 1,
                    tokens.With(buffer.Flush()).With(new Token(c.ToString(), TokenType.OpenBrace)), buffer),
                S when level > 0 => (escaping, level,
                    tokens.With(buffer.Flush()).With(new Token(c.ToString(), TokenType.Separator)), buffer),
                R when level > 0 => (escaping, level - 1,
                    tokens.With(buffer.Flush()).With(new Token(c.ToString(), TokenType.CloseBrace)).Merge(), buffer),
                _ => (escaping, level, tokens, buffer.Append(c))
            };
        }
        if (buffer.Length > 0) tokens.Add(buffer.Flush());
        for (int i = 0; i < tokens.Count; i++) {
            if (tokens[i].Type == TokenType.OpenBrace || tokens[i].Type == TokenType.Separator) {
                tokens[i] = tokens[i].Value; //Change to text
            }
        }
        return new Token(tokens, TokenType.Concat);
    }
    
    static List<Token> Merge(this List<Token> list) {
        int separators = 0;
        int last = list.Count - 1;
        for (int i = list.Count - 3; i >= 0; i--) {
            if (list[i].Type == TokenType.Separator) {
                separators++;
                Concat(list, i + 1, last);
                list.RemoveAt(i);
                last = i;
            } else if (list[i].Type == TokenType.OpenBrace) {
                Concat(list, i + 1, last);
                if (separators > 0) {
                    list[i] = new Token(list.Range((i+1)..^1), TokenType.Alternate);
                    list.RemoveRange(i+1, list.Count - i - 1);
                } else {
                    list[i] = L.ToString();
                    list[^1] = R.ToString();
                    Concat(list, i, list.Count);
                }
                break;
            }
        }
        return list;
    }
    
    static void Concat(List<Token> list, int s, int e) {
        for (int i = e - 2; i >= s; i--) {
            (Token a, Token b) = (list[i], list[i+1]);
            switch (a.Type, b.Type) {
                case (TokenType.Text, TokenType.Text):
                    list[i] = a.Value + b.Value;
                    list.RemoveAt(i+1);
                    break;
                case (TokenType.Concat, TokenType.Concat):
                    a.SubTokens.AddRange(b.SubTokens);
                    list.RemoveAt(i+1);
                    break;
                case (TokenType.Concat, TokenType.Text) when b.Value == "":
                    list.RemoveAt(i+1);
                    break;
                case (TokenType.Text, TokenType.Concat) when a.Value == "":
                    list.RemoveAt(i);
                    break;
                default:
                    list[i] = new Token(new [] { a, b }, TokenType.Concat);
                    list.RemoveAt(i+1);
                    break;
            }
        }
    }
    
    private struct Token : IEnumerable<string>
    {
        private List<Token>? _subTokens;
        
        public string Value { get; }
        public TokenType Type { get; }
        public List<Token> SubTokens => _subTokens ??= new List<Token>();
        
        public Token(string value, TokenType type) => (Value, Type, _subTokens) = (value, type, null);
        public Token(IEnumerable<Token> subTokens, TokenType type) => (Value, Type, _subTokens) = ("", type, subTokens.ToList());
        
        public static implicit operator Token(string value) => new Token(value, TokenType.Text);
        
        public IEnumerator<string> GetEnumerator() => (Type switch
        {
            TokenType.Concat => SubTokens.Select(t => t.AsEnumerable()).CartesianProduct().Select(p => string.Join("", p)),
            TokenType.Alternate => from t in SubTokens from s in t select s,
            _ => Repeat(Value, 1)
        }).GetEnumerator();
        
        IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();        
    }
    
    //===Extension methods===
    static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences) {
        IEnumerable<IEnumerable<T>> emptyProduct = new[] { Empty<T>() };
        return sequences.Aggregate(
            emptyProduct,
            (accumulator, sequence) =>
                from acc in accumulator
                from item in sequence
                select acc.Concat(new [] { item }));
    }
    
    static List<Token> With(this List<Token> list, Token token) {
        list.Add(token);
        return list;
    }
    
    static IEnumerable<Token> Range(this List<Token> list, Range range) {
        int start = range.Start.GetOffset(list.Count);
        int end = range.End.GetOffset(list.Count);
        for (int i = start; i < end; i++) yield return list[i];
    }
    
    static string Flush(this StringBuilder builder) {
        string result = builder.ToString();
        builder.Clear();
        return result;
    }
}
Translation of: Python
public static class BraceExpansion
{
    const char L = '{', R = '}', S = ',';
    //Main method same as above

    static void Expand(string input) {
        foreach (string s in GetItem(input).Item1) Console.WriteLine(s);
        Console.WriteLine();
    }

    static (List<string>, string) GetItem(string s, int depth = 0) {
        var output = new List<string> {""};
        while (s.Length > 0) {
            string c = s[..1];
            if (depth > 0 && (c[0] == S || c[0] == R)) return (output, s);
            if (c[0] == L) {
                var x = GetGroup(s[1..], depth+1);
                if (!(x.Item1 is null)) {
                    (output, s) = ((from a in output from b in x.Item1 select a + b).ToList(), x.Item2);
                    continue;
                }
            }
            if (c[0] == '\\' && s.Length > 1) {
                c += s[1];
                s = s[1..];
            }
            (output, s) = ((from a in output select a + c).ToList(), s[1..]);
        }
        return (output, s);
    }

    static (List<string>?, string) GetGroup(string s, int depth) {
        var output = new List<string>();
        bool comma = false;
        while (s.Length > 0) {
            List<string>? g;
            (g, s) = GetItem(s, depth);
            if (s.Length == 0) break;
            output.AddRange(g);

            if (s[0] == R) {
                if (comma) return (output, s[1..]);
                return ((from a in output select L + a + R).ToList(), s[1..]);
            }
            if (s[0] == S) (comma, s) = (true, s[1..]);
        }
        return (null, "");
    }
}
Output:
Itemized, please.
Itemize, please.
Italicized, please.
Italicize, please.
Iterated, please.
Iterate, please.

~/Downloads/*.jpg
~/Downloads/*.gif
~/Downloads/*.png
~/Pictures/*.jpg
~/Pictures/*.gif
~/Pictures/*.png

cowbell!
more cowbell!
gotta have more cowbell!
gotta have\, again\, more cowbell!

{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}
{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}

C++

C++11 solution:

#include <iostream>
#include <iterator>
#include <string>
#include <utility>
#include <vector>

namespace detail {

template <typename ForwardIterator>
class tokenizer
{
	
	ForwardIterator _tbegin, _tend, _end;
	
public:
	
	tokenizer(ForwardIterator begin, ForwardIterator end)
		: _tbegin(begin), _tend(begin), _end(end)
	{ }
	
	template <typename Lambda>
	bool next(Lambda istoken)
	{
		if (_tbegin == _end) {
			return false;
		}
		_tbegin = _tend;
		for (; _tend != _end && !istoken(*_tend); ++_tend) {
			if (*_tend == '\\' && std::next(_tend) != _end) {
				++_tend;
			}
		}
		if (_tend == _tbegin) {
			_tend++;
		}
		return _tbegin != _end;
	}
	
	ForwardIterator begin() const { return _tbegin; }
	ForwardIterator end()   const { return _tend; }
	bool operator==(char c) { return *_tbegin == c; }
	
};

template <typename List>
void append_all(List & lista, const List & listb)
{
	if (listb.size() == 1) {
		for (auto & a : lista) {
			a += listb.back();
		}
	} else {
		List tmp;
		for (auto & a : lista) {
			for (auto & b : listb) {
				tmp.push_back(a + b);
			}
		}
		lista = std::move(tmp);
	}
}

template <typename String, typename List, typename Tokenizer>
List expand(Tokenizer & token)
{
	
	std::vector<List> alts{ { String() } };
	
	while (token.next([](char c) { return c == '{' || c == ',' || c == '}'; })) {
		
		if (token == '{') {
			append_all(alts.back(), expand<String, List>(token));
		} else if (token == ',') {
			alts.push_back({ String() });
		} else if (token == '}') {
			if (alts.size() == 1) {
				for (auto & a : alts.back()) {
					a = '{' + a + '}';
				}
				return alts.back();
			} else {
				for (std::size_t i = 1; i < alts.size(); i++) {
					alts.front().insert(alts.front().end(),
						std::make_move_iterator(std::begin(alts[i])),
						std::make_move_iterator(std::end(alts[i])));
				}
				return std::move(alts.front());
			}
		} else {
			for (auto & a : alts.back()) {
				a.append(token.begin(), token.end());
			}
		}
		
	}
	
	List result{ String{ '{' } };
	append_all(result, alts.front());
	for (std::size_t i = 1; i < alts.size(); i++) {
		for (auto & a : result) {
			a += ',';
		}
		append_all(result, alts[i]);
	}
	return result;
}

} // namespace detail

template <
	typename ForwardIterator,
	typename String = std::basic_string<
		typename std::iterator_traits<ForwardIterator>::value_type
	>,
	typename List = std::vector<String>
>
List expand(ForwardIterator begin, ForwardIterator end)
{
	detail::tokenizer<ForwardIterator> token(begin, end);
	List list{ String() };
	while (token.next([](char c) { return c == '{'; })) {
		if (token == '{') {
			detail::append_all(list, detail::expand<String, List>(token));
		} else {
			for (auto & a : list) {
				a.append(token.begin(), token.end());
			}
		}
	}
	return list;
}

template <
	typename Range,
	typename String = std::basic_string<typename Range::value_type>,
	typename List = std::vector<String>
>
List expand(const Range & range)
{
	using Iterator = typename Range::const_iterator;
	return expand<Iterator, String, List>(std::begin(range), std::end(range));
}

int main()
{
	
	for (std::string string : {
		R"(~/{Downloads,Pictures}/*.{jpg,gif,png})",
		R"(It{{em,alic}iz,erat}e{d,}, please.)",
		R"({,{,gotta have{ ,\, again\, }}more }cowbell!)",
		R"({}} some {\\{edge,edgy} }{ cases, here\\\})",
		R"(a{b{1,2}c)",
		R"(a{1,2}b}c)",
		R"(a{1,{2},3}b)",
		R"(a{b{1,2}c{}})",
		R"(more{ darn{ cowbell,},})",
		R"(ab{c,d\,e{f,g\h},i\,j{k,l\,m}n,o\,p}qr)",
		R"({a,{\,b}c)",
		R"(a{b,{{c}})",
		R"({a{\}b,c}d)",
		R"({a,b{{1,2}e}f)",
		R"({}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\})",
		R"({{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{)",
	}) {
		std::cout << string << '\n';
		for (auto expansion : expand(string)) {
			std::cout << "    " << expansion << '\n';
		}
		std::cout << '\n';
	}
	
	return 0;
}

Common Lisp

(defstruct alternation
  (alternatives nil :type list))

(defun alternatives-end-positions (string start)
  (assert (char= (char string start) #\{))
  (loop with level = 0
        with end-positions
        with escapep and commap
        for index from start below (length string)
        for c = (char string index)
        do (cond (escapep
                  (setf escapep nil))
                 ((char= c #\\)
                  (setf escapep t))
                 ((char= c #\{)
                  (incf level))
                 ((char= c #\})
                  (decf level)
                  (when (zerop level)
                    (push index end-positions)
                    (loop-finish)))
                 ((and (char= c #\,) (= level 1))
                  (setf commap t)
                  (push index end-positions)))
        finally (return (and (zerop level) commap (nreverse end-positions)))))

(defun parse-alternation (string start)
  (loop with end-positions = (alternatives-end-positions string start)
        for %start = (1+ start) then (1+ %end)
        for %end in end-positions
        collect (parse string :start %start :end %end) into alternatives
        finally (return (and alternatives
                             (values (make-alternation :alternatives alternatives) (1+ %end))))))

(defun parse (string &key (start 0) (end (length string)))
  (loop with result and escapep
        for index = start then next
        while (< index end)
        for c = (char string index)
        for next = (1+ index)
        do (cond (escapep
                  (push c result)
                  (setf escapep nil))
                 ((char= c #\\)
                  (push c result)
                  (setf escapep t))
                 ((char= c #\{)
                  (multiple-value-bind (alternation next-index)
                      (parse-alternation string index)
                    (cond (alternation
                           (push alternation result)
                           (setf next next-index))
                          (t
                           (push c result)))))
                 (t
                  (push c result)))
        finally (return (nreverse result))))

(defun traverse-alternation (alternation)
  (mapcan #'traverse (alternation-alternatives alternation)))

(defun traverse (parsed)
  (let ((results (list nil)))
    (dolist (element parsed results)
      (etypecase element
        (character
         (setf results (loop for r in results
                             collect (nconc r (list element)))))
        (alternation
         (setf results (loop for r in results
                             nconc (loop for ar in (traverse-alternation element)
                                         collect (append r ar)))))))))

(defun expand (string)
  (loop for result in (traverse (parse string))
        collect (coerce result 'string)))

(defun main ()
  (dolist (input '("~/{Downloads,Pictures}/*.{jpg,gif,png}"
                   "It{{em,alic}iz,erat}e{d,}, please."
                   "{,{,gotta have{ ,\\, again\\, }}more }cowbell!"
                   "{}} some }{,{\\\\{ edge, edge} \\,}{ cases, {here} \\\\\\\\\\}"))
    (write-line input)
    (dolist (output (expand input))
      (format t "    ~A~%" output))
    (terpri)))
Output:
~/{Downloads,Pictures}/*.{jpg,gif,png}
    ~/Downloads/*.jpg
    ~/Downloads/*.gif
    ~/Downloads/*.png
    ~/Pictures/*.jpg
    ~/Pictures/*.gif
    ~/Pictures/*.png

It{{em,alic}iz,erat}e{d,}, please.
    Itemized, please.
    Itemize, please.
    Italicized, please.
    Italicize, please.
    Iterated, please.
    Iterate, please.

{,{,gotta have{ ,\, again\, }}more }cowbell!
    cowbell!
    more cowbell!
    gotta have more cowbell!
    gotta have\, again\, more cowbell!

{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}
    {}} some }{,{\\ edge \,}{ cases, {here} \\\\\}
    {}} some }{,{\\ edge \,}{ cases, {here} \\\\\}

D

Translation of: Python

This code is not UTF-corrected, because it uses slicing instead of front, popFront, etc.

import std.stdio, std.typecons, std.array, std.range, std.algorithm, std.string;

Nullable!(Tuple!(string[], string)) getGroup(string s, in uint depth)
pure nothrow @safe {
    string[] sout;
    auto comma = false;

    while (!s.empty) {
        // {const g, s} = getItems(s, depth);
        const r = getItems(s, depth);
        const g = r[0];
        s = r[1];

        if (s.empty)
            break;
        sout ~= g;

        if (s[0] == '}') {
            if (comma)
                return typeof(return)(tuple(sout, s[1 .. $]));
            return typeof(return)(tuple(
                sout.map!(a => '{' ~ a ~ '}').array, s[1 .. $]));
        }

        if (s[0] == ',') {
            comma = true;
            s = s[1 .. $];
        }
    }
    return typeof(return)();
}

Tuple!(string[], string) getItems(string s, in uint depth=0) pure @safe nothrow {
    auto sout = [""];

    while (!s.empty) {
        auto c = s[0 .. 1];
        if (depth && (c == "," || c == "}"))
            return tuple(sout, s);

        if (c == "{") {
            /*const*/ auto x = getGroup(s.dropOne, depth + 1);
            if (!x.isNull) {
                sout = cartesianProduct(sout, x[0])
                       .map!(ab => ab[0] ~ ab[1])
                       .array;
                s = x[1];
                continue;
            }
        }

        if (c == "\\" && s.length > 1) {
            c ~= s[1];
            s = s[1 .. $];
        }

        sout = sout.map!(a => a ~ c).array;
        s = s[1 .. $];
    }
    return tuple(sout, s);
}

void main() @safe {
    immutable testCases = r"~/{Downloads,Pictures}/*.{jpg,gif,png}
It{{em,alic}iz,erat}e{d,}, please.
{,{,gotta have{ ,\, again\, }}more }cowbell!
{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}
a{b{1,2}c
a{1,2}b}c
a{1,{2},3}b
a{b{1,2}c{}}
more{ darn{ cowbell,},}
ab{c,d\,e{f,g\h},i\,j{k,l\,m}n,o\,p}qr
{a,{\,b}c
a{b,{{c}}
{a{\}b,c}d
{a,b{{1,2}e}f";

    foreach (const s; testCases.splitLines)
        writefln("%s\n%-(    %s\n%)\n", s, s.getItems[0]);
}
Output:
~/{Downloads,Pictures}/*.{jpg,gif,png}
    ~/Downloads/*.jpg
    ~/Downloads/*.gif
    ~/Downloads/*.png
    ~/Pictures/*.jpg
    ~/Pictures/*.gif
    ~/Pictures/*.png

It{{em,alic}iz,erat}e{d,}, please.
    Itemized, please.
    Itemize, please.
    Italicized, please.
    Italicize, please.
    Iterated, please.
    Iterate, please.

{,{,gotta have{ ,\, again\, }}more }cowbell!
    cowbell!
    more cowbell!
    gotta have more cowbell!
    gotta have\, again\, more cowbell!

{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}
    {}} some }{,{\\ edge \,}{ cases, {here} \\\\\}
    {}} some }{,{\\ edge \,}{ cases, {here} \\\\\}

a{b{1,2}c
    a{b1c
    a{b2c

a{1,2}b}c
    a1b}c
    a2b}c

a{1,{2},3}b
    a1b
    a{2}b
    a3b

a{b{1,2}c{}}
    a{b1c{}}
    a{b2c{}}

more{ darn{ cowbell,},}
    more darn cowbell
    more darn
    more

ab{c,d\,e{f,g\h},i\,j{k,l\,m}n,o\,p}qr
    abcqr
    abd\,efqr
    abd\,eg\hqr
    abi\,jknqr
    abi\,jl\,mnqr
    abo\,pqr

{a,{\,b}c
    {a,{\,b}c

a{b,{{c}}
    a{b,{{c}}

{a{\}b,c}d
    {a\}bd
    {acd

{a,b{{1,2}e}f
    {a,b{1e}f
    {a,b{2e}f

Elixir

Translation of: Ruby
defmodule Brace_expansion do
  def getitem(s), do: getitem(String.codepoints(s), 0, [""])
  
  defp getitem([], _, out), do: {out,[]}
  defp getitem([c|_]=s, depth, out) when depth>0 and (c == "," or c == "}"), do: {out,s}
  defp getitem([c|t], depth, out) do
    x = getgroup(t, depth+1, [], false)
    if (c == "{") and x do
      {y, z} = x
      out2 = for a <- out, b <- y, do: a<>b
      getitem(z, depth, out2)
    else
      if c == "\\" and length(t) > 0 do
        c2 = c <> hd(t)
        getitem(tl(t), depth, Enum.map(out, fn a -> a <> c2 end))
      else 
        getitem(t, depth, Enum.map(out, fn a -> a <> c end))
      end
    end
  end
  
  defp getgroup([], _, _, _), do: nil
  defp getgroup(s, depth, out, comma) do
    {g, s2} = getitem(s, depth, [""])
    if s2 == [] do
      nil
    else
      out2 = out ++ g
      case hd(s2) do
        "}" -> if comma, do: {out2, tl(s2)},
                       else: {Enum.map(out2, &"{#{&1}}"), tl(s2)}
        "," -> getgroup(tl(s2), depth, out2, true)
        _   -> getgroup(s2, depth, out2, comma)
      end
    end
  end
end

test_cases = ~S"""
~/{Downloads,Pictures}/*.{jpg,gif,png}
It{{em,alic}iz,erat}e{d,}, please.
{,{,gotta have{ ,\, again\, }}more }cowbell!
{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}
""" |> String.split("\n", trim: true)

Enum.each(test_cases, fn s ->
  IO.puts s
  Brace_expansion.getitem(s)
  |> elem(0)
  |> Enum.each(fn str -> IO.puts "\t#{str}" end)
  IO.puts ""
end)
Output:
~/{Downloads,Pictures}/*.{jpg,gif,png}
        ~/Downloads/*.jpg
        ~/Downloads/*.gif
        ~/Downloads/*.png
        ~/Pictures/*.jpg
        ~/Pictures/*.gif
        ~/Pictures/*.png

It{{em,alic}iz,erat}e{d,}, please.
        Itemized, please.
        Itemize, please.
        Italicized, please.
        Italicize, please.
        Iterated, please.
        Iterate, please.

{,{,gotta have{ ,\, again\, }}more }cowbell!
        cowbell!
        more cowbell!
        gotta have more cowbell!
        gotta have\, again\, more cowbell!

{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}
        {}} some }{,{\\ edge \,}{ cases, {here} \\\\\}
        {}} some }{,{\\ edge \,}{ cases, {here} \\\\\}

Go

expand.go:

package expand

// Expander is anything that can be expanded into a slice of strings.
type Expander interface {
	Expand() []string
}

// Text is a trivial Expander that expands to a slice with just itself.
type Text string

func (t Text) Expand() []string { return []string{string(t)} }

// Alternation is an Expander that expands to the union of its
// members' expansions.
type Alternation []Expander

func (alt Alternation) Expand() []string {
	var out []string
	for _, e := range alt {
		out = append(out, e.Expand()...)
	}
	return out
}

// Sequence is an Expander that expands to the combined sequence of its
// members' expansions.
type Sequence []Expander

func (seq Sequence) Expand() []string {
	if len(seq) == 0 {
		return nil
	}
	out := seq[0].Expand()
	for _, e := range seq[1:] {
		out = combine(out, e.Expand())
	}
	return out
}

func combine(al, bl []string) []string {
	out := make([]string, 0, len(al)*len(bl))
	for _, a := range al {
		for _, b := range bl {
			out = append(out, a+b)
		}
	}
	return out
}

// Currently only single byte runes are supported for these.
const (
	escape   = '\\'
	altStart = '{'
	altEnd   = '}'
	altSep   = ','
)

type piT struct{ pos, cnt, depth int }

type Brace string

// Expand takes an input string and returns the expanded list of
// strings. The input string can contain any number of nested
// alternation specifications of the form "{A,B}" which is expanded to
// the strings "A", then "B".
//
// E.g. Expand("a{2,1}b{X,Y,X}c") returns ["a2bXc", "a2bYc", "a2bXc",
// "a1bXc", "a1bYc", "a1bXc"].
//
// Unmatched '{', ',', and '}' characters are passed through to the
// output. The special meaning of these characters can be escaped with
// '\', (which itself can be escaped).
// Escape characters are not removed, but passed through to the output.
func Expand(s string) []string   { return Brace(s).Expand() }
func (b Brace) Expand() []string { return b.Expander().Expand() }
func (b Brace) Expander() Expander {
	s := string(b)
	//log.Printf("Exapand(%#q)\n", s)
	var posInfo []piT
	var stack []int // indexes into posInfo
	removePosInfo := func(i int) {
		end := len(posInfo) - 1
		copy(posInfo[i:end], posInfo[i+1:])
		posInfo = posInfo[:end]
	}

	inEscape := false
	for i, r := range s {
		if inEscape {
			inEscape = false
			continue
		}
		switch r {
		case escape:
			inEscape = true
		case altStart:
			stack = append(stack, len(posInfo))
			posInfo = append(posInfo, piT{i, 0, len(stack)})
		case altEnd:
			if len(stack) == 0 {
				continue
			}
			si := len(stack) - 1
			pi := stack[si]
			if posInfo[pi].cnt == 0 {
				removePosInfo(pi)
				for pi < len(posInfo) {
					if posInfo[pi].depth == len(stack) {
						removePosInfo(pi)
					} else {
						pi++
					}
				}
			} else {
				posInfo = append(posInfo, piT{i, -2, len(stack)})
			}
			stack = stack[:si]
		case altSep:
			if len(stack) == 0 {
				continue
			}
			posInfo = append(posInfo, piT{i, -1, len(stack)})
			posInfo[stack[len(stack)-1]].cnt++
		}
	}
	//log.Println("stack:", stack)
	for len(stack) > 0 {
		si := len(stack) - 1
		pi := stack[si]
		depth := posInfo[pi].depth
		removePosInfo(pi)
		for pi < len(posInfo) {
			if posInfo[pi].depth == depth {
				removePosInfo(pi)
			} else {
				pi++
			}
		}
		stack = stack[:si]
	}
	return buildExp(s, 0, posInfo)
}

func buildExp(s string, off int, info []piT) Expander {
	if len(info) == 0 {
		return Text(s)
	}
	//log.Printf("buildExp(%#q, %d, %v)\n", s, off, info)
	var seq Sequence
	i := 0
	var dj, j, depth int
	for dk, piK := range info {
		k := piK.pos - off
		switch s[k] {
		case altStart:
			if depth == 0 {
				dj = dk
				j = k
				depth = piK.depth
			}
		case altEnd:
			if piK.depth != depth {
				continue
			}
			if j > i {
				seq = append(seq, Text(s[i:j]))
			}
			alt := buildAlt(s[j+1:k], depth, j+1+off, info[dj+1:dk])
			seq = append(seq, alt)
			i = k + 1
			depth = 0
		}
	}
	if j := len(s); j > i {
		seq = append(seq, Text(s[i:j]))
	}
	if len(seq) == 1 {
		return seq[0]
	}
	return seq
}

func buildAlt(s string, depth, off int, info []piT) Alternation {
	//log.Printf("buildAlt(%#q, %d, %d, %v)\n", s, depth, off, info)
	var alt Alternation
	i := 0
	var di int
	for dk, piK := range info {
		if piK.depth != depth {
			continue
		}
		if k := piK.pos - off; s[k] == altSep {
			sub := buildExp(s[i:k], i+off, info[di:dk])
			alt = append(alt, sub)
			i = k + 1
			di = dk + 1
		}
	}
	sub := buildExp(s[i:], i+off, info[di:])
	alt = append(alt, sub)
	return alt
}

expand_test.go

package expand

import (
	"fmt"
	"reflect"
	"testing"
)

// These could be in expand.go but for now they're only used for debugging.
func (t Text) String() string          { return fmt.Sprintf("%#q", string(t)) }
func (alt Alternation) String() string { return fmt.Sprintf("ALT:%v", []Expander(alt)) }

// From http://rosettacode.org/wiki/Brace_expansion
var testCases = []struct {
	input    string
	expected []string
}{
	{"", []string{""}},
	{"a{2,1}b{X,Y,X}c", []string{
		"a2bXc",
		"a2bYc",
		"a2bXc",
		"a1bXc",
		"a1bYc",
		"a1bXc"}},
	{`a\\{\\\{b,c\,d}`, []string{
		`a\\\\\{b`,
		`a\\c\,d`}},
	{"{a,b{c{,{d}}e}f", []string{
		"{a,b{ce}f",
		"{a,b{c{d}e}f"}},
	{"~/{Downloads,Pictures}/*.{jpg,gif,png}", []string{
		"~/Downloads/*.jpg",
		"~/Downloads/*.gif",
		"~/Downloads/*.png",
		"~/Pictures/*.jpg",
		"~/Pictures/*.gif",
		"~/Pictures/*.png"}},
	{"It{{em,alic}iz,erat}e{d,}, please.", []string{
		"Itemized, please.",
		"Itemize, please.",
		"Italicized, please.",
		"Italicize, please.",
		"Iterated, please.",
		"Iterate, please."}},
	{`{,{,gotta have{ ,\, again\, }}more }cowbell!`, []string{
		"cowbell!",
		"more cowbell!",
		"gotta have more cowbell!",
		`gotta have\, again\, more cowbell!`}},
	{`{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}`, []string{
		`{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}`,
		`{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}`}},
}

//func ml(l []string) string { return "\n\t" + strings.Join(l, "\n\t") }
func ml(l []string) string {
	var result string
	for _, s := range l {
		result += fmt.Sprintf("\n\t%#q", s)
	}
	return result
}

func TestExpand(t *testing.T) {
	for _, d := range testCases {
		if g := Expand(d.input); !reflect.DeepEqual(g, d.expected) {
			t.Errorf("unexpected result\n Expand(%#q) gave:%v\nExpected:%v",
				d.input, ml(g), ml(d.expected))
		} else {
			// Normally Go tests aren't this verbose, but for rosettacode
			t.Logf("as expected\n Expand(%#q):%v", d.input, ml(g))
		}
	}
}

func BenchmarkExpand(b *testing.B) {
	input := testCases[5].input
	//b.Logf("Benchmarking Expand(%#q)\n", input)
	b.ReportAllocs()
	for i := 0; i < b.N; i++ {
		Expand(input)
	}
}
Output:
% go test -v -bench=.
=== RUN TestExpand
--- PASS: TestExpand (0.00 seconds)
	expand_test.go:72: as expected
		 Expand(``):
			``
	expand_test.go:72: as expected
		 Expand(`a{2,1}b{X,Y,X}c`):
			`a2bXc`
			`a2bYc`
			`a2bXc`
			`a1bXc`
			`a1bYc`
			`a1bXc`
	expand_test.go:72: as expected
		 Expand(`a\\{\\\{b,c\,d}`):
			`a\\\\\{b`
			`a\\c\,d`
	expand_test.go:72: as expected
		 Expand(`{a,b{c{,{d}}e}f`):
			`{a,b{ce}f`
			`{a,b{c{d}e}f`
	expand_test.go:72: as expected
		 Expand(`~/{Downloads,Pictures}/*.{jpg,gif,png}`):
			`~/Downloads/*.jpg`
			`~/Downloads/*.gif`
			`~/Downloads/*.png`
			`~/Pictures/*.jpg`
			`~/Pictures/*.gif`
			`~/Pictures/*.png`
	expand_test.go:72: as expected
		 Expand(`It{{em,alic}iz,erat}e{d,}, please.`):
			`Itemized, please.`
			`Itemize, please.`
			`Italicized, please.`
			`Italicize, please.`
			`Iterated, please.`
			`Iterate, please.`
	expand_test.go:72: as expected
		 Expand(`{,{,gotta have{ ,\, again\, }}more }cowbell!`):
			`cowbell!`
			`more cowbell!`
			`gotta have more cowbell!`
			`gotta have\, again\, more cowbell!`
	expand_test.go:72: as expected
		 Expand(`{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}`):
			`{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}`
			`{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}`
PASS
BenchmarkExpand	  500000	      6562 ns/op	    2467 B/op	      64 allocs/op
ok  	rosetta_code/Brace_expansion	3.347s

Groovy

Translation of: Java
class BraceExpansion {
    static void main(String[] args) {
        for (String s : [
                "It{{em,alic}iz,erat}e{d,}, please.",
                "~/{Downloads,Pictures}/*.{jpg,gif,png}",
                "{,{,gotta have{ ,\\, again\\, }}more }cowbell!",
                "{}} some }{,{\\\\{ edge, edge} \\,}{ cases, {here} \\\\\\\\\\}"
        ]) {
            println()
            expand(s)
        }
    }

    static void expand(String s) {
        expandR("", s, "")
    }

    private static void expandR(String pre, String s, String suf) {
        int i1 = -1, i2 = 0
        String noEscape = s.replaceAll("([\\\\]{2}|[\\\\][,}{])", "  ")
        StringBuilder sb = null

        outer:
        while ((i1 = noEscape.indexOf('{', i1 + 1)) != -1) {
            i2 = i1 + 1
            sb = new StringBuilder(s)
            for (int depth = 1; i2 < s.length() && depth > 0; i2++) {
                char c = noEscape.charAt(i2)
                depth = (c == ('{' as char)) ? ++depth : depth
                depth = (c == ('}' as char)) ? --depth : depth
                if (c == (',' as char) && depth == 1) {
                    sb.setCharAt(i2, '\u0000' as char)
                } else if (c == ('}' as char) && depth == 0 && sb.indexOf("\u0000") != -1) {
                    break outer
                }
            }
        }
        if (i1 == -1) {
            if (suf.length() > 0) {
                expandR(pre + s, suf, "")
            } else {
                printf("%s%s%s%n", pre, s, suf)
            }
        } else {
            for (String m : sb.substring(i1 + 1, i2).split("\u0000", -1)) {
                expandR(pre + s.substring(0, i1), m, s.substring(i2 + 1) + suf)
            }
        }
    }
}
Output:
Itemized, please.
Itemize, please.
Italicized, please.
Italicize, please.
Iterated, please.
Iterate, please.

~/Downloads/*.jpg
~/Downloads/*.gif
~/Downloads/*.png
~/Pictures/*.jpg
~/Pictures/*.gif
~/Pictures/*.png

cowbell!
more cowbell!
gotta have more cowbell!
gotta have\, again\, more cowbell!

{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}
{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}

Haskell

"Here is a direct translation to Haskell using parsec" (of an earlier version of the Raku solution):

import qualified Text.Parsec as P

showExpansion :: String -> String
showExpansion =
  (<>) . (<> "\n-->\n") <*> (either show unlines . P.parse parser [])

parser :: P.Parsec String u [String]
parser = expansion P.anyChar

expansion :: P.Parsec String u Char -> P.Parsec String u [String]
expansion =
  fmap expand .
  P.many .
  ((P.try alts P.<|> P.try alt1 P.<|> escape) P.<|>) . fmap (pure . pure)

expand :: [[String]] -> [String]
expand = foldr ((<*>) . fmap (<>)) [[]]

alts :: P.Parsec String u [String]
alts = concat <$> P.between (P.char '{') (P.char '}') (alt `sepBy2` P.char ',')

alt :: P.Parsec String u [String]
alt = expansion (P.noneOf ",}")

alt1 :: P.Parsec String u [String]
alt1 =
  (\x -> ['{' : (x <> "}")]) <$>
  P.between (P.char '{') (P.char '}') (P.many $ P.noneOf ",{}")

sepBy2 :: P.Parsec String u a -> P.Parsec String u b -> P.Parsec String u [a]
p `sepBy2` sep = (:) <$> p <*> P.many1 (sep >> p)

escape :: P.Parsec String u [String]
escape = pure <$> sequence [P.char '\\', P.anyChar]

main :: IO ()
main =
  mapM_
    (putStrLn . showExpansion)
    [ "~/{Downloads,Pictures}/*.{jpg,gif,png}"
    , "It{{em,alic}iz,erat}e{d,}, please."
    , "{,{,gotta have{ ,\\, again\\, }}more }cowbell!"
    , "{}} some }{,{\\\\{ edge, edge} \\,}{ cases, {here} \\\\\\\\\\}"
    ]
Output:
It{{em,alic}iz,erat}e{d,}, please.
-->
Itemized, please.
Itemize, please.
Italicized, please.
Italicize, please.
Iterated, please.
Iterate, please.

{,{,gotta have{ ,\, again\, }}more }cowbell!
-->
cowbell!
more cowbell!
gotta have more cowbell!
gotta have\, again\, more cowbell!

{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}
-->
{}} some }{ cases, {here} \\\\\}
{}} some }{\\ edge \,{ cases, {here} \\\\\}
{}} some }{\\ edge \,{ cases, {here} \\\\\}

J

Implementation:

NB. legit { , and } do not follow a legit backslash:
legit=: 1,_1}.4>(3;(_2[\"1".;._2]0 :0);('\';a.);0 _1 0 1)&;:&.(' '&,)
 2 1   1 1 NB. result 0 or 1: initial state
 2 2   1 2 NB. result 2 or 3: after receiving a non backslash
 1 2   1 2 NB. result 4 or 5: after receiving a backslash
)

expand=:3 :0
  Ch=. u:inv y
  M=. N=. 1+>./ Ch
  Ch=. Ch*-_1^legit y
  delim=. 'left comma right'=. u:inv '{,}'
  J=. i.K=. #Ch
  while. M=. M+1 do.
    candidates=. i.0 2
    for_check.I. comma=Ch do.
      begin=. >./I. left=check{. Ch
      end=. check+<./I. right=check}. Ch
      if. K>:end-begin do.
        candidates=. candidates,begin,end
      end.
    end.
    if. 0=#candidates do. break. end.
    'begin end'=. candidates{~(i.>./) -/"1 candidates
    ndx=. I.(begin<:J)*(end>:J)*Ch e. delim
    Ch=. M ndx} Ch 
  end.
  T=. ,<Ch
  for_mark. |.N}.i.M  do.
    T=. ; mark divide each T
  end.
  u: each |each T
)

divide=:4 :0
  if. -.x e. y do. ,<y return. end.
  mask=. x=y
  prefix=. < y #~ -.+./\ mask
  suffix=. < y #~ -.+./\. mask
  options=. }:mask <;._1 y
  prefix,each options,each suffix
)

Examples:

   >expand t1
~/Downloads/*.jpg
~/Downloads/*.gif
~/Downloads/*.png
~/Pictures/*.jpg 
~/Pictures/*.gif 
~/Pictures/*.png 
   > expand t2
Itemized, please.  
Itemize, please.   
Italicized, please.
Italicize, please. 
Iterated, please.  
Iterate, please.   
   >expand t3
cowbell!                          
more cowbell!                     
gotta have more cowbell!          
gotta have\, again\, more cowbell!
   >expand t4
{}} some {\\edge }{ cases, here\\\}
{}} some {\\edgy }{ cases, here\\\}

Explanation:

Instead of working directly with text, work with a string of numeric unicode values. Negate the numbers for characters which are "off limits" because of preceding backslashes (we will take the absolute value and convert back to unicode for the final result). Also, find a limit value larger than that of the largest in-use character.

Then, iteratively: for each relevant comma, find the location of the closest surrounding braces. From these candidates, pick a pair of braces that's the shortest distance apart. Mark those braces and their contained relevant commas by replacing their character codes with an integer larger than any previously used (all of them in the set get marked with the same number). Repeat until we cannot find any more possibilities.

Finally, for each integer that we've used to mark delimiter locations, split out each of the marked options (each with a copy of that group's prefix and suffix). (Then when all that is done, take the absolute values convert back to unicode for the final result.)

Java

Should be able to handle all printable Unicode.

public class BraceExpansion {

    public static void main(String[] args) {
        for (String s : new String[]{"It{{em,alic}iz,erat}e{d,}, please.",
            "~/{Downloads,Pictures}/*.{jpg,gif,png}",
            "{,{,gotta have{ ,\\, again\\, }}more }cowbell!",
            "{}} some }{,{\\\\{ edge, edge} \\,}{ cases, {here} \\\\\\\\\\}"}) {
            System.out.println();
            expand(s);
        }
    }

    public static void expand(String s) {
        expandR("", s, "");
    }

    private static void expandR(String pre, String s, String suf) {
        int i1 = -1, i2 = 0;
        String noEscape = s.replaceAll("([\\\\]{2}|[\\\\][,}{])", "  ");
        StringBuilder sb = null;

        outer:
        while ((i1 = noEscape.indexOf('{', i1 + 1)) != -1) {
            i2 = i1 + 1;
            sb = new StringBuilder(s);
            for (int depth = 1; i2 < s.length() && depth > 0; i2++) {
                char c = noEscape.charAt(i2);
                depth = (c == '{') ? ++depth : depth;
                depth = (c == '}') ? --depth : depth;
                if (c == ',' && depth == 1) {
                    sb.setCharAt(i2, '\u0000');
                } else if (c == '}' && depth == 0 && sb.indexOf("\u0000") != -1)
                    break outer;
            }
        }
        if (i1 == -1) {
            if (suf.length() > 0)
                expandR(pre + s, suf, "");
            else
                System.out.printf("%s%s%s%n", pre, s, suf);
        } else {
            for (String m : sb.substring(i1 + 1, i2).split("\u0000", -1))
                expandR(pre + s.substring(0, i1), m, s.substring(i2 + 1) + suf);
        }
    }
}
Itemized, please.
Itemize, please.
Italicized, please.
Italicize, please.
Iterated, please.
Iterate, please.

~/Downloads/*.jpg
~/Downloads/*.gif
~/Downloads/*.png
~/Pictures/*.jpg
~/Pictures/*.gif
~/Pictures/*.png

cowbell!
more cowbell!
gotta have more cowbell!
gotta have\, again\, more cowbell!

{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}
{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}

JavaScript

ES5 Functional

Without importing Node.js libraries, JavaScript doesn't immediately have access to anything like Haskell's Parsec, but using a functional idiom of JavaScript, and emphasising clarity more than optimisation, we can separate out the tokenizing from the parsing, and the parsing from the generation of strings, to build a function which:

  1. returns the set of expansions for each brace expression, and
  2. logs a pretty-printed abstract syntax tree for each expression to the console (in a JSON format).

Each node of the parse tree consists of one of two simple functions (AND: syntagmatic concatenation, OR: flattening of paradigms) with a set of arguments, each of which may be a plain string or an AND or OR subtree. The expansions are derived by evaluating the parse tree as an expression.

(function () {
    'use strict'

    // Index of any closing brace matching the opening 
    // brace at iPosn,
    // with the indices of any immediately-enclosed commas.
    function bracePair(tkns, iPosn, iNest, lstCommas) {
        if (iPosn >= tkns.length || iPosn < 0) return null;

        var t = tkns[iPosn],
            n = (t === '{') ? (
                iNest + 1
            ) : (t === '}' ? (
                iNest - 1
            ) : iNest),
            lst = (t === ',' && iNest === 1) ? (
                lstCommas.concat(iPosn)
            ) : lstCommas;

        return n ? bracePair(tkns, iPosn + 1, n, lst) : {
            close: iPosn,
            commas: lst
        };
    }

    // Parse of a SYNTAGM subtree
    function andTree(dctSofar, tkns) {
        if (!tkns.length) return [dctSofar, []];

        var dctParse = dctSofar ? dctSofar : {
                fn: and,
                args: []
            },

            head = tkns[0],
            tail = head ? tkns.slice(1) : [],

            dctBrace = head === '{' ? bracePair(
                tkns, 0, 0, []
            ) : null,

            lstOR = dctBrace && (
                dctBrace.close
            ) && dctBrace.commas.length ? (
                splitAt(dctBrace.close + 1, tkns)
            ) : null;

        return andTree({
            fn: and,
            args: dctParse.args.concat(
                lstOR ? (
                    orTree(dctParse, lstOR[0], dctBrace.commas)
                ) : head
            )
        }, lstOR ? (
            lstOR[1]
        ) : tail);
    }

    // Parse of a PARADIGM subtree
    function orTree(dctSofar, tkns, lstCommas) {
        if (!tkns.length) return [dctSofar, []];
        var iLast = lstCommas.length;

        return {
            fn: or,
            args: splitsAt(
                lstCommas, tkns
            ).map(function (x, i) {
                var ts = x.slice(
                    1, i === iLast ? (
                        -1
                    ) : void 0
                );

                return ts.length ? ts : [''];
            }).map(function (ts) {
                return ts.length > 1 ? (
                    andTree(null, ts)[0]
                ) : ts[0];
            })
        };
    }

    // List of unescaped braces and commas, and remaining strings
    function tokens(str) {
        // Filter function excludes empty splitting artefacts
        var toS = function (x) {
            return x.toString();
        };

        return str.split(/(\\\\)/).filter(toS).reduce(function (a, s) {
            return a.concat(s.charAt(0) === '\\' ? s : s.split(
                /(\\*[{,}])/
            ).filter(toS));
        }, []);
    }

    // PARSE TREE OPERATOR (1 of 2)
    // Each possible head * each possible tail
    function and(args) {
        var lng = args.length,
            head = lng ? args[0] : null,
            lstHead = "string" === typeof head ? (
                [head]
            ) : head;

        return lng ? (
            1 < lng ? lstHead.reduce(function (a, h) {
                return a.concat(
                    and(args.slice(1)).map(function (t) {
                        return h + t;
                    })
                );
            }, []) : lstHead
        ) : [];
    }

    // PARSE TREE OPERATOR (2 of 2)
    // Each option flattened
    function or(args) {
        return args.reduce(function (a, b) {
            return a.concat(b);
        }, []);
    }

    // One list split into two (first sublist length n)
    function splitAt(n, lst) {
        return n < lst.length + 1 ? [
            lst.slice(0, n), lst.slice(n)
        ] : [lst, []];
    }

    // One list split into several (sublist lengths [n])
    function splitsAt(lstN, lst) {
        return lstN.reduceRight(function (a, x) {
            return splitAt(x, a[0]).concat(a.slice(1));
        }, [lst]);
    }

    // Value of the parse tree
    function evaluated(e) {
        return typeof e === 'string' ? e :
            e.fn(e.args.map(evaluated));
    }

    // JSON prettyprint (for parse tree, token list etc)
    function pp(e) {
        return JSON.stringify(e, function (k, v) {
            return typeof v === 'function' ? (
                '[function ' + v.name + ']'
            ) : v;
        }, 2)
    }


    // ----------------------- MAIN ------------------------

    // s -> [s]
    function expansions(s) {
        // BRACE EXPRESSION PARSED
        var dctParse = andTree(null, tokens(s))[0];

        // ABSTRACT SYNTAX TREE LOGGED
        console.log(pp(dctParse));

        // AST EVALUATED TO LIST OF STRINGS
        return evaluated(dctParse);
    }


    // Sample expressions, 
    // double-escaped for quotation in source code.
    var lstTests = [
        '~/{Downloads,Pictures}/*.{jpg,gif,png}',
        'It{{em,alic}iz,erat}e{d,}, please.',
        '{,{,gotta have{ ,\\, again\\, }}more }cowbell!',
        '{}} some }{,{\\\\{ edge, edge} \\,}{ cases, {here} \\\\\\\\\\}'
    ];


    // 1. Return each expression with an indented list of its expansions, while
    // 2. logging each parse tree to the console.log() stream

    return lstTests.map(function (s) {
        return s + '\n\n' + expansions(s).map(function (x) {
            return '   ' + x;
        }).join('\n');
    }).join('\n\n');

})();

Value returned by function:

~/{Downloads,Pictures}/*.{jpg,gif,png}

   ~/Downloads/*.jpg
   ~/Downloads/*.gif
   ~/Downloads/*.png
   ~/Pictures/*.jpg
   ~/Pictures/*.gif
   ~/Pictures/*.png

It{{em,alic}iz,erat}e{d,}, please.

   Itemized, please.
   Itemize, please.
   Italicized, please.
   Italicize, please.
   Iterated, please.
   Iterate, please.

{,{,gotta have{ ,\, again\, }}more }cowbell!

   cowbell!
   more cowbell!
   gotta have more cowbell!
   gotta have\, again\, more cowbell!

{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}

   {}} some }{,{\\ edge \,}{ cases, {here} \\\\\}
   {}} some }{,{\\ edge \,}{ cases, {here} \\\\\}

Sample of parse trees logged to the console:

{
  "fn": "[function and]",
  "args": [
    "It",
    {
      "fn": "[function or]",
      "args": [
        {
          "fn": "[function and]",
          "args": [
            {
              "fn": "[function or]",
              "args": [
                "em",
                "alic"
              ]
            },
            "iz"
          ]
        },
        "erat"
      ]
    },
    "e",
    {
      "fn": "[function or]",
      "args": [
        "d",
        ""
      ]
    },
    ",",
    " please."
  ]
}

jq

Adapted from Wren

Works with: jq

Also works with gojq, the Go implementation of jq

# Input: a string
# Emit an array of the expansions
def expand:

  # Emit [ array, string ] 
  def getItem($depth):

  def getGroup($depth):
    { out: [], comma: false, s: . }
    | until (.s == "" or .return;
        (.s | getItem($depth)) as $t
        | $t[0] as $g
        | .s = $t[1]
        | if .s == "" then .return = [[], ""]
          else .out += $g
          | if .s[0:1] == "}"
            then if .comma then .return = [.out, .s[1:]] 
                 else .return = [ (.out | map( "{" + . + "}" )), .s[1:]]
                 end
            else if .s[0:1] == ","
                 then .comma = true
                 | .s |= .[1:]
                 else .
	         end
            end
     	  end)
    | if .return then .return else [[], ""] end ;

    { out: [""], s: .}
    | until( (.s == "") or .return;
        .c = .s[0:1]
        | if ($depth > 0) and (.c == "," or .c == "}")
	  then .return = [.out, .s]
      else .cont = false
      | if .c == "{"
	    then (.s[1:] | getGroup($depth+1)) as $x
        | if $x[0] | length > 0
          # conform to the "lexicographic" ordering requirement
          then .out |= [ .[] as $o | $o + $x[0][] ]
          | .s = $x[1]
          | .cont = true
	      else .
	      end
        else .
        end
	  end
      | if (.cont | not)
        then if (.c == "\\") and ((.s|length) > 1)
	         then .c += .s[1:2]
             | .s |= .[1:]
             else .
		     end
        | .out = [.out[] + .c]
        | .s |= .[1:]
        else .
	    end )
      | if .return then .return else [.out, .s] end ;

    getItem(0)[0];
    
def inputs: [
     "~/{Downloads,Pictures}/*.{jpg,gif,png}",
    "It{{em,alic}iz,erat}e{d,}, please.",
    "{,{,gotta have{ ,\\, again\\, }}more }cowbell!",
    "{}} some }{,{\\\\{ edge, edge} \\,}{ cases, {here} \\\\\\\\\\}"
];

inputs[]
| "\n",
  .,
  "    " + expand[]
Output:
~/{Downloads,Pictures}/*.{jpg,gif,png}
    ~/Downloads/*.jpg
    ~/Downloads/*.gif
    ~/Downloads/*.png
    ~/Pictures/*.jpg
    ~/Pictures/*.gif
    ~/Pictures/*.png


It{{em,alic}iz,erat}e{d,}, please.
    Itemized, please.
    Itemize, please.
    Italicized, please.
    Italicize, please.
    Iterated, please.
    Iterate, please.


{,{,gotta have{ ,\, again\, }}more }cowbell!
    cowbell!
    more cowbell!
    gotta have more cowbell!
    gotta have\, again\, more cowbell!


{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}
    {}} some }{,{\\ edge \,}{ cases, {here} \\\\\}
    {}} some }{,{\\ edge \,}{ cases, {here} \\\\\}

Julia

Translation of: Python
 function getitem(s, depth=0)
    out = [""]
    while s != ""
        c = s[1]
        if depth > 0 && (c == ',' || c == '}')
            return out, s
        elseif c == '{'
            x = getgroup(s[2:end], depth+1)
            if x != ""
                out, s = [a * b for a in out, b in x[1]], x[2]
                continue
            end
        elseif c == '\\' && length(s) > 1
            s, c = s[2:end], c * s[2]
        end
        out, s = [a * c for a in out], s[2:end]
    end
    return out, s
end

function getgroup(s, depth)
    out, comma = "", false
    while s != ""
        g, s = getitem(s, depth)
        if s == "" 
            break
        end
        out = vcat([out...], [g...])
        if s[1] == '}'
            if comma
                return out, s[2:end]
            end
            return ["{" * a * "}" for a in out], s[2:end]
        end
        if s[1] == ','
            comma, s = true, s[2:end]
        end
    end
    return ""
end    

const teststrings = [raw"~/{Downloads,Pictures}/*.{jpg,gif,png}",
                    raw"It{{em,alic}iz,erat}e{d,}, please.",
                    raw"{,{,gotta have{ ,\, again\, }}more }cowbell!",
                    raw"{}} some }{,{\\\\{ edge, edge} \,}{ cases, {here} \\\\\\\\\}'''"]
    
for s in teststrings
    println("\n", s, "\n--------------------------------------------")
    for ans in getitem(s)[1]
        println(ans)
    end
end
Output:

~/{Downloads,Pictures}/*.{jpg,gif,png} -------------------------------------------- ~/Downloads/*.jpg ~/Pictures/*.jpg ~/Downloads/*.gif ~/Pictures/*.gif ~/Downloads/*.png ~/Pictures/*.png

It{{em,alic}iz,erat}e{d,}, please. -------------------------------------------- Itemized, please. Italicized, please. Iterated, please. Itemize, please. Italicize, please. Iterate, please.

{,{,gotta have{ ,\, again\, }}more }cowbell! -------------------------------------------- cowbell! more cowbell! gotta have more cowbell! gotta have\ again\ more cowbell!

{}} some }{,{\\\\{ edge, edge} \,}{ cases, {here} \\\\\\\\\}''' -------------------------------------------- {}} some }{,{\\\{ edge \}}{ cases, {here} \\\\\\\\\'''' {}} some }{,{\\\{ edge \}}{ cases, {here} \\\\\\\\\''''

Kotlin

Translation of: Java
// version 1.1.2

object BraceExpansion {
    fun expand(s: String) = expandR("", s, "")

    private val r = Regex("""([\\]{2}|[\\][,}{])""")

    private fun expandR(pre: String, s: String, suf: String) {
        val noEscape = s.replace(r, "  ")
        var sb = StringBuilder("")
        var i1 = noEscape.indexOf('{')
        var i2 = 0

        outer@ while (i1 != -1) {
            sb = StringBuilder(s)
            var depth = 1
            i2 = i1 + 1
            while (i2 < s.length && depth > 0) {
                val c = noEscape[i2]

                if (c == '{') depth++
                else if (c == '}') depth--

                if (c == ',' && depth == 1) sb[i2] = '\u0000'
                else if (c == '}' && depth == 0 && sb.indexOf("\u0000") != -1) break@outer
                i2++
            }
            i1 = noEscape.indexOf('{', i1 + 1)
        }
        if (i1 == -1) {
            if (suf.isNotEmpty()) expandR(pre + s, suf, "")
            else println("$pre$s$suf")
        } else {
            for (m in sb.substring(i1 + 1, i2).split('\u0000')) {
                expandR(pre + s.substring(0, i1), m, s.substring(i2 + 1) + suf)
            }
        }
    }
}

fun main(args: Array<String>) {
    val strings = arrayOf(
        """~/{Downloads,Pictures}/*.{jpg,gif,png}""",
        """It{{em,alic}iz,erat}e{d,}, please.""",
        """{,{,gotta have{ ,\, again\, }}more }cowbell!""",
        """{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}"""
    )
    for (s in strings) {
        println()
        BraceExpansion.expand(s)
    }
}
Output:
~/Downloads/*.jpg
~/Downloads/*.gif
~/Downloads/*.png
~/Pictures/*.jpg
~/Pictures/*.gif
~/Pictures/*.png

Itemized, please.
Itemize, please.
Italicized, please.
Italicize, please.
Iterated, please.
Iterate, please.

cowbell!
more cowbell!
gotta have more cowbell!
gotta have\, again\, more cowbell!

{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}
{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}

Lua

Translation of: Python

Note that this code isn't very memory efficient.

local function wrapEachItem(items, prefix, suffix)
	local itemsWrapped = {}

	for i, item in ipairs(items) do
		itemsWrapped[i] = prefix .. item .. suffix
	end

	return itemsWrapped
end

local function getAllItemCombinationsConcatenated(aItems, bItems)
	local combinations = {}

	for _, a in ipairs(aItems) do
		for _, b in ipairs(bItems) do
			table.insert(combinations, a..b)
		end
	end

	return combinations
end

local getItems -- Forward declaration.

local function getGroup(s, pos, depth)
	local groupItems = {}
	local foundComma = false

	while pos <= #s do
		local items
		items, pos = getItems(s, pos, depth)
		if pos > #s then  break  end

		for _, item in ipairs(items) do
			table.insert(groupItems, item)
		end

		local c = s:sub(pos, pos)

		if c == "}" then -- Possibly end of group.
			if foundComma then  return groupItems, pos+1  end
			return wrapEachItem(groupItems, "{", "}"), pos+1 -- No group.

		elseif c == "," then
			foundComma, pos = true, pos+1
		end
	end

	return nil -- No group.
end

function getItems(s, pos, depth)
	local items = {""}

	while pos <= #s do
		local c = s:sub(pos, pos)

		if depth > 0 and (c == "," or c == "}") then -- End of item in surrounding group.
			return items, pos
		end

		local groupItems, nextPos = nil
		if c == "{" then -- Possibly start of a group.
			groupItems, nextPos = getGroup(s, pos+1, depth+1)
		end

		if groupItems then
			items, pos = getAllItemCombinationsConcatenated(items, groupItems), nextPos
		else
			if c == "\\" and pos < #s then -- Escaped character.
				pos = pos + 1
				c   = c .. s:sub(pos, pos)
			end
			items, pos = wrapEachItem(items, "", c), pos+1
		end
	end

	return items, pos
end

local tests = [[
~/{Downloads,Pictures}/*.{jpg,gif,png}
It{{em,alic}iz,erat}e{d,}, please.
{,{,gotta have{ ,\, again\, }}more }cowbell!
{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}
]]

for test in tests:gmatch"[^\n]+" do
	print(test)
	for _, item in ipairs(getItems(test, 1, 0)) do
		print("\t"..item)
	end
	print()
end
Output:
~/{Downloads,Pictures}/*.{jpg,gif,png}
	~/Downloads/*.jpg
	~/Downloads/*.gif
	~/Downloads/*.png
	~/Pictures/*.jpg
	~/Pictures/*.gif
	~/Pictures/*.png
...
{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}
	{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}
	{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}

Mathematica/Wolfram Language

(*The strategy is to first capture all special sub-expressions and reformat them so they are semantically clear. The built in function Distribute could then do the work of creating the alternatives, but the order wouldn't match that given in the instructions (although as a set the alternatives would be correct). I'll take a more complicated route so as to follow the instructions exactly.*)

(*A few named constants for readability.*)
EscapeToken="\\";(*In Mathematica, backslash is an escape character when inputing a string, so we need to escape it.*)
LeftBraceToken="{";
RightBraceToken="}";

(*This basically sequesters escaped substrings so that they don't get matched during later processing.*)
CaptureEscapes[exp:{___String}]:=SequenceReplace[exp,{EscapeToken,x_}:>EscapeToken<>x];

(*Any remaining braces are un-escaped. I'm "unstringifying" them to more easily pick them out during later processing.*)
CaptureBraces[exp:{___String}]:=ReplaceAll[exp,{LeftBraceToken->LeftBrace,RightBraceToken->RightBrace}];

(*Building up trees for the braced expressions. Extra braces are just raw data, so transform them back to strings.*)
CaptureBraceTrees[exp:{(_String|LeftBrace|RightBrace)...}]:=ReplaceAll[FixedPoint[SequenceReplace[{LeftBrace,seq:(_String|_BraceTree)...,RightBrace}:>BraceTree[seq]],exp],{LeftBrace->LeftBraceToken,RightBrace->RightBraceToken}];

(*At thie point, we should have an expression with well-braced substructures representing potential alternatives. We must expand brace trees to alternatives in the correct order.*)
ExpandBraceTrees[exp:Expr[head___String,bt_BraceTree,tail___]]:=ReplaceAll[Thread[Expr[head,ToAlternatives[bt],tail]],alt_Alt:>Sequence@@alt];
ExpandBraceTrees[exp:Expr[___String]]:={exp};
ExpandBraceTrees[exps:{__Expr}]:=Catenate[ExpandBraceTrees/@exps];

(*If there are no commas, then it's a literal sub-expression. Otherwise, it's a set of alternatives.*)
ToAlternatives[bt_BraceTree]:={LeftBraceToken<>StringJoin@@bt<>RightBraceToken}/;FreeQ[bt,","];
ToAlternatives[BraceTree[","]]=ToAlternatives[BraceTree["",",",""]];
ToAlternatives[bt:BraceTree[",",__]]:=ToAlternatives[Prepend[bt,""]];
ToAlternatives[bt:BraceTree[__,","]]:=ToAlternatives[Append[bt,""]];
ToAlternatives[bt_BraceTree]:=Alt@@@SequenceSplit[List@@bt,{","}];

NormalizeExpression=Apply[Expr]@*CaptureBraceTrees@*CaptureBraces@*CaptureEscapes@*Characters;

BraceExpand[str_String]:=ReplaceAll[FixedPoint[ExpandBraceTrees,NormalizeExpression[str]],Expr->StringJoin];

(*Data was stored in a local file.*)
BraceTestData=ReadList[FileNameJoin[{NotebookDirectory[],"BraceTestData.txt"}],String];BraceTestData//TableForm
~/{Downloads,Pictures}/*.{jpg,gif,png}
It{{em,alic}iz,erat}e{d,}, please.
{,{,gotta have{ ,\, again\, }}more }cowbell!
{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}
Output:
Column[Column /@ BraceExpand /@ BraceTestData, Left, 2]
~/Downloads/*.jpg
~/Downloads/*.gif
~/Downloads/*.png
~/Pictures/*.jpg
~/Pictures/*.gif
~/Pictures/*.png


Itemized, please.
Itemize, please.
Italicized, please.
Italicize, please.
Iterated, please.
Iterate, please.


cowbell!
more cowbell!
gotta have more cowbell!
gotta have\, again\, more cowbell!


{}} some }{,\\ edge \,{ cases, {here} \\\\\}
{}} some }{,\\ edge \,{ cases, {here} \\\\\}

Nim

Translation of: Seed7
proc expandBraces(str: string) =

  var
    escaped = false
    depth = 0
    bracePoints: seq[int]
    bracesToParse: seq[int]

  for idx, ch in str:
    case ch
    of '\\':
      escaped = not escaped
    of '{':
      inc depth
      if not escaped and depth == 1:
        bracePoints = @[idx]
    of ',':
      if not escaped and depth == 1:
        bracePoints &= idx
    of '}':
      if not escaped and depth == 1 and bracePoints.len >= 2:
        bracesToParse = bracePoints & idx
      dec depth
    else:
      discard
    if ch != '\\':
      escaped = false

  if bracesToParse.len > 0:
    let prefix = str[0..<bracesToParse[0]]
    let suffix = str[(bracesToParse[^1] + 1)..^1]
    for idx in 1..bracesToParse.high:
      let option = str[(bracesToParse[idx - 1] + 1)..(bracesToParse[idx] - 1)]
      expandBraces(prefix & option & suffix)

  else:
    echo "  ", str

#———————————————————————————————————————————————————————————————————————————————————————————————————

when isMainModule:

  for str in ["It{{em,alic}iz,erat}e{d,}, please.",
              "~/{Downloads,Pictures}/*.{jpg,gif,png}",
              "{,{,gotta have{ ,\\, again\\, }}more }cowbell!",
              "{}} some }{,{\\\\{ edge, edge} \\,}{ cases, {here} \\\\\\\\\\}"]:
    echo "\nExpansions of \"", str, "\":"
    expandBraces(str)
Output:
Expansions of "It{{em,alic}iz,erat}e{d,}, please.":
  Itemized, please.
  Italicized, please.
  Iterated, please.
  Itemize, please.
  Italicize, please.
  Iterate, please.

Expansions of "~/{Downloads,Pictures}/*.{jpg,gif,png}":
  ~/Downloads/*.jpg
  ~/Pictures/*.jpg
  ~/Downloads/*.gif
  ~/Pictures/*.gif
  ~/Downloads/*.png
  ~/Pictures/*.png

Expansions of "{,{,gotta have{ ,\, again\, }}more }cowbell!":
  cowbell!
  more cowbell!
  gotta have more cowbell!
  gotta have\, again\, more cowbell!

Expansions of "{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}":
  {}} some }{,{\\ edge \,}{ cases, {here} \\\\\}
  {}} some }{,{\\ edge \,}{ cases, {here} \\\\\}

Perl

Perl has a built-in glob function which does brace expansion, but it can't be used to solve this task because it also does shell-like word splitting, wildcard expansion, and tilde expansion at the same time. The File::Glob core module gives access to the more low-level bsd_glob function which actually supports exclusive brace expansion, however it does not comply with this task's specification when it comes to preserving backslashes and handling unbalanced brace characters.

So here is a manual solution that implements the specification precisely:

sub brace_expand {
    my $input = shift;
    my @stack = ([my $current = ['']]);
    
    while ($input =~ /\G ((?:[^\\{,}]++ | \\(?:.|\z))++ | . )/gx) {
        if ($1 eq '{') {
            push @stack, [$current = ['']];
        }
        elsif ($1 eq ',' && @stack > 1) {
            push @{$stack[-1]}, ($current = ['']);
        }
        elsif ($1 eq '}' && @stack > 1) {
            my $group = pop @stack;
            $current = $stack[-1][-1];
            
            # handle the case of brace pairs without commas:
            @{$group->[0]} = map { "{$_}" } @{$group->[0]} if @$group == 1;
            
            @$current = map {
                my $c = $_;
                map { map { $c . $_ } @$_ } @$group;
            } @$current;
        }
        else { $_ .= $1 for @$current; }
    }
    
    # handle the case of missing closing braces:
    while (@stack > 1) {
        my $right = pop @{$stack[-1]};
        my $sep;
        if (@{$stack[-1]}) { $sep = ',' }
        else               { $sep = '{'; pop @stack }
        $current = $stack[-1][-1];
        @$current = map {
            my $c = $_;
            map { $c . $sep . $_ } @$right;
        } @$current;
    }
    
    return @$current;
}

Usage demonstration:

while (my $input = <DATA>) {
    chomp($input);
    print "$input\n";
    print "    $_\n" for brace_expand($input);
    print "\n";
}

__DATA__
~/{Downloads,Pictures}/*.{jpg,gif,png}
It{{em,alic}iz,erat}e{d,}, please.
{,{,gotta have{ ,\, again\, }}more }cowbell!
{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}
Output:
~/{Downloads,Pictures}/*.{jpg,gif,png}
    ~/Downloads/*.jpg
    ~/Downloads/*.gif
    ~/Downloads/*.png
    ~/Pictures/*.jpg
    ~/Pictures/*.gif
    ~/Pictures/*.png

It{{em,alic}iz,erat}e{d,}, please.
    Itemized, please.
    Itemize, please.
    Italicized, please.
    Italicize, please.
    Iterated, please.
    Iterate, please.

{,{,gotta have{ ,\, again\, }}more }cowbell!
    cowbell!
    more cowbell!
    gotta have more cowbell!
    gotta have\, again\, more cowbell!

{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}
    {}} some }{,{\\ edge \,}{ cases, {here} \\\\\}
    {}} some }{,{\\ edge \,}{ cases, {here} \\\\\}

Phix

Fairly straightforward recursive solution

-- demo\rosetta\Brace_expansion.exw
with javascript_semantics
function pair(sequence stems, sequence brest)
    sequence res = {}
    for i=1 to length(stems) do
        for j=1 to length(brest) do
            res = append(res,stems[i]&brest[j])
        end for
    end for
    return res
end function

function brarse(string s)
    integer idx = 1
    while idx<=length(s) do
        integer ch = s[idx]
        if ch='{' then
            sequence alts = {idx}
            idx += 1
            integer l0 = idx
            bool nest = false, bl0 = false
            integer level = 1
            while idx<=length(s) do
                switch s[idx] do
                    case '{': level += 1
                              nest = true
                    case '}': level -= 1
                              bl0 = (level=0)
                    case ',': if level=1 then
                                alts = append(alts,idx)
                              end if
                    case '\\': idx += 1
                end switch
                if bl0 then exit end if
                idx += 1
            end while
            if length(alts)>1 and level=0 then
                alts &= idx
                sequence stems = {}
                string stem = s[1..alts[1]-1]
                for i=2 to length(alts) do
                    string rest = s[alts[i-1]+1..alts[i]-1]
                    if nest then
                        sequence inners = brarse(rest)
                        for j=1 to length(inners) do
                            stems = append(stems,stem&inners[j])
                        end for
                    else
                        stems = append(stems,stem&rest)
                    end if
                end for
                return pair(stems,brarse(s[idx+1..$]))
            elsif nest then
                return pair({s[1..l0-1]},brarse(s[l0..$]))
            end if
        end if
        idx += 1
    end while
    return {s}
end function

-- (since ? and pp() add their own backslash escapes:)
procedure edump(sequence x)
    for i=1 to length(x) do
        printf(1,"%s\n",{x[i]})
    end for
end procedure

edump(brarse("~/{Downloads,Pictures}/*.{jpg,gif,png}"))
edump(brarse("It{{em,alic}iz,erat}e{d,}, please."))
edump(brarse(`{,{,gotta have{ ,\, again\, }}more }cowbell!`))
edump(brarse(`{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}`))
Output:
~/Downloads/*.jpg
~/Downloads/*.gif
~/Downloads/*.png
~/Pictures/*.jpg
~/Pictures/*.gif
~/Pictures/*.png
Itemized, please.
Itemize, please.
Italicized, please.
Italicize, please.
Iterated, please.
Iterate, please.
cowbell!
more cowbell!
gotta have more cowbell!
gotta have\, again\, more cowbell!
{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}
{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}

PHP

Translation of: Python
function getitem($s,$depth=0) {
    $out = [''];
    while ($s) {
        $c = $s[0];
        if ($depth && ($c == ',' || $c == '}')) {
            return [$out, $s];
        }
        if ($c == '{') {
            $x = getgroup(substr($s, 1), $depth + 1);
            if($x) {
                $tmp = [];
                foreach($out as $a) {
                    foreach($x[0] as $b) { 
                        $tmp[] = $a . $b;
                    }
                }
                $out = $tmp;
                $s = $x[1];
                continue;
            }
        }
        if ($c == '\\' && strlen($s) > 1) {
            list($s, $c) = [substr($s, 1), ($c . $s[1])];
        }

        $tmp = [];
        foreach($out as $a) {
            $tmp[] = $a . $c;
        }
        $out = $tmp;
        $s = substr($s, 1);
        
    }
    return [$out, $s];
}
function getgroup($s,$depth) {
    list($out, $comma) = [[], false];
    while ($s) {
        list($g, $s) = getitem($s, $depth);
        if (!$s) {
            break;
        }
        $out = array_merge($out, $g);
        if ($s[0] == '}') {
            if ($comma) {
                return [$out, substr($s, 1)];
            }

            $tmp = [];
            foreach($out as $a) {
                $tmp[] = '{' . $a . '}';
            }
            return [$tmp, substr($s, 1)];
        }
        if ($s[0] == ',') {
            list($comma, $s) = [true, substr($s, 1)];
        }
    }
    return null;
}

$lines = <<< 'END'
~/{Downloads,Pictures}/*.{jpg,gif,png}
It{{em,alic}iz,erat}e{d,}, please.
{,{,gotta have{ ,\, again\, }}more }cowbell!
{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}
END;

foreach( explode("\n", $lines) as $line ) {
    printf("\n%s\n", $line);
    foreach( getitem($line)[0] as $expansion ) {
        printf("    %s\n", $expansion);
    }
}
Output:
~/{Downloads,Pictures}/*.{jpg,gif,png}
    ~/Downloads/*.jpg
    ~/Downloads/*.gif
    ~/Downloads/*.png
    ~/Pictures/*.jpg
    ~/Pictures/*.gif
    ~/Pictures/*.png

It{{em,alic}iz,erat}e{d,}, please.
    Itemized, please.
    Itemize, please.
    Italicized, please.
    Italicize, please.
    Iterated, please.
    Iterate, please.

{,{,gotta have{ ,\, again\, }}more }cowbell!
    cowbell!
    more cowbell!
    gotta have more cowbell!
    gotta have\, again\, more cowbell!

{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}
    {}} some }{,{\\ edge \,}{ cases, {here} \\\\\}
    {}} some }{,{\\ edge \,}{ cases, {here} \\\\\}

PicoLisp

(de braceExpand (Str)
   (let Lst
      (make
         (for (Lst (chop Str)  Lst)
            (case (pop 'Lst)
               ("\\" (link (pop 'Lst)))
               ("{"
                  (recur ()
                     (let L
                        (make
                           (while
                              (case (pop 'Lst)
                                 ("\\" (link (pop 'Lst)) Lst)
                                 ("{" (recurse) Lst)
                                 ("}" NIL)
                                 ("," (link 0) Lst)  # Replace commata with '0'
                                 (T (link @) Lst) ) ) )
                        (if (= "}" @)  # Was closing brace
                           (if (member 0 L)  # Has comma(ta)
                              (link (split L 0))
                              (chain (list "{") (replace L 0 ",") (list "}")))
                           (chain (list "{") (replace L 0 ",")) ) ) ) )
               (T (link @)) ) ) )
      (recur (Lst)
         (ifn (find pair Lst)
            (list (pack Lst))
            (let R (recurse (cdr Lst))
               (mapcan
                  '((A) (mapcar '((B) (pack A B)) R))
                  (if (pair (car Lst))
                     (mapcan recurse (car Lst))
                     (list (car Lst)) ) ) ) ) ) ) )

Test:

(test
   (quote
      "~/Downloads/*.jpg"
      "~/Downloads/*.gif"
      "~/Downloads/*.png"
      "~/Pictures/*.jpg"
      "~/Pictures/*.gif"
      "~/Pictures/*.png" )
   (braceExpand "~/{Downloads,Pictures}/*.{jpg,gif,png}") )

(test
   (quote
      "Itemized, please."
      "Itemize, please."
      "Italicized, please."
      "Italicize, please."
      "Iterated, please."
      "Iterate, please." )
   (braceExpand "It{{em,alic}iz,erat}e{d,}, please.") )

(test
   (quote
      "cowbell!"
      "more cowbell!"
      "gotta have more cowbell!"
      "gotta have\, again\, more cowbell!" )
   (braceExpand "{,{,gotta have{ ,\\, again\\, }}more }cowbell!") )

(test
   (quote
      "{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}"
      "{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}" )
   (braceExpand "{}} some }{,{\\\\{ edge, edge} \\,}{ cases, {here} \\\\\\\\\\}") )

PowerShell

Works with: PowerShell version 2
function Expand-Braces ( [string]$String )
    {
    $Escaped = $False
    $Stack = New-Object System.Collections.Stack
    $ClosedBraces = $BracesToParse = $Null
 
    ForEach ( $i in 0..($String.Length-1) )
        {
        Switch ( $String[$i] )
            {
            '\' {
                $Escaped = -not $Escaped
                break
                }
 
            '{' {
                If ( -not $Escaped ) { $Stack.Push( [pscustomobject]@{ Delimiters = @( $i ) } ) }
                }
 
            ',' {
                If ( -not $Escaped -and $Stack.Count ) { $Stack.Peek().Delimiters += $i }
                }
 
            '}' {
                If ( -not $Escaped -and $Stack.Count )
                    {
                    $Stack.Peek().Delimiters += $i
                    $ClosedBraces = $Stack.Pop()
                    If ( $ClosedBraces.Delimiters.Count -gt 2 )
                        {
                        $BracesToParse = $ClosedBraces
                        }
                    }
                }
 
            default { $Escaped = $False }
            }
        }
 
        If ( $BracesToParse )
            {
            $Start = $String.Substring( 0, $BracesToParse.Delimiters[0] )
            $End   = $String.Substring( $BracesToParse.Delimiters[-1] + 1 )
 
            ForEach ( $i in 0..($BracesToParse.Delimiters.Count-2) )
                {
                $Option = $String.Substring( $BracesToParse.Delimiters[$i] + 1, $BracesToParse.Delimiters[$i+1] - $BracesToParse.Delimiters[$i] - 1 )
                Expand-Braces ( $Start + $Option + $End )
                }
            }
        Else
            {
            $String
            }
    }
$TestStrings = @(
    'It{{em,alic}iz,erat}e{d,}, please.'
    '~/{Downloads,Pictures}/*.{jpg,gif,png}'
    '{,{,gotta have{ ,\, again\, }}more }cowbell!'
    '{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}'
    )
 
ForEach ( $String in $TestStrings )
    {
    ''
    $String
    '------'
    Expand-Braces $String
    }
Output:
It{{em,alic}iz,erat}e{d,}, please.
------
Itemized, please.
Italicized, please.
Iterated, please.
Itemize, please.
Italicize, please.
Iterate, please.

~/{Downloads,Pictures}/*.{jpg,gif,png}
------
~/Downloads/*.jpg
~/Pictures/*.jpg
~/Downloads/*.gif
~/Pictures/*.gif
~/Downloads/*.png
~/Pictures/*.png

{,{,gotta have{ ,\, again\, }}more }cowbell!
------
cowbell!
more cowbell!
gotta have more cowbell!
gotta have\, again\, more cowbell!

{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}
------
{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}
{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}

Prolog

sym(',', commalist) --> ['\\',','], !.
sym(H, Context)         --> [H], { not(H = '{'; H = '}'), (Context = commalist -> not(H = ','); true) }.
syms([H|T], Context)    --> sym(H, Context), !, syms(T, Context).
syms([], _)             --> [].
symbol(Symbol, Context) --> syms(Syms,Context), {atom_chars(Symbol, Syms)}.

braces(Member) --> ['{'], commalist(List), ['}'], {length(List, Len), Len > 1, member(Member, List)}.

commalist([H|T]) --> sym_braces(H, commalist), [','], commalist(T).
commalist([H]) --> sym_braces(H, commalist).

sym_braces(String, Context) --> symbol(S1, Context), braces(S2), sym_braces(S3, Context), {atomics_to_string([S1,S2,S3],String)}.
sym_braces(String, Context) --> braces(S1), symbol(S2, Context), sym_braces(S3, Context), {atomics_to_string([S1,S2,S3],String)}.
sym_braces(String, Context) --> symbol(String, Context).
sym_braces(String, _) --> braces(String).
sym_braces(String, Context) --> ['{'], sym_braces(S2, Context), {atomics_to_string(['{',S2],String)}.
sym_braces(String, Context) --> ['}'], sym_braces(S2, Context), {atomics_to_string(['}',S2],String)}.

grammar(String) --> sym_braces(String, braces).

brace_expansion(In, Out) :- atom_chars(In, Chars), findall(Out,grammar(Out, Chars, []), List), list_to_set(List, Out).

Testing:

?- brace_expansion("~/{Downloads,Pictures}/*.{jpg,gif,png}", Out).
Out = ["~/Downloads/*.jpg","~/Downloads/*.gif","~/Downloads/*.png","~/Pictures/*.jpg","~/Pictures/*.gif","~/Pictures/*.png"].

?- brace_expansion("It{{em,alic}iz,erat}e{d,}, please.", Out).
Out = ["Itemized, please.", "Itemize, please.", "Iterated, please.", "Iterate, please.", "Italicized, please.", "Italicize, please."].

?- brace_expansion("{,{,gotta have{ ,\\, again\\, }}more }cowbell!", Out).
Out = ["cowbell!", "more cowbell!", "gotta have more cowbell!", "gotta have, again, more cowbell!"].

Python

def getitem(s, depth=0):
    out = [""]
    while s:
        c = s[0]
        if depth and (c == ',' or c == '}'):
            return out,s
        if c == '{':
            x = getgroup(s[1:], depth+1)
            if x:
                out,s = [a+b for a in out for b in x[0]], x[1]
                continue
        if c == '\\' and len(s) > 1:
            s, c = s[1:], c + s[1]

        out, s = [a+c for a in out], s[1:]

    return out,s

def getgroup(s, depth):
    out, comma = [], False
    while s:
        g,s = getitem(s, depth)
        if not s: break
        out += g

        if s[0] == '}':
            if comma: return out, s[1:]
            return ['{' + a + '}' for a in out], s[1:]

        if s[0] == ',':
            comma,s = True, s[1:]

    return None

# stolen cowbells from Raku example
for s in '''~/{Downloads,Pictures}/*.{jpg,gif,png}
It{{em,alic}iz,erat}e{d,}, please.
{,{,gotta have{ ,\, again\, }}more }cowbell!
{}} some }{,{\\\\{ edge, edge} \,}{ cases, {here} \\\\\\\\\}'''.split('\n'):
    print "\n\t".join([s] + getitem(s)[0]) + "\n"
Output:
~/{Downloads,Pictures}/*.{jpg,gif,png}
        ~/Downloads/*.jpg
        ~/Downloads/*.gif
        ~/Downloads/*.png
        ~/Pictures/*.jpg
        ~/Pictures/*.gif
        ~/Pictures/*.png

It{{em,alic}iz,erat}e{d,}, please.
        Itemized, please.
        Itemize, please.
        Italicized, please.
        Italicize, please.
        Iterated, please.
        Iterate, please.

{,{,gotta have{ ,\, again\, }}more }cowbell!
        cowbell!
        more cowbell!
        gotta have more cowbell!
        gotta have\, again\, more cowbell!

{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}
        {}} some }{,{\\ edge \,}{ cases, {here} \\\\\}
        {}} some }{,{\\ edge \,}{ cases, {here} \\\\\}

Racket

Translation of: Python
#lang racket/base
(require racket/match)
(define (merge-lists as . bss)
  (match bss
    ['() as]
    [(cons b bt)
     (apply merge-lists
            (for*/list ((a (in-list as)) (b (in-list b))) (append a b))
            bt)]))

(define (get-item cs depth)
  (let loop ((out '(())) (cs cs))
    (match cs
      ['() (values out cs)]
      [`(,(or #\, #\}) . ,more) #:when (positive? depth) (values out cs)]
      [`(#\{ . ,more)
       (=> no-group-match)
       (define-values (group-out group-rem) (get-group more (add1 depth) no-group-match))
       (loop (merge-lists out group-out) group-rem)]
      [(or `(#\\ ,c ,more ...) `(,c . ,more)) (loop (merge-lists out (list (list c))) more)])))

(define (get-group cs depth no-group-match)
  (let loop ((out '()) (cs cs) (comma? #f))
    (when (null? cs) (no-group-match))
    (define-values (item-out item-rem) (get-item cs depth))
    (when (null? item-rem) (no-group-match))
    (let ((out (append out item-out)))
      (match item-rem
        [`(#\} . ,more) #:when comma? (values out more)]
        [`(#\} . ,more) (values (merge-lists '((#\{)) out '((#\}))) more)]
        [`(#\, . ,more) (loop out more #t)]
        [_ (no-group-match)]))))

(define (brace-expand s)
  (let-values (([out rem] (get-item (string->list s) 0))) (map list->string out)))

(module+ test
  (define patterns
    (list
     "~/{Downloads,Pictures}/*.{jpg,gif,png}"
     "It{{em,alic}iz,erat}e{d,}, please."
     #<<P
{,{,gotta have{ ,\, again\, }}more }cowbell!
P
     #<<P
{}} some }{,{\\\\{ edge, edge} \,}{ cases, {here} \\\\\\\\\}
P
     ))
  (for ((s (in-list patterns)) #:when (printf "expand: ~a~%" s) (x (in-list (brace-expand s))))
    (printf "\t~a~%" x)))
Output:
expand: ~/{Downloads,Pictures}/*.{jpg,gif,png}
	~/Downloads/*.jpg
	~/Downloads/*.gif
	~/Downloads/*.png
	~/Pictures/*.jpg
	~/Pictures/*.gif
	~/Pictures/*.png
expand: It{{em,alic}iz,erat}e{d,}, please.
	Itemized, please.
	Itemize, please.
	Italicized, please.
	Italicize, please.
	Iterated, please.
	Iterate, please.
expand: {,{,gotta have{ ,\, again\, }}more }cowbell!
	cowbell!
	more cowbell!
	gotta have more cowbell!
	gotta have, again, more cowbell!
expand: {}} some }{,{\\\\{ edge, edge} \,}{ cases, {here} \\\\\\\\\}
	{}} some }{,{\\ edge ,}{ cases, {here} \\\\}
	{}} some }{,{\\ edge ,}{ cases, {here} \\\\}

Raku

(formerly Perl 6) The task description allows the taking of shortcuts, but please note that we are not taking any shortcuts here. The solution is short because this particular problem happens to map quite naturally to the strengths of Raku.

First, the parsing is handled with a grammar that can backtrack in the few places this problem needs it. The + quantifier matches one or more alternatives (we handle the case of a single alternative in the walk now), and the % modifier requires a comma between each quantified item to its left. Note that the * quantifiers do not backtrack here, because the token keyword suppresses that; all the backtracking here fails over to a different alternative in an outer alternation (that is, things separated by the | character in the grammar. Most of these failovers just nibble an uninteresting character and continue.)

On the other end, we recursively walk the parse tree returning expanded sublists, and we do the cartesian concatenation of sublists at each level by use of the X~ operator, which is a "cross" metaoperator used on a simple ~ concatenation. As a list infix operator, X~ does not care how many items are on either side, which is just what you want in this case, since some of the arguments are strings and some are lists. Here we use a fold or reduction form in square brackets to interpose the cross-concat between each value generated by the map, which returns a mixture of lists and literal strings. One other thing that might not be obvious: if we bind to the match variable, $/, we automatically get all the syntactic sugar for its submatches. In this case, $0 is short for $/[0], and represents all the submatches captured by 0th set of parens in either TOP or alt. $<meta> is likewise short for $/<meta>, and retrieves what was captured by that named submatch.

grammar BraceExpansion {
    token TOP  { ( <meta> | . )* }
    token meta { '{' <alts> '}' | \\ .  }
    token alts { <alt>+ % ',' }
    token alt  { ( <meta> | <-[ , } ]> )* }
}

sub crosswalk($/) {
    |[X~] flat '', $0.map: -> $/ { $<meta><alts><alt>.&alternatives or ~$/ }
}

sub alternatives($_) {
    when :not { () }
    when 1    { '{' X~ $_».&crosswalk X~ '}' }
    default   { $_».&crosswalk }
}

sub brace-expand($s) { crosswalk BraceExpansion.parse($s) }

# Testing:

sub bxtest(*@s) {
    for @s -> $s {
        say "\n$s";
        for brace-expand($s) {
            say "    ", $_;
        }
    }
}

bxtest Q:to/END/.lines;
    ~/{Downloads,Pictures}/*.{jpg,gif,png}
    It{{em,alic}iz,erat}e{d,}, please.
    {,{,gotta have{ ,\, again\, }}more }cowbell!
    a{b{1,2}c
    a{1,2}b}c
    a{1,{2},3}b
    more{ darn{ cowbell,},}
    ab{c,d\,e{f,g\h},i\,j{k,l\,m}n,o\,p}qr
    {a,{\,b}c
    a{b,{{c}}
    {a{\}b,c}d
    END
Output:
~/{Downloads,Pictures}/*.{jpg,gif,png}
    ~/Downloads/*.jpg
    ~/Downloads/*.gif
    ~/Downloads/*.png
    ~/Pictures/*.jpg
    ~/Pictures/*.gif
    ~/Pictures/*.png

It{{em,alic}iz,erat}e{d,}, please.
    Itemized, please.
    Itemize, please.
    Italicized, please.
    Italicize, please.
    Iterated, please.
    Iterate, please.

{,{,gotta have{ ,\, again\, }}more }cowbell!
    cowbell!
    more cowbell!
    gotta have more cowbell!
    gotta have\, again\, more cowbell!

{}} some {\\{edge,edgy} }{ cases, here\\\}
    {}} some {\\edge }{ cases, here\\\}
    {}} some {\\edgy }{ cases, here\\\}

a{b{1,2}c
    a{b1c
    a{b2c

a{1,2}b}c
    a1b}c
    a2b}c

a{1,{2},3}b
    a1b
    a{2}b
    a3b

more{ darn{ cowbell,},}
    more darn cowbell
    more darn
    more

ab{c,d\,e{f,g\h},i\,j{k,l\,m}n,o\,p}qr
    abcqr
    abd\,efqr
    abd\,eg\hqr
    abi\,jknqr
    abi\,jl\,mnqr
    abo\,pqr

{a,{\,b}c
    {a,{\,b}c

a{b,{{c}}
    a{b,{{c}}

{a{\}b,c}d
    {a\}bd
    {acd

REXX

/*- REXX --------------------------------------------------------------
* Brace expansion
* 26.07.2016
* s.* holds the set of strings
*--------------------------------------------------------------------*/
text.1='{,{,gotta have{ ,\, again\, }}more }cowbell!'
text.2='~/{Downloads,Pictures}/*.{jpg,gif,png}'
text.3='It{{em,alic}iz,erat}e{d,}, please. '
text.4='{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\} '
text.5='x{,a,b,c}{d,e}y'
text.6='aa{,{,11}cc}22'
text.7='{}'
Parse Arg dbg
oid='brace.xxx'; 'erase' oid
Do case=1 To 7
  Call brac text.case
  End
Return
brac:
  s.=0
  Parse Arg s
  Say ''
  Say '  's
  s.1.0=1                            /* first iteration              */
  s.1.1=s                            /* the initial string           */
  Do it=1 To 10 Until todo=0         /* Iterate until all done       */
    todo=0                           /* will be 1 if more to be done */
    Call dbg 'Iteration' it
    do di=1 To s.it.0                /* show current state           */
      Call dbg 's.'it'.'di  s.it.di
      End
    ita=it+1                         /* index for next set of strings*/
    xp=0
    do di=1 To s.it.0                /* loop over all strings        */
      Call dbg it'.'di s.it.di
      Call bra s.it.di               /* analyze current string       */
      If braces=1 Then Do            /* If brace groups were found   */
        Do bgi=1 To bgdata.0         /* loop over grace groups       */
          If end.bgi=0 Then Iterate  /* Incomplete bg (... )         */
          clist=''
          Do cj=1 To ci.bgi.0
            clist=clist ci.bgi.cj
            End
          Call dbg bgdata.bgi '->' clist
          If ccount.bgi>0 Then Do    /* comma(s) founf in bg         */
            Call expand bgi          /* expand this bg               */
            xp=1                     /* indicate that we worked      */
            Leave
            End
          End
        If xp=0 Then Do              /* nothing done                 */
          z=s.ita.0+1                /* copy string to next iteration*/
          s.ita.z=s.it.di
          End
        End
      Else Do                        /* no brace group               */
        z=s.ita.0+1                  /* copy string to next iteration*/
        s.ita.z=s
        s.ita.0=z
        End
      End
    Do dd=1 To s.ita.0               /* log current set of strings   */
      Call dbg ita dd s.ita.dd
      End
    End
  Do dd=1 To s.it.0                  /* show final set of strings    */
    Say dd s.it.dd
    End
  Return

bra:
/*---------------------------------------------------------------------
* Analyze the given string
* Input: s
* Output:
* bgdata.*  Array of data about brace groups:
*                      level start column comma positions end column
*--------------------------------------------------------------------*/
parse Arg s
Call dbg 'bra:' s
level=0
bgdata.=0
bgn=0
bgnmax=0
ccount.=0
ol=''
ci.=0
bgnl=''
braces=0
end.=0
escape=0
Do i=1 To length(s)
  c=substr(s,i,1)
  Select
    When escape Then
      escape=0
    When c='\' Then
      escape=1
    When c='{' Then Do
      level=level+1
      Call bm c
      co=level
      End
    When c='}' Then Do
      If level>0 Then Do
        co=level
        Call bm c
        level=level-1
        End
      End
    When c=',' Then Do
      co=level
      If co>0 Then Do
        ccount.bgn=ccount.bgn+1
        z=ccount.bgn
        ci.bgn.0=z
        ci.bgn.z=i
        End
      If ccount.bgn>0 Then
        braces=1
      End
    Otherwise
      co=level
    End
  ol=ol||co
  bgnl=bgnl||bgn
  End
Call dbg s
Call dbg ol
Call dbg left(copies('123456789.',10),length(s))
Call dbg bgnl
Do bgi=1 To bgdata.0
  If end.bgi=1 Then Do
    cl=''
    Do cii=1 To ci.bgi.0
      cl=cl ci.bgi.cii
      End
    Parse Var bgdata.bgi level a e
    Call dbg bgi level a cl e
    End
  End
Return

bm:
/*---------------------------------------------------------------------
* Brace Management
* for '{' create a new brace group )record level and start column
* for '}' look for corresponding bg and add end column
* Input: column and character ( '{' or '}' )
* Output: bgdata.*  level start-column [end-column]
*--------------------------------------------------------------------*/
  Parse Arg oc
  Call dbg oc i level
  If oc='{' Then Do
    z=bgdata.0+1
    bgdata.z=level i
    bgdata.0=z
    bgn=bgnmax+1
    bgnmax=bgn
    End
  Else Do
    Do bgi=bgdata.0 To 1 By -1
      If level=word(bgdata.bgi,1) Then Do
        bgdata.bgi=bgdata.bgi i
        end.bgi=1
        Leave
        End
      End
    bgn=bgn-1
    Call dbg bgdata.bgi 'bgn='bgn
    End
  Return

expand:
/*---------------------------------------------------------------------
* Expand a brace group in string s
*--------------------------------------------------------------------*/
  Parse Arg bgi
  Parse Var bgdata.bgi . start end
  clist=start clist end
  If words(clist)>0 Then Do          /* commas in brace group        */
    left=left(s,start-1)             /* part of s before the '{'     */
    rite=substr(s,end+1)             /* part of s after the '}'      */
    Do k=1 To words(clist)-1         /* Loop over comma positions    */
      a=word(clist,k)                /* start position               */
      e=word(clist,k+1)              /* end position                 */
      choice.k=substr(s,a+1,e-a-1)   /* one of the choices           */
      z=s.ita.0+1                    /* add new string to next set   */
      s.ita.z=left||choice.k||rite   /* construct new string         */
      s.ita.0=z
      todo=1                         /* maybe more to be done        */
      End
    End
  Else Do                            /* no commas                    */
    z=s.ita.0+1                      /* copy string as is to next set*/
    s.ita.z=s
    s.ita.0=z
    End
  Do zz=1 To s.ita.0
    Call dbg zz s.ita.zz
    End
  Return

dbg:                                 /* handle debug output          */
  If dbg<>'' Then                    /* argument given               */
    Say arg(1)                       /* show on screen               */
  Call lineout oid,arg(1)            /* write to file                */
  Return
Output:
J:\>rexx braces

  {,{,gotta have{ ,\, again\, }}more }cowbell!
1 cowbell!
2 more cowbell!
3 gotta have more cowbell!
4 gotta have\, again\, more cowbell!

  ~/{Downloads,Pictures}/*.{jpg,gif,png}
1 ~/Downloads/*.jpg
2 ~/Downloads/*.gif
3 ~/Downloads/*.png
4 ~/Pictures/*.jpg
5 ~/Pictures/*.gif
6 ~/Pictures/*.png

  It{{em,alic}iz,erat}e{d,}, please.
1 Itemized, please.
2 Itemize, please.
3 Italicized, please.
4 Italicize, please.
5 Iterated, please.
6 Iterate, please.

  {}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}
1 {}} some }{,{\\ edge \,}{ cases, {here} \\\\\}
2 {}} some }{,{\\ edge \,}{ cases, {here} \\\\\}

  x{,a,b,c}{d,e}y
1 xdy
2 xey
3 xady
4 xaey
5 xbdy
6 xbey
7 xcdy
8 xcey

  aa{,{,11}cc}22
1 aa22
2 aacc22
3 aa11cc22

  {}
1 {}

Ruby

Translation of: Python
def getitem(s, depth=0)
  out = [""]
  until s.empty?
    c = s[0]
    break  if depth>0 and (c == ',' or c == '}')
    if c == '{' and x = getgroup(s[1..-1], depth+1)
      out = out.product(x[0]).map{|a,b| a+b}
      s = x[1]
    else
      s, c = s[1..-1], c + s[1]  if c == '\\' and s.size > 1
      out, s = out.map{|a| a+c}, s[1..-1]
    end
  end
  return out, s
end

def getgroup(s, depth)
  out, comma = [], false
  until s.empty?
    g, s = getitem(s, depth)
    break  if s.empty?
    out += g
    case s[0]
      when '}' then return (comma ? out : out.map{|a| "{#{a}}"}), s[1..-1]
      when ',' then comma, s = true, s[1..-1]
    end
  end
end

strs = <<'EOS'
~/{Downloads,Pictures}/*.{jpg,gif,png}
It{{em,alic}iz,erat}e{d,}, please.
{,{,gotta have{ ,\, again\, }}more }cowbell!
{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}
EOS

strs.each_line do |s|
  puts s.chomp!
  puts getitem(s)[0].map{|str| "\t"+str}
  puts
end
Output:
~/{Downloads,Pictures}/*.{jpg,gif,png}
	~/Downloads/*.jpg
	~/Downloads/*.gif
	~/Downloads/*.png
	~/Pictures/*.jpg
	~/Pictures/*.gif
	~/Pictures/*.png

It{{em,alic}iz,erat}e{d,}, please.
	Itemized, please.
	Itemize, please.
	Italicized, please.
	Italicize, please.
	Iterated, please.
	Iterate, please.

{,{,gotta have{ ,\, again\, }}more }cowbell!
	cowbell!
	more cowbell!
	gotta have more cowbell!
	gotta have\, again\, more cowbell!

{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}
	{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}
	{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}

Rust

const OPEN_CHAR: char = '{';
const CLOSE_CHAR: char = '}';
const SEPARATOR: char = ',';
const ESCAPE: char = '\\';

#[derive(Debug, PartialEq, Clone)]
enum Token {
    Open,
    Close,
    Separator,
    Payload(String),
    Branches(Branches),
}

impl From<char> for Token {
    fn from(ch: char) -> Token {
        match ch {
            OPEN_CHAR => Token::Open,
            CLOSE_CHAR => Token::Close,
            SEPARATOR => Token::Separator,
            _ => panic!("Non tokenizable char!"),
        }
    }
}

#[derive(Debug, PartialEq, Clone)]
struct Branches {
    tokens: Vec<Vec<Token>>,
}

impl Branches {
    fn new() -> Branches {
        Branches{
            tokens: Vec::new(),
        }
    }

    fn add_branch(&mut self, branch: Vec<Token>) {
        self.tokens.push(branch);
    }

    fn from(tokens: &Vec<Token>) -> Branches {
        let mut branches = Branches::new();
        let mut tail = tokens.clone();
        while let Some(pos) = tail.iter().position(|token| { *token == Token::Separator }) {
            let mut rest = tail.split_off(pos);
            branches.add_branch(tail);
            rest.remove(0);
            tail = rest;
        }
        branches.add_branch(tail);
        branches
    }
}

impl From<Branches> for Token {
    fn from(branches: Branches) -> Token {
        Token::Branches(branches)
    }
}

impl From<Vec<Token>> for Branches {
    fn from(tokens: Vec<Token>) -> Branches {
        Branches::from(&tokens)
    }
}

impl From<Token> for String {
    fn from(token: Token) -> String {
        match token {
            Token::Branches(_) => panic!("Cannot convert to String!"),
            Token::Payload(text) => text,
            Token::Open => OPEN_CHAR.to_string(),
            Token::Close => CLOSE_CHAR.to_string(),
            Token::Separator => SEPARATOR.to_string(),
        }
    }
}

impl From<Branches> for Vec<String> {
    fn from(branches: Branches) -> Vec<String> {
        let Branches{ tokens: token_lines } = branches;
        let mut vec: Vec<String> = Vec::new();
        let braces = { if token_lines.len() == 1 { true } else { false } };
        for tokens in token_lines {
            let mut vec_string = output(tokens);
            vec.append(&mut vec_string);
        }
        if braces {
            vec.iter()
                .map(|line| {
                    format!("{}{}{}", OPEN_CHAR, line, CLOSE_CHAR)
                }).
                collect::<Vec<String>>()
        } else {
            vec
        }
    }
}

impl From<Token> for Vec<String> {
    fn from(token: Token) -> Vec<String> {
        match token {
            Token::Branches(branches) => {
                branches.into()
            },
            _ => {
                let frag: String = token.into();
                vec![frag]
            },
        }
    }
}

fn tokenize(string: &str) -> Vec<Token> {
    let mut tokens: Vec<Token> = Vec::new();
    let mut chars = string.chars();
    let mut payload = String::new();
    while let Some(ch) = chars.next() {
        match ch {
            OPEN_CHAR | SEPARATOR | CLOSE_CHAR => {
                if payload.len() > 0 {
                    tokens.push(Token::Payload(payload));
                }
                payload = String::new();
                if ch == CLOSE_CHAR {
                    let pos = tokens.iter().rposition(|token| *token == Token::Open);
                    if let Some(pos) = pos {
                        let branches: Branches = {
                            let mut to_branches = tokens.split_off(pos);
                            to_branches.remove(0);
                            to_branches
                        }.into();
                        tokens.push(branches.into());
                    } else {
                        tokens.push(ch.into());
                    }
                } else {
                    tokens.push(ch.into());
                }
            },
            ESCAPE => {
                payload.push(ch);
                if let Some(next_char) = chars.next() {
                    payload.push(next_char);
                }
            },
            _ => payload.push(ch),
        }
    }
    let payload = payload.trim_end();
    if payload.len() > 0 {
        tokens.push(Token::Payload(payload.into()));
    }
    tokens
}

fn output(tokens: Vec<Token>) -> Vec<String> {
    let mut output: Vec<String> = vec![String::new()];
    for token in tokens {
        let mut aux: Vec<String> = Vec::new();
        let strings: Vec<String> = token.into();
        for root in &output {
            for string in &strings {
                aux.push({format!("{}{}", root, string)});
            }
        }
        output = aux;
    }
    output
}

fn main() {
    let mut input: String = String::new();
    std::io::stdin().read_line(&mut input).unwrap();

    let tokens: Vec<Token> = tokenize(&input);
    // println!("Tokens:\n{:#?}", tokens);

    let output = output(tokens);
    for line in &output {
        println!("{}", line);
    }
}


Output:
INPUT -> ~/{Downloads,Pictures}/*.{jpg,gif,png}
~/Downloads/*.jpg
~/Downloads/*.gif
~/Downloads/*.png
~/Pictures/*.jpg
~/Pictures/*.gif
~/Pictures/*.png

INPUT -> It{{em,alic}iz,erat}e{d,}, please.
Itemized, please.
Itemize, please.
Italicized, please.
Italicize, please.
Iterated, please.
Iterate, please.

INPUT -> {,{,gotta have{ ,\, again\, }}more }cowbell!
cowbell!
more cowbell!
gotta have more cowbell!
gotta have\, again\, more cowbell!

INPUT -> {}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}
{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}
{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}



Translation of: Python
fn main() {
    let input = "~/{Downloads,Pictures}/*.{jpg,gif,png}
It{{em,alic}iz,erat}e{d,}, please.
{,{,gotta have{ ,\\, again\\, }}more }cowbell!
{}} some }{,{\\\\{ edge, edge} \\,}{ cases, {here} \\\\\\\\\\}";

    for line in input.split("\n") {
        println!("{}", line);
        for line in get_item(line, 0).0 {
            println!("\t{}", line);
        }
    }
}

fn get_item(s: &str, depth: usize) -> (Vec<String>, &str) {
    let mut out = vec![String::new()];
    let mut s = s;
    while !s.is_empty() {
        let mut c = s.chars().nth(0).unwrap().to_string();
        if depth > 0 && (c == "," || c == "}") {
            return (out, s);
        }
        if c == "{" {
            let x = get_group(&s[1..], depth + 1);
            if x.is_some() {
                let (items, s_new) = x.unwrap();
                out = out
                    .iter()
                    .map(|out_item| {
                        items
                            .iter()
                            .map(|item| format!("{}{}", out_item, item))
                            .collect::<Vec<String>>()
                    })
                    .flatten()
                    .collect();
                s = s_new;
                continue;
            }
        }
        if c == "\\" && s.len() > 1 {
            s = &s[1..];
            c.push(s.chars().nth(0).unwrap());
        }
        out = out
            .iter()
            .map(|o| [o, &c[..]].concat())
            .collect::<Vec<String>>();
        s = &s[1..];
    }
    (out, s)
}

fn get_group(s: &str, depth: usize) -> Option<(Vec<String>, &str)> {
    let mut out: Vec<String> = vec![];
    let mut comma = false;
    let mut s = s;
    while !s.is_empty() {
        let (g, new_s) = get_item(s, depth);
        s = new_s;
        if s.is_empty() {
            break;
        }
        out.extend(g);
        if s.chars().nth(0).unwrap() == '}' {
            if comma {
                return Some((out, &s[1..]));
            }
            return Some((
                out.iter().map(|item| format!("{{{}}}", item)).collect(),
                &s[1..],
            ));
        }
        if s.chars().nth(0).unwrap() == ',' {
            comma = true;
            s = &s[1..];
        }
    }
    None
}
Output:
~/{Downloads,Pictures}/*.{jpg,gif,png}
	~/Downloads/*.jpg
	~/Downloads/*.gif
	~/Downloads/*.png
	~/Pictures/*.jpg
	~/Pictures/*.gif
	~/Pictures/*.png
It{{em,alic}iz,erat}e{d,}, please.
	Itemized, please.
	Itemize, please.
	Italicized, please.
	Italicize, please.
	Iterated, please.
	Iterate, please.
{,{,gotta have{ ,\, again\, }}more }cowbell!
	cowbell!
	more cowbell!
	gotta have more cowbell!
	gotta have\, again\, more cowbell!
{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}
	{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}
	{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}

Scala

Works with: Scala version 2.11
import collection.mutable.ListBuffer
case class State(isChild: Boolean, alts: ListBuffer[String], rem: List[Char])
def expand(s: String): Seq[String] = {
  def parseGroup(s: State): State = s.rem match {
    case Nil =>  s.copy(alts = ListBuffer("{" + s.alts.mkString(",")))
    case ('{' | ',')::sp =>
      val newS = State(true, ListBuffer(""), rem = sp)
      val elem = parseElem(newS)
      elem.rem match {
        case Nil =>     elem.copy(alts = elem.alts.map(a => "{" + s.alts.map(_ + ",").mkString("") + a))
        case elemrem => parseGroup(s.copy(alts = (s.alts ++= elem.alts), rem = elem.rem))
      }
    case '}'::sp =>
      if (s.alts.isEmpty)          s.copy(alts = ListBuffer("{}"), rem = sp)
      else if(s.alts.length == 1)  s.copy(alts = ListBuffer("{"+s.alts.head + "}"), rem = sp)
      else                         s.copy(rem = sp)
    case _ => throw new Exception("parseGroup should be called only with delimitors")
  }
  def parseElem(s: State): State = s.rem match {
    case Nil =>  s
    case '{'::sp =>
      val ys = parseGroup(State(true, ListBuffer(), s.rem))
      val newAlts = for { x <- s.alts; y <- ys.alts} yield x + y
      parseElem(s.copy(alts = newAlts, rem = ys.rem))
    case (',' | '}')::_ if s.isChild => s
    case '\\'::c::sp => parseElem(s.copy(alts = s.alts.map(_ + '\\' + c), rem = sp))
    case c::sp =>       parseElem(s.copy(alts = s.alts.map(_ + c), rem = sp))
  }
  parseElem(State(false, ListBuffer(""), s.toList)).alts
}

Demonstrating:

println(expand("""~/{Downloads,Pictures}/*.{jpg,gif,png}""") mkString "\n")
println(expand("It{{em,alic}iz,erat}e{d,}, please.") mkString "\n")
println(expand("""{,{,gotta have{ ,\, again\, }}more }cowbell!""") mkString "\n")
println(expand("""{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}""") mkString "\n")
Output:
~/Downloads/*.jpg
~/Downloads/*.gif
~/Downloads/*.png
~/Pictures/*.jpg
~/Pictures/*.gif
~/Pictures/*.png
Itemized, please.
Itemize, please.
Italicized, please.
Italicize, please.
Iterated, please.
Iterate, please.
cowbell!
more cowbell!
gotta have more cowbell!
gotta have\, again\, more cowbell!
{}} some }{,\\ edge \,{ cases, {here} \\\\\}
{}} some }{,\\ edge \,{ cases, {here} \\\\\}

Scheme

(define (parse-brackets str)
  ;; We parse the bracketed strings using an accumulator and a stack
  ;;
  ;; lst is the stream of tokens
  ;; acc is the accumulated list of "bits" in this branch
  ;; stk is a list of partially completed accumulators
  ;;
  (let go ((lst (string->list str))
           (acc '())
           (stk '()))
    (cond ((null? lst)
           (unless (null? stk)
             (error "parse-brackets" 'non-empty-stack))
           (comma-sep acc))
          ((eq? (car lst) #\{)
           (go (cdr lst)
               '()
               (cons acc stk)))
          ((eq? (car lst) #\})
           (when (null? stk)
             (error "parse-brackets" 'empty-stack))
           (go (cdr lst)
               (cons (comma-sep acc) (car stk))
               (cdr stk)))
          (else
           (go (cdr lst)
               (cons (car lst) acc)
               stk)))))

(define (comma-sep lst)
  ;; This function is applied to the accumulator, it does three things:
  ;; - it reverses the list
  ;; - joins characters into short strings
  ;; - splits the strings based on commas
  ;;
  (let go ((lst lst)
           (acc '())
           (rst '()))
    (if (null? lst)
        (cons (list->string acc) rst)
        (cond ((eq? #\, (car lst))
               (go (cdr lst)
                   '()
                   (cons (list->string acc) rst)))
              ((char? (car lst))
               (go (cdr lst)
                   (cons (car lst) acc)
                   rst))
              (else
               (go (cdr lst)
                   '()
                   (cons (car lst)
                         (cons (list->string acc)
                               rst))))))))

;; We use the list monad for the nondeterminism needed to expand out every possible bracket option

(define (concatenate lists)
  (apply append lists))

(define (return x)
  (list x))
(define (>>= l f)
  (concatenate (map f l)))

(define (sequence lsts)
  (if (null? lsts)
      (return '())
      (>>= (car lsts)
           (lambda (option)
             (>>= (sequence (cdr lsts))
                  (lambda (tail)
                    (return (cons option tail))))))))

(define (expand-inner tree)
  (if (string? tree)
      (return tree)
      (>>= tree
           (lambda (option)
             (expand-inner option)))))

(define (expand tree)
  (define (string-append* lst) (apply string-append lst))
  (map string-append* (sequence (map expand-inner tree))))

(define (bracket-expand str)
  (expand (parse-brackets str)))

(bracket-expand "It{{em,alic}iz,erat}e{d,}")
;; '("Ited" "Ite" "Itemed" "Iteme" "Italiced" "Italice" "Itized" "Itize" "Iterated" "Iterate")

Seed7

$ include "seed7_05.s7i";

const proc: expandBraces (in string: stri) is func
  local
    var boolean: escaped is FALSE;
    var integer: depth is 0;
    var array integer: bracePoints is 0 times 0;
    var array integer: bracesToParse is 0 times 0;
    var string: prefix is "";
    var string: suffix is "";
    var string: option is "";
    var integer: idx is 0;
  begin
    for key idx range stri do
      case stri[idx] of
        when {'\\'}:
          escaped := not escaped;
        when {'{'}:
          incr(depth);
          if not escaped and depth = 1 then
            bracePoints := [] (idx);
          end if;
        when {','}:
          if not escaped and depth = 1 then
            bracePoints &:= idx;
          end if;
        when {'}'}:
          if not escaped and depth = 1 and length(bracePoints) >= 2 then
            bracesToParse := bracePoints & [] (idx);
          end if;
          decr(depth);
      end case;
      if stri[idx] <> '\\' then
        escaped := FALSE;
      end if;
    end for;
    if length(bracesToParse) <> 0 then
      prefix := stri[.. pred(bracesToParse[1])];
      suffix := stri[succ(bracesToParse[length(bracesToParse)]) ..];
      for idx range 1 to pred(length(bracesToParse)) do
        option := stri[succ(bracesToParse[idx]) .. pred(bracesToParse[succ(idx)])];
        expandBraces(prefix & option & suffix);
      end for;
    else
      writeln(stri);
    end if;
  end func;

const proc: main is func
  local
    var string: stri is "";
  begin
    for stri range [] ("It{{em,alic}iz,erat}e{d,}, please.",
                       "~/{Downloads,Pictures}/*.{jpg,gif,png}",
                       "{,{,gotta have{ ,\\, again\\, }}more }cowbell!",
                       "{}} some }{,{\\\\{ edge, edge} \\,}{ cases, {here} \\\\\\\\\\}") do
      writeln;
      expandBraces(stri);
    end for;
  end func;
Output:

Itemized, please.
Italicized, please.
Iterated, please.
Itemize, please.
Italicize, please.
Iterate, please.

~/Downloads/*.jpg
~/Pictures/*.jpg
~/Downloads/*.gif
~/Pictures/*.gif
~/Downloads/*.png
~/Pictures/*.png

cowbell!
more cowbell!
gotta have more cowbell!
gotta have\, again\, more cowbell!

{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}
{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}

Sidef

Translation of: Perl
func brace_expand (input) {
    var current = ['']
    var stack = [[current]]

    loop {
        var t = input.match(
            /\G ((?:[^\\{,}]++ | \\(?:.|\z))++ | . )/gx
        )[0] \\ break

        if (t == '{') {
            stack << [current = ['']]
        }
        elsif ((t == ',') && (stack.len > 1)) {
            stack[-1] << (current = [''])
        }
        elsif ((t == '}') && (stack.len > 1)) {
            var group = stack.pop
            current   = stack[-1][-1]

            # handle the case of brace pairs without commas:
            group[0][] = group[0].map{ '{'+_+'}' }... if (group.len == 1)

            current[] = current.map { |c|
                group.map { .map { c + _ }... }...
            }...
        }
        else {
            current[] = current.map { _ + t }...
        }
    }

    # handle the case of missing closing braces:
    while (stack.len > 1) {

        var right = stack[-1].pop
        var sep = ','

        if (stack[-1].is_empty) {
            sep = '{'
            stack.pop
        }

        current = stack[-1][-1]
        current[] = current.map  { |c|
            right.map { c + sep + _ }...
        }...
    }

    return current
}

DATA.each { |line|
    say line
    brace_expand(line).each { "\t#{_}".say }
    say ''
}

__DATA__
~/{Downloads,Pictures}/*.{jpg,gif,png}
It{{em,alic}iz,erat}e{d,}, please.
{,{,gotta have{ ,\, again\, }}more }cowbell!
{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}
Output:
~/{Downloads,Pictures}/*.{jpg,gif,png}
	~/Downloads/*.jpg
	~/Downloads/*.gif
	~/Downloads/*.png
	~/Pictures/*.jpg
	~/Pictures/*.gif
	~/Pictures/*.png

It{{em,alic}iz,erat}e{d,}, please.
	Itemized, please.
	Itemize, please.
	Italicized, please.
	Italicize, please.
	Iterated, please.
	Iterate, please.

{,{,gotta have{ ,\, again\, }}more }cowbell!
	cowbell!
	more cowbell!
	gotta have more cowbell!
	gotta have\, again\, more cowbell!

{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}
	{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}
	{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}

Simula

Translation of: Python
CLASS ARRAYLISTS;
BEGIN

   CLASS ITEM;;

   CLASS ITEMARRAY(N); INTEGER N;
   BEGIN
      REF(ITEM) ARRAY DATA(1:N);
   !  OUTTEXT("NEW ITEMARRAY WITH ");!OUTINT(N, 0);!OUTTEXT(" ELEMENTS");
   !  OUTIMAGE;
   END;

   CLASS ARRAYLIST;
   BEGIN

      PROCEDURE EXPAND(N); INTEGER N;
      BEGIN
         INTEGER I;
         REF(ITEMARRAY) TEMP;
      !  OUTTEXT("EXPAND TO CAPACITY ");!OUTINT(N, 0);!OUTIMAGE;
         TEMP :- NEW ITEMARRAY(N);
         FOR I := 1 STEP 1 UNTIL SIZE DO
            TEMP.DATA(I) :- ITEMS.DATA(I);
         ITEMS :- TEMP;
      END;

      PROCEDURE ADD(T); REF(ITEM) T;
      BEGIN
         IF SIZE + 1 > CAPACITY THEN
         BEGIN
            CAPACITY := 2 * CAPACITY;
            EXPAND(CAPACITY);
         END;
         SIZE := SIZE + 1;
         ITEMS.DATA(SIZE) :- T;
      !  OUTTEXT("SIZE IS ");!OUTINT(SIZE, 0);!OUTIMAGE;
      END;

      PROCEDURE REMOVE(I); INTEGER I;
      BEGIN
        INTEGER J;
        IF I < 1 OR I > SIZE THEN ERROR("REMOVE: INDEX OUT OF BOUNDS");
        FOR J := I STEP 1 UNTIL SIZE - 1 DO
          ITEMS.DATA(J) :- ITEMS.DATA(J + 1);
        ITEMS.DATA(SIZE) :- NONE;
        SIZE := SIZE - 1;
      END;

      REF(ITEM) PROCEDURE GET(I); INTEGER I;
      BEGIN
         IF I < 1 OR I > SIZE THEN ERROR("GET: INDEX OUT OF BOUNDS");
         GET :- ITEMS.DATA(I);
      END;

      INTEGER CAPACITY;
      INTEGER SIZE;
      REF(ITEMARRAY) ITEMS;

      CAPACITY := 20;
      SIZE := 0;
      EXPAND(CAPACITY);

   END;


   ITEM CLASS TEXTITEM(TXT); TEXT TXT;;

   ARRAYLIST CLASS TEXTARRAYLIST;
   BEGIN
      PROCEDURE ADD(T); TEXT T;
         THIS TEXTARRAYLIST QUA ARRAYLIST.ADD(NEW TEXTITEM(T));
      TEXT PROCEDURE GET(I); INTEGER I;
         GET :- THIS TEXTARRAYLIST QUA ARRAYLIST.GET(I) QUA TEXTITEM.TXT;
   END;


   ITEM CLASS REALITEM(X); REAL X;;

   ARRAYLIST CLASS REALARRAYLIST;
   BEGIN
      PROCEDURE ADD(X); REAL X;
         THIS REALARRAYLIST QUA ARRAYLIST.ADD(NEW REALITEM(X));
      REAL PROCEDURE GET(I); INTEGER I;
         GET := THIS REALARRAYLIST QUA ARRAYLIST.GET(I) QUA REALITEM.X;
   END;

END;
EXTERNAL CLASS ARRAYLISTS;
ARRAYLISTS
BEGIN


    CLASS TUPLE(TLIST,T);
        REF(TEXTARRAYLIST) TLIST;
        TEXT T;
    BEGIN
    END TUPLE;


    REF(TUPLE) PROCEDURE GETITEM(S, DEPTH);
        TEXT S;
        INTEGER DEPTH;
    BEGIN
        REF(TUPLE) RESULT;
        REF(TEXTARRAYLIST) OUT;
        OUT :- NEW TEXTARRAYLIST;
        OUT.ADD("");

    CONTINUE:
        WHILE S.LENGTH > 0 DO BEGIN
            CHARACTER C;
            TEXT CTEXT;

            S.SETPOS(1); C := S.GETCHAR; CTEXT :- BLANKS(1); CTEXT.PUTCHAR(C);
            IF DEPTH > 0 AND (C = ',' OR C = '}') THEN
                GOTO RETURN;

            IF C = '{' THEN BEGIN
                REF(TUPLE) X;

                X :- GETGROUP(S.SUB(2,S.LENGTH-1), DEPTH + 1);
                IF X =/= NONE THEN BEGIN
                    REF(TEXTARRAYLIST) OUT2;
                    INTEGER A,B;
                    ! OUT,S = [A+B FOR A IN OUT FOR B IN X[0]], X[1] ;
                    OUT2 :- NEW TEXTARRAYLIST;
                    FOR A := 1 STEP 1 UNTIL OUT.SIZE DO
                        FOR B := 1 STEP 1 UNTIL X.TLIST.SIZE DO
                            OUT2.ADD(OUT.GET(A) & X.TLIST.GET(B));
                    OUT :- OUT2;
                    S :- X.T;
                    GOTO CONTINUE;
                END;
            END;

            IF C = '\' AND S.LENGTH > 1 THEN BEGIN
                TEXT NEWCTEXT;

                NEWCTEXT :- BLANKS(CTEXT.LENGTH + 1);
                NEWCTEXT := CTEXT;
                NEWCTEXT.SETPOS(CTEXT.LENGTH+1);
                S.SETPOS(2); NEWCTEXT.PUTCHAR(S.GETCHAR);
                CTEXT :- NEWCTEXT;
                S :- S.SUB(2,S.LENGTH-1);
            END;

            BEGIN
                REF(TEXTARRAYLIST) OUT2;
                INTEGER A;
                ! OUT, S = [A+CTEXT FOR A IN OUT], S[1:] ;
                OUT2 :- NEW TEXTARRAYLIST;
                FOR A := 1 STEP 1 UNTIL OUT.SIZE DO
                    OUT2.ADD(OUT.GET(A) & CTEXT);
                OUT :- OUT2;
                S :- S.SUB(2,S.LENGTH-1);
            END;
        END;

    RETURN:
        RESULT :- NEW TUPLE(OUT,S);
        GETITEM :- RESULT;
    END GETITEM;


    REF(TUPLE) PROCEDURE GETGROUP(S, DEPTH);
        TEXT S;
        INTEGER DEPTH;
    BEGIN
        REF(TUPLE) RESULT;
        REF(TEXTARRAYLIST) OUT;
        BOOLEAN COMMA,BREAK;

        OUT :- NEW TEXTARRAYLIST;
        COMMA := FALSE;
        BREAK := FALSE;
        WHILE S.LENGTH > 0 AND NOT BREAK DO BEGIN
            REF(TUPLE) GS;
            REF(TEXTARRAYLIST) G;

            GS :- GETITEM(S, DEPTH); G :- GS.TLIST; S :- GS.T;
            IF S.LENGTH = 0 THEN BREAK := TRUE ELSE
            BEGIN
                CHARACTER S1;
                INTEGER I;

                ! out += g ;
                FOR I := 1 STEP 1 UNTIL G.SIZE DO OUT.ADD(G.GET(I));

                S.SETPOS(1); S1 := S.GETCHAR;
                IF S1 = '}' THEN BEGIN
                    IF COMMA THEN BEGIN
                        BREAK := TRUE;
                        RESULT :- NEW TUPLE(OUT, S.SUB(2,S.LENGTH-1));
                    END ELSE
                    BEGIN
                        REF(TEXTARRAYLIST) OUT2;
                        INTEGER I;

                        OUT2 :- NEW TEXTARRAYLIST;
                        FOR I := 1 STEP 1 UNTIL OUT.SIZE DO
                            OUT2.ADD("{" & OUT.GET(I) & "}");
                        BREAK := TRUE;
                        RESULT :- NEW TUPLE(OUT2, S.SUB(2,S.LENGTH-1));
                    END;
                END ELSE
                IF S1 = ',' THEN BEGIN
                    COMMA := TRUE;
                    S :- S.SUB(2,S.LENGTH-1);
                END;
            END;
        END;
        GETGROUP :- RESULT;
    END GETGROUP;


    TEXT INP;

    FOR INP :- "~/{Downloads,Pictures}/*.{jpg,gif,png}",
               "It{{em,alic}iz,erat}e{d,}, please.",
               "{,{,gotta have{ ,\, again\, }}more }cowbell!",
               "{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}" DO
    BEGIN
        REF(TUPLE) RES;
        INTEGER I;

        RES :- GETITEM(INP,0);
        OUTTEXT(INP);
        OUTIMAGE;
        FOR I := 1 STEP 1 UNTIL RES.TLIST.SIZE DO BEGIN
            OUTTEXT("        ");
            OUTTEXT(RES.TLIST.GET(I));
            OUTIMAGE;
        END;
        OUTIMAGE;
    END;

END
Output:
~/{Downloads,Pictures}/*.{jpg,gif,png}
        ~/Downloads/*.jpg
        ~/Downloads/*.gif
        ~/Downloads/*.png
        ~/Pictures/*.jpg
        ~/Pictures/*.gif
        ~/Pictures/*.png

It{{em,alic}iz,erat}e{d,}, please.
        Itemized, please.
        Itemize, please.
        Italicized, please.
        Italicize, please.
        Iterated, please.
        Iterate, please.

{,{,gotta have{ ,\, again\, }}more }cowbell!
        cowbell!
        more cowbell!
        gotta have more cowbell!
        gotta have\, again\, more cowbell!

{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}
        {}} some }{,{\\ edge \,}{ cases, {here} \\\\\}
        {}} some }{,{\\ edge \,}{ cases, {here} \\\\\}

Tailspin

templates braceExpansion
  composer braceParse
    [ <part|'[{}\\,]'>* ] // This is not simply <production> because there may be unbalanced special chars
    rule production: [ <part>* ]
    rule part: <alternation|balancedBraces|escapedCharacter|'[^{}\\,]+'>+
    rule alternation: (<='{'>) [ <production> <alternate>+ ] (<='}'>)
    rule alternate: (<=','>) <production>
    rule balancedBraces: <='{'> <part>* <='}'>
    rule escapedCharacter: <'\\.'>
  end braceParse

  templates collateSequence
    data part <[]|''> local
    @: [''];
    $... -> #
    $@!
    when <´part´ '.*'> do
      def part: $;
      @: [$@... -> '$;$part;'];
    otherwise
      def alternates: [ $... -> collateSequence ... ];
      @: [$@... -> \(def prefix: $; $alternates... -> '$prefix;$;' ! \)];
  end collateSequence

  $ -> braceParse -> collateSequence !
end braceExpansion

'~/{Downloads,Pictures}/*.{jpg,gif,png}' -> '"$;" expands to:$ -> braceExpansion ... -> '$#10;$;';$#10;$#10;' -> !OUT::write

'It{{em,alic}iz,erat}e{d,}, please.' -> '"$;" expands to $ -> braceExpansion ... -> '$#10;$;';$#10;$#10;' -> !OUT::write

'{,{,gotta have{ ,\, again\, }}more }cowbell!' -> '"$;" expands to $ -> braceExpansion ... -> '$#10;$;';$#10;$#10;' -> !OUT::write

'{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}' -> '"$;" expands to $ -> braceExpansion ... -> '$#10;$;';$#10;$#10;' -> !OUT::write
Output:
"~/{Downloads,Pictures}/*.{jpg,gif,png}" expands to:
~/Downloads/*.jpg
~/Downloads/*.gif
~/Downloads/*.png
~/Pictures/*.jpg
~/Pictures/*.gif
~/Pictures/*.png

"It{{em,alic}iz,erat}e{d,}, please." expands to 
Itemized, please.
Itemize, please.
Italicized, please.
Italicize, please.
Iterated, please.
Iterate, please.

"{,{,gotta have{ ,\, again\, }}more }cowbell!" expands to 
cowbell!
more cowbell!
gotta have more cowbell!
gotta have\, again\, more cowbell!

"{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}" expands to 
{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}
{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}

Tcl

Works with: Tcl version 8.6
package require Tcl 8.6

proc combine {cases1 cases2 {insert ""}} {
    set result {}
    foreach c1 $cases1 {
	foreach c2 $cases2 {
	    lappend result $c1$insert$c2
	}
    }
    return $result
}
proc expand {string *expvar} {
    upvar 1 ${*expvar} expanded
    set a {}
    set result {}
    set depth 0
    foreach token [regexp -all -inline {(?:[^\\{},]|\\.)+|[\\{},]} $string] {
	switch $token {
	    "," {
		if {$depth == 0} {
		    lappend result {*}[commatize $a]
		    set a {}
		    set expanded 1
		    continue
		}
	    }
	    "\{" {incr depth  1}
	    "\}" {incr depth -1}
	}
	append a $token
    }
    lappend result {*}[commatize $a]
    return $result
}
proc commatize {string} {
    set current {{}}
    set depth 0
    foreach token [regexp -all -inline {(?:[^\\{},]|\\.)+|[\\{},]} $string] {
	switch $token {
	    "\{" {
		if {[incr depth] == 1} {
		    set collect {}
		    continue
		}
	    }
	    "\}" {
		if {[incr depth -1] == 0} {
		    set foundComma 0
		    set exp [expand $collect foundComma]
		    if {!$foundComma} {
			set exp [lmap c [commatize $collect] {set c \{$c\}}]
		    }
		    set current [combine $current $exp]
		    continue
		} elseif {$depth < 0} {
		    set depth 0
		}
	    }
	}
	if {$depth} {
	    append collect $token
	} else {
	    set current [lmap s $current {set s $s$token}]
	}
    }
    if {$depth} {
	set current [combine $current [commatize $collect] "\{"]
    }
    return $current
}

Demonstrating:

foreach testcase {
    "~/{Downloads,Pictures}/*.{jpg,gif,png}"
    "It{{em,alic}iz,erat}e{d,}, please."
    "{,{,gotta have{ ,\\, again\\, }}more }cowbell!"
    "\{\}\} some \}\{,\{\\\\\{ edge, edge\} \\,\}\{ cases, \{here\} \\\\\\\\\\\}"
} {
    puts $testcase\n\t[join [commatize $testcase] \n\t]
}
Output:
~/{Downloads,Pictures}/*.{jpg,gif,png}
	~/Downloads/*.jpg
	~/Downloads/*.gif
	~/Downloads/*.png
	~/Pictures/*.jpg
	~/Pictures/*.gif
	~/Pictures/*.png
It{{em,alic}iz,erat}e{d,}, please.
	Itemized, please.
	Itemize, please.
	Italicized, please.
	Italicize, please.
	Iterated, please.
	Iterate, please.
{,{,gotta have{ ,\, again\, }}more }cowbell!
	cowbell!
	more cowbell!
	gotta have more cowbell!
	gotta have\, again\, more cowbell!
{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}
	{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}
	{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}

TXR

The approach here is to parse the notation into a nested tree of strings. In the following diagram the -> arrow indicates that the tree on the left denotes the list of output strings on the right.

A list with no operator symbol denotes catenation:

("foo" "bar")  -> ("foobar")

The / symbol (slash, usually denoting arithmetic division) denotes alternation:

(/ "foo" "bar") -> ("foo" "bar")
("inter" (/ "pol" "pret") "ation") -> ("interpolation" "interpretation")

This notation is processed by the bexp-expand function to produce the list of strings which it denotes. The bexp-parse function parses a string containing brace expansion into the above notation.

The backslashes and edge cases are handled between the tokenizing and parsing. Backslashed characters are represented as tokens which include the backslash. Thus the \{ token compares unequal to { and isn't mistaken for it. These backslashed tokens just look like any other text that has no special meaning.

The empty {} is handled as a token, but other cases of braces containing no commas are handled in the parser.

When the parser has scanned a complete, valid brace that contains no comma, instead of generating a (/ ...) tree node from the content, it generates ("{" ... "}"), rendering the braces as literal strings. The ... content may contain / operators, as required.

When the parser has scanned an incomplete brace, it puts out ("{" ...): the dangling brace is represented literally, followed by the items that have been parsed out. The comma elements are preserved in this case; the lack of a closing brace turns off their meaning.

In the main case of a balanced brace with commas, the parsed out elements are split on the commas, which are removed, and that forms the arguments of / node.

;; API
(defun brace-expand (str)
  (bexp-expand (bexp-parse str)))

;; parser
(defstruct bexp-parse-ctx ()
  str
  toks)

(defun bexp-parse (str)
  (let ((ctx (new bexp-parse-ctx
                   str str
                   ;; tokenizer
                   toks (remqual "" (tok #/([{},]|{}|\\\\|\\.)/ t str)))))
    (build
      (whilet ((next (pop ctx.toks)))
        (add
          (if (equal next "{")
            (bexp-parse-brace ctx)
            next))))))

(defun bexp-parse-brace (ctx)
  (buildn
    (let ((orig-toks ctx.toks))
      (caseq (whilet ((next (pop ctx.toks)))
               (casequal next
                 ("{" (add (bexp-parse-brace ctx)))
                 ("}" (return :ok))
                 (t (add next))))
        (:ok
          (cond
            ((memqual "," (get))
             (flow (get)
               (split* @1 (op where (op equal ",")))
               (cons '/)))
            (t
              (add* "{")
              (add "}")
              (get))))
        (nil
          (add* "{")
          (get))))))

;; expander
(defun bexp-expand (tree : (path (new list-builder)))
  (build
    (match-case tree
      (() (add (cat-str path.(get))))
      (((/ . @alt) . @rest)
       (let ((saved-path path.(get)))
         (each ((elem alt))
           path.(oust saved-path)
           (pend (bexp-expand (cons elem rest) path)))))
      ((@(consp @succ) . @rest)
       (pend (bexp-expand (append succ rest) path)))
      ((@head . @rest)
       path.(add head)
       (pend (bexp-expand rest path))))))

;; Tests
(tprint (brace-expand "~/{Downloads,Pictures}/*.{jpg,gif,png}"))
(tprint (brace-expand "It{{em,alic}iz,erat}e{d,}, please."))
(tprint (brace-expand "{,{,gotta have{ ,\\, again\\, }}more }cowbell!"))
(tprint (brace-expand "{}} some }{,{\\\\{ edge, edge} \\,}{ cases, {here} \\\\\\\\\\}"))
Output:
~/Downloads/*.jpg
~/Downloads/*.gif
~/Downloads/*.png
~/Pictures/*.jpg
~/Pictures/*.gif
~/Pictures/*.png
Itemized, please.
Itemize, please.
Italicized, please.
Italicize, please.
Iterated, please.
Iterate, please.
cowbell!
more cowbell!
gotta have more cowbell!
gotta have\, again\, more cowbell!
{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}
{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}

Visual Basic .NET

Translation of: Python
Module Module1

    Function GetGroup(s As String, depth As Integer) As Tuple(Of List(Of String), String)
        Dim out As New List(Of String)
        Dim comma = False
        While Not String.IsNullOrEmpty(s)
            Dim gs = GetItem(s, depth)
            Dim g = gs.Item1
            s = gs.Item2
            If String.IsNullOrEmpty(s) Then
                Exit While
            End If
            out.AddRange(g)

            If s(0) = "}" Then
                If comma Then
                    Return Tuple.Create(out, s.Substring(1))
                End If
                Return Tuple.Create(out.Select(Function(a) "{" + a + "}").ToList(), s.Substring(1))
            End If

            If s(0) = "," Then
                comma = True
                s = s.Substring(1)
            End If
        End While
        Return Nothing
    End Function

    Function GetItem(s As String, Optional depth As Integer = 0) As Tuple(Of List(Of String), String)
        Dim out As New List(Of String) From {""}
        While Not String.IsNullOrEmpty(s)
            Dim c = s(0)
            If depth > 0 AndAlso (c = "," OrElse c = "}") Then
                Return Tuple.Create(out, s)
            End If
            If c = "{" Then
                Dim x = GetGroup(s.Substring(1), depth + 1)
                If Not IsNothing(x) Then
                    Dim tout As New List(Of String)
                    For Each a In out
                        For Each b In x.Item1
                            tout.Add(a + b)
                        Next
                    Next
                    out = tout
                    s = x.Item2
                    Continue While
                End If
            End If
            If c = "\" AndAlso s.Length > 1 Then
                c += s(1)
                s = s.Substring(1)
            End If
            out = out.Select(Function(a) a + c).ToList()
            s = s.Substring(1)
        End While
        Return Tuple.Create(out, s)
    End Function

    Sub Main()
        For Each s In {
            "It{{em,alic}iz,erat}e{d,}, please.",
            "~/{Downloads,Pictures}/*.{jpg,gif,png}",
            "{,{,gotta have{ ,\, again\, }}more }cowbell!",
            "{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}"
        }
            Dim fmt = "{0}" + vbNewLine + vbTab + "{1}"
            Dim parts = GetItem(s)
            Dim res = String.Join(vbNewLine + vbTab, parts.Item1)
            Console.WriteLine(fmt, s, res)
        Next
    End Sub

End Module
Output:
It{{em,alic}iz,erat}e{d,}, please.
        Itemized, please.
        Itemize, please.
        Italicized, please.
        Italicize, please.
        Iterated, please.
        Iterate, please.
~/{Downloads,Pictures}/*.{jpg,gif,png}
        ~/Downloads/*.jpg
        ~/Downloads/*.gif
        ~/Downloads/*.png
        ~/Pictures/*.jpg
        ~/Pictures/*.gif
        ~/Pictures/*.png
{,{,gotta have{ ,\, again\, }}more }cowbell!
        cowbell!
        more cowbell!
        gotta have more cowbell!
        gotta have\ again\ more cowbell!
{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}
        {}} some }{,{\ edge \}{ cases, {here} \\\
        {}} some }{,{\ edge \}{ cases, {here} \\\

Wren

Translation of: Python
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()
}
Output:
~/{Downloads,Pictures}/*.{jpg,gif,png}
    ~/Downloads/*.jpg
    ~/Downloads/*.gif
    ~/Downloads/*.png
    ~/Pictures/*.jpg
    ~/Pictures/*.gif
    ~/Pictures/*.png

It{{em,alic}iz,erat}e{d,}, please.
    Itemized, please.
    Itemize, please.
    Italicized, please.
    Italicize, please.
    Iterated, please.
    Iterate, please.

{,{,gotta have{ ,\, again\, }}more }cowbell!
    cowbell!
    more cowbell!
    gotta have more cowbell!
    gotta have\, again\, more cowbell!

{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}
    {}} some }{,{\\ edge \,}{ cases, {here} \\\\\}
    {}} some }{,{\\ edge \,}{ cases, {here} \\\\\}

zkl

This is a two pass algorithm (2*length(string)), one pass to find valid {} pairs, the next pass to expand them.

fcn eyeball(code,ps=L(),brace=False){ //-->indexes of valid braces & commas
   cs:=L();
   foreach c in (code){ // start fresh or continue (if recursing)
      switch(c){
	 case("\\"){ __cWalker.next(); }
	 case(",") { if(brace) cs.append(__cWalker.n); } // maybe valid
	 case("{") {  // this is real only if there is matching } and a comma
	    n:=__cWalker.n;
	    _,cz:=self.fcn(__cWalker,ps,True);
	    if(cz){ ps.append(n,__cWalker.n); ps.extend(cz) } // valid {} pair
	 }
	 case("}"){ if(brace) return(ps,cs); }
      }
   }
   return(ps,False)
}

fcn expando(code,strings=T("")){
   reg [const] stack=List(); reg roots,cs; bs,_:=eyeball(code);
   foreach c in (code){
      if(bs.holds(__cWalker.n)){
         if     (c=="{") { stack.append(cs); cs=0; roots=strings;       }
	 else if(c==",") { stack.append(strings); strings=roots; cs+=1; }
	 else if(c=="}") { do(cs){ strings=stack.pop().extend(strings); } cs=stack.pop(); }
      }else   if(c=="\\"){
	 c="\\"+__cWalker.next();
	 strings=strings.apply('+(c));
      }
      else strings=strings.apply('+(c));
   }
   strings
}
foreach bs in (T("It{{em,alic}iz,erat}e{d,}",  "~/{Downloads,Pictures}/*.{jpg,gif,png}",
   "It{{em,alic}iz,erat}e{d,}, please.",  "a{2,1}b{X,Y,X}c",  0'|a\\{\\\{b,c\,d}|,
   "{a,b{c{,{d}}e}f",  0'|{,{,gotta have{ ,\, again\, }}more }cowbell!|,
   0'|{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}|))
{      
   "%s expands to\n   %s".fmt(bs,expando(bs)).println();
}
Output:
It{{em,alic}iz,erat}e{d,} expands to
   L("Itemized","Italicized","Iterated","Itemize","Italicize","Iterate")
~/{Downloads,Pictures}/*.{jpg,gif,png} expands to
   L("~/Downloads/*.jpg","~/Pictures/*.jpg","~/Downloads/*.gif","~/Pictures/*.gif","~/Downloads/*.png","~/Pictures/*.png")
It{{em,alic}iz,erat}e{d,}, please. expands to
   L("Itemized, please.","Italicized, please.","Iterated, please.","Itemize, please.","Italicize, please.","Iterate, please.")
a{2,1}b{X,Y,X}c expands to
   L("a2bXc","a1bXc","a2bYc","a1bYc","a2bXc","a1bXc")
a\\{\\\{b,c\,d} expands to
   L("a\\\\\{b","a\\c\,d")
{a,b{c{,{d}}e}f expands to
   L("{a,b{ce}f","{a,b{c{d}e}f")
{,{,gotta have{ ,\, again\, }}more }cowbell! expands to
   L("cowbell!","more cowbell!","gotta have more cowbell!","gotta have\, again\, more cowbell!")
{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\} expands to
   L("{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}","{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}")