Brace expansion: Difference between revisions

From Rosetta Code
Content added Content deleted
(Updated D entry)
Line 660: Line 660:
[http://www.reddit.com/r/readablecode/comments/1w6exe/p6_crosswalk_braceexpansionparses/cf229at "Here is a direct translation to Haskell using parsec"] (of [http://rosettacode.org/mw/index.php?title=Brace_expansion&oldid=175567#Perl_6 an earlier version of the Perl 6 solution]):
[http://www.reddit.com/r/readablecode/comments/1w6exe/p6_crosswalk_braceexpansionparses/cf229at "Here is a direct translation to Haskell using parsec"] (of [http://rosettacode.org/mw/index.php?title=Brace_expansion&oldid=175567#Perl_6 an earlier version of the Perl 6 solution]):


<lang haskell>import Control.Applicative (pure, (<$>), (<*>))
<lang haskell>import Control.Applicative (liftA2, pure, (<$>), (<*>))
import Control.Monad (forever)
import Control.Monad (forever)
import Text.Parsec
import Text.Parsec
Line 666: Line 666:
parser :: Parsec String u [String]
parser :: Parsec String u [String]
parser = expand <$> many (try alts <|> try alt1 <|> escape <|> pure . pure <$> anyChar)
parser = expand <$> many (try alts <|> try alt1 <|> escape <|> pure . pure <$> anyChar)
where
where alts = concat <$> between (char '{') (char '}') (alt `sepBy2` char ',')
alt1 = (\s -> ["{" ++ s ++ "}"]) <$> between (char '{') (char '}') (many $ noneOf ",{}")
alts = concat <$> between (char '{') (char '}') (alt `sepBy2` char ',')
alt = expand <$> many (try alts <|> try alt1 <|> escape <|> pure . pure <$> noneOf ",}")
alt1 = (:[]).('{':).(++"}") <$> between (char '{') (char '}') (many $ noneOf ",{}")
escape = pure <$> sequence [char '\\', anyChar]
alt = expand <$> many (try alts <|> try alt1 <|> escape <|> pure . pure <$> noneOf ",}")
expand = foldr (\x xs -> (++) <$> x <*> xs) [""]
escape = pure <$> sequence [char '\\', anyChar]
p `sepBy2` sep = (:) <$> p <*> many1 (sep >> p)
expand = foldr (liftA2 (++)) [""]
p `sepBy2` sep = liftA2 (:) p (many1 (sep >> p))


main :: IO ()
main :: IO ()

Revision as of 17:29, 31 December 2014

Brace expansion is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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.

The 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} \\\\\}

AutoHotkey

<lang autohotkey>; AutoHotkey runs Perl-compatible regular expressions no problem t=~/{Downloads,Pictures}/ *.{jpg,gif,png} ; Note I added a space so the RosettaCode syntax highlighting will work. The AutoHotkey interpreter handles it no problem. msgbox % expand(t) t=It{{em,alic}iz,erat}e{d,}, please. msgbox % expand(t) t={,{,gotta have{ ,\, again\, }}more }cowbell! msgbox % expand(t) t={}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\} msgbox % expand(t)

expand(t) { t:=RegExReplace(t, "\\\\", "\!") ; if you want to use these character combinations literally in your string, just switch these susbstitutions to something unicode ,t:=RegExReplace(t, "\\,", "\#") ,t:=RegExReplace(t, "\\\{", "\@") ,t:=RegExReplace(t, "\\\}", "\&") a=1 While a or b ; expand (braces with multiple commas) which are (apparently inside something else) t:=RegExReplace(t, "Sxm)^(.*) ([{,]) ([^{},]*) \{ ([^{},]*) , ([^{},]* , [^{}]*) \} ([^{},]*?) ([},]) (.*)$", "$1$2$3$4$6,$3{$5}$6$7$8", a) ; expand (braces with single commas) which are (apparently inside something else) ,t:=RegExReplace(t, "Sxm)^(.*) ([{,]) ([^{},]*) \{ ([^{},]*) , ([^{},]*) \} ([^{},]*?) ([},]) (.*)$", "$1$2$3$4$6,$3$5$6$7$8", b) a=1 While a or b ; expand braces with single commas t:=RegExReplace(t, "Sxm)^(.*) \{ ([^{},]*) , ([^{},]*) \} (.*)$", "$1$2$4`r`n$1$3$4", a) ; expand braces with multiple commas ,t:=RegExReplace(t, "Sxm)^(.*) \{ ([^{},]*) , ([^{},]* , [^{}]*) \} (.*)$", "$1$2$4`r`n$1{$3}$4", b) t:=RegExReplace(t, "\\!", "\\") ,t:=RegExReplace(t, "\\#", "\,") ,t:=RegExReplace(t, "\\@", "\{") ,t:=RegExReplace(t, "\\&", "\}") Return t }</lang>

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 {\\edgy }{ cases, here\\\}

C++

C++11 solution:

<lang cpp>#include <iostream>

  1. include <iterator>
  2. include <string>
  3. include <utility>
  4. 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,Template: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; }</lang>

D

Translation of: Python

This code is not UTF-corrected, because it uses slicing instead of front, popFront, etc. <lang d>import std.stdio, std.typecons, std.array, std.range, std.algorithm, std.string;

Nullable!(Tuple!(string[], string)) getGroup(string s, in uint depth) /*pure*/ @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.front == '}') {
           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 { 

   auto sout = [""];

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

       if (c == "{") {
           const 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() { 

   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,Template: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]);

}</lang>

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

Haskell

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

<lang haskell>import Control.Applicative (liftA2, pure, (<$>), (<*>)) import Control.Monad (forever) import Text.Parsec

parser :: Parsec String u [String] parser = expand <$> many (try alts <|> try alt1 <|> escape <|> pure . pure <$> anyChar) 

   where
       alts = concat <$> between (char '{') (char '}') (alt `sepBy2` char ',')
       alt1 = (:[]).('{':).(++"}") <$> between (char '{') (char '}') (many $ noneOf ",{}")
       alt = expand <$> many (try alts <|> try alt1 <|> escape <|> pure . pure <$> noneOf ",}")
       escape = pure <$> sequence [char '\\', anyChar]
       expand = foldr (liftA2 (++)) [""]
       p `sepBy2` sep = liftA2 (:) p (many1 (sep >> p))

main :: IO () main = forever $ parse parser [] <$> getLine >>= either print (mapM_ putStrLn)</lang>

Output:
$ ./bracex
~/{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
a{b{1,2}c{}}
a{b1c{}}
a{b2c{}}
^D
bracex: <stdin>: hGetLine: end of file

Go

expand.go: <lang 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 }</lang> expand_test.go <lang 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) } }</lang>

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

J

Implementation:

<lang J> 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

)</lang>

Examples:

<lang J> >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\\\}</lang>

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. <lang java>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);
       }
   }

}</lang> 

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} \\\\\}

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:

<lang perl>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;

}</lang>

Usage demonstration: <lang perl>while (my $input = ) { 

   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} \\\\\}</lang>

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} \\\\\}

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 Perl 6.

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. <lang perl6>grammar BraceExpansion { 

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

}

sub crosswalk($/) { 

   [X~] , $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) }</lang> And to test... <lang perl6>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!
   {}} some {\\{edge,edgy} }{ 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,Template:C
   {a{\}b,c}d
   {a,b{{1,2}e}f
   END</lang>
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

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

Python

<lang 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
  1. stolen cowbells from perl6 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"</lang>
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} \\\\\}

Ruby

Translation of: Python

<lang ruby>def getitem(s, depth=0) 

 out = [""]
 until s.empty?
   c = s[0]
   break  if depth>0 and (c == ',' or c == '}')
   if c == '{'
     x = getgroup(s[1..-1], depth+1)
     if x
       out = out.product(x[0]).map{|a,b| a+b}
       s = x[1]
       next
     end
   end
   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
 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
   if s[0] == '}'
     return out, s[1..-1]  if comma
     return out.map{|a| '{' + a + '}'}, s[1..-1]
   end
   comma, s = true, s[1..-1]  if s[0] == ','
 end
 nil

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</lang>

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} \\\\\}

Tcl

Works with: Tcl version 8.6

<lang tcl>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

}</lang> Demonstrating: <lang tcl>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]

}</lang>

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. <lang zkl>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

}</lang> <lang zkl>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();

}</lang>

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} \\\\\}")
Retrieved from "https://rosettacode.org/wiki/Brace_expansion?oldid=239480"