Brace expansion is a type of parameter expansion [[wp:Bash_%28Unix_shell%29#Brace_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 <code>enable_{audio,video}</code> would be interpreted as if both <code>enable_audio</code> and <code>enable_video</code> had been specified.


;Task

Write a function that can perform brace expansion on any input string, according to the following specification.<br>
Demonstrate how it would be used, and that it passes the four test cases given below.

{{task heading|Specification}}

In the input string, balanced pairs of braces containing comma-separated substrings <small>(details below)</small> 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:

<!-- BEGINNING OF MAIN DIAGRAM -->
<table align="center" style="margin-top:0.8em; margin-bottom:1em; border:double 3px #bbb; background:#F9F9F9; color:#111; line-height:1.5em"><tr><td>
<div style="padding:0.4em 0.6em; margin:0 0 0 0.4em; background:#ddd; font-family:'DejaVu Sans Mono','Courier New',Consolas,Monaco,monospace"><nowiki>It{{em,alic}iz,erat}e{d,}</nowiki></div>
</td><td>
<div style="padding:0 0.6em; text-align:center; color:#665">''parse''&nbsp;<br>―――――▶<br>&zwnj;</div>
</td><td>
<table style="border-spacing:0; border-collapse:collapse; text-align:center; background:#D5B874; font-family:'DejaVu Sans Mono','Courier New',Consolas,Monaco,monospace">
  <tr>
    <td style="padding:0 0 0 0.7em;">It</td>
    <td style="padding:0.1em 0 0.1em 0;">
      <table style="border-spacing:0 0.3em;">
        <tr>
          <td style="padding:0" rowspan="2">
            <div style="font-size:155%; line-height:1.15em; position:relative; left:0.32em; color:#644709">⎧<br>⎨<br>⎩</div>
          </td>
          <td style="padding:0 0.4em; background:#E5CD94">
            <table style="border-spacing:0 0.2em; position:relative; right:0.25em">
              <tr>
                <td style="padding:0" rowspan="2">
                  <div style="font-size:100%;line-height:1em; position:relative; left:0.26em; color:#644709">⎧<br>⎨<br>⎩</div>
                </td>
                <td style="padding:0 0.4em; background:#F3E0B3">em</td>
                <td style="padding:0" rowspan="2">
                  <div style="font-size:100%; line-height:1em; position:relative; right:0.26em; color:#644709">⎫<br>⎬<br>⎭</div>
                </td>
              </tr>
              <tr><td style="padding:0 0.5em; background:#F3E0B3">alic</td></tr>
            </table>
          </td>
          <td style="padding:0 0 0 0; background:#E5CD94">
            <div style="position:relative; right:0.5em">iz</div>
          </td>
          <td style="padding:0" rowspan="2">
            <div style="font-size:155%; line-height:1.15em; position:relative; right:0.32em; color:#644709">⎫<br>⎬<br>⎭</div>
          </td>
        </tr>
        <tr><td style="padding:0; background:#E5CD94" colspan="2">erat</td></tr>
      </table>
    </td>
    <td style="padding:0">e</td>
    <td style="padding:0 0.32em 0 0.2em">
      <table style="border-spacing:0 0.2em;">
        <tr>
          <td style="padding:0" rowspan="2">
            <div style="font-size:100%;line-height:1em; position:relative; left:0.28em; color:#644709">⎧<br>⎨<br>⎩</div>
          </td>
          <td style="padding:0 0.5em; background:#E5CD94">d</td>
          <td style="padding:0" rowspan="2">
            <div style="font-size:100%;line-height:1em; position:relative; right:0.26em; color:#644709">⎫<br>⎬<br>⎭</div>
          </td>
        </tr>
        <tr><td style="padding:0; background-color:#E5CD94; background-image: linear-gradient(-45deg, #E5CD94 25%, #D5B874 25%, #D5B874 50%, #E5CD94 50%, #E5CD94 75%, #D5B874 75%, #D5B874); background-size: 0.5em 0.5em;">&zwnj;</td></tr>
      </table>
    </td>
  </tr>
</table>
</td><td>
<div style="padding:0 0.6em; text-align:center; color:#665">''expand''&nbsp;<br>―――――▶<br>&zwnj;</div>
</td><td style"padding:0"><div style="padding:0.5em 0.6em; margin:0.4em 0.4em 0.4em 0; background:#ddd; font-family:'DejaVu Sans Mono','Courier New',Consolas,Monaco,monospace; line-height:1.35em"><span style="padding:0.1em 0;background:#D5B874">It<span style="padding:0.1em 0;background:#F3E0B3">em</span><span style="padding:0.1em 0;background:#E5CD94">iz</span>e<span style="padding:0.1em 0;background:#E5CD94">d</span></span><br><span style="padding:0.1em 0;background:#D5B874">It<span style="padding:0.1em 0;background:#F3E0B3">em</span><span style="padding:0.1em 0;background:#E5CD94">iz</span>e</span><br><span style="padding:0.1em 0;background:#D5B874">It<span style="padding:0.1em 0;background:#F3E0B3">alic</span><span style="padding:0.1em 0;background:#E5CD94">iz</span>e<span style="padding:0.1em 0;background:#E5CD94">d</span></span><br><span style="padding:0.1em 0;background:#D5B874">It<span style="padding:0.1em 0;background:#F3E0B3">alic</span><span style="padding:0.1em 0;background:#E5CD94">iz</span>e</span><br>
<span style="padding:0.1em 0;background:#D5B874">It<span style="padding:0.1em 0;background:#E5CD94">erat</span>e<span style="padding:0.1em 0;background:#E5CD94">d</span></span><br><span style="padding:0.1em 0;background:#D5B874">It<span style="padding:0.1em 0;background:#E5CD94">erat</span>e</span></div>
</td></tr>
<tr style="text-align:center; color:#665">
  <td><small>input string</small></td>
  <td></td>
  <td><small>alternation tree</small></td>
  <td></td>
  <td><small>output ''(list of strings)''</small></td>
</tr></table>
<!-- END OF MAIN DIAGRAM -->

This tree can in turn be transformed into the intended list of output strings by, colloquially speaking, determining all the possible ways to walk through it from left to right while only descending into ''one'' branch of each alternation one comes across ''(see the right part of the diagram)''. When implementing it, one can of course combine the parsing and expansion into a single algorithm, but this specification discusses them separately for the sake of clarity.

'''Expansion''' of alternations can be more rigorously described by these rules:

<!-- BEGINNING OF "EXPANSION" SIDE-DIAGRAM -->
<table style="margin:0.4em; float:right; position:relative; top:-0.8em; padding:0.22em 0.5em; background:#F9F9F9; border:solid 1px #ccc; color:#111; line-height:1.2em; font-family:'DejaVu Sans Mono', 'Courier New', Consolas, Monaco;"><tr>
<td style="padding:0;">
  <table style="border-spacing:0 0.2em; background:#D5B874">
    <tr>
      <td style="padding:0 0.1em 0 0.6em; background:#E5CD94">a</td>
      <td style="padding:0; background:#E5CD94">
        <table style="border-spacing:0 0.2em">
          <tr>
            <td style="padding:0" rowspan="2">
              <div style="font-size:100%; color:#644709; line-height:1em; position:relative; left:0.27em">⎧<br>⎨<br>⎩</div>
            </td>
            <td style="padding:0 0.35em; background:#F3E0B3">2</td>
            <td style="padding:0" rowspan="2">
              <div style="font-size:100%; color:#644709; line-height:1em; position:relative; right:0.25em">⎫<br>⎬<br>⎭</div>
            </td>
          </tr>
          <tr><td style="padding:0 0.35em; background:#F3E0B3">1</td></tr>
        </table>
      </td>
      <td style="padding:0 0.06em 0 0.12em; background:#E5CD94">b</td>
      <td style="padding:0; background:#E5CD94">
        <table style="border-spacing:0 0.2em">
          <tr>
            <td style="padding:0" rowspan="3">
              <div style="font-size:115%; color:#644709; line-height:1.19em; position:relative; left:0.25em">⎧<br>⎨<br>⎩</div>
            </td>
            <td style="padding:0 0.4em; background:#F3E0B3">X</td>
            <td style="padding:0" rowspan="3">
              <div style="font-size:115%; color:#644709; line-height:1.19em; position:relative; right:0.25em">⎫<br>⎬<br>⎭</div>
            </td>
          </tr>
          <tr><td style="padding:0 0.4em; background:#F3E0B3">Y</td></tr>
          <tr><td style="padding:0 0.4em; background:#F3E0B3">X</td></tr>
        </table>
      </td>
      <td style="padding:0 0.6em 0 0.1em; background:#E5CD94">c</td>
    </tr>
  </table>
</td>
<td><div style="padding:0 0.6em;text-align:center; color:#665">&#10230;</div></td>
<td style="padding:0; background:#D5B874"><table style="border-spacing:0 0.25em;">
  <tr><td style="padding:0 0.4em; background:#E5CD94">a2bXc</td></tr>
  <tr><td style="padding:0 0.4em; background:#E5CD94">a2bYc</td></tr>
  <tr><td style="padding:0 0.4em; background:#E5CD94">a2bXc</td></tr>
  <tr><td style="padding:0 0.4em; background:#E5CD94">a1bXc</td></tr>
  <tr><td style="padding:0 0.4em; background:#E5CD94">a1bYc</td></tr>
  <tr><td style="padding:0 0.4em; background:#E5CD94">a1bXc</td></tr>
</table></td>
</tr></table>
<!-- END OF "EXPANSION" SIDE-DIAGRAM -->

<ul style="margin-bottom:0.9em">
<li>
An alternation causes the list of alternatives that will be produced by its parent branch to be increased &#119899;-fold, each copy featuring <u>one</u> of the &#119899; alternatives produced by the alternation's child branches, in turn, at that position.
</li>
<li>
This means that multiple alternations inside the same branch are cumulative &nbsp;''(i.e. the complete list of alternatives produced by a branch is the string-concatenating "[[wp:Cartesian product|Cartesian product]]" of its parts)''.
</li>
<li>
All alternatives (even duplicate and empty ones) are preserved, and they are ordered like the examples demonstrate &nbsp;''(i.e. "[[wp:Lexicographical_order|lexicographically]]" with regard to the alternations)''.
</li>
<li>
The alternatives produced by the root branch constitute the final output.
</li>
</ul>

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

<!-- BEGINNING OF "PARSING" SIDE-DIAGRAM -->
<table style="margin:0.4em; border-collapse:collapse; clear:both; float:right; position:relative; top:-0.8em; padding:0.22em 0.5em; background:#F9F9F9; border:solid 1px #ccc; color:#111; line-height:1.2em; text-align:center; font-family:'DejaVu Sans Mono','Courier New',Consolas,Monaco,monospace"><tr>
<td style="padding:0 0 0 0.6em"><div style="padding:0.35em 0.5em; margin:0; background:#ddd">a\\{\\\{b,c\,d}</div></td>
<td style="padding:0"><div style="padding:0 0.6em; color:#665">&#10230;</div></td>

<td style="padding:0.4em 0.6em 0.4em 0">
  <table style="border-spacing:0 0.2em; border-collapse:collapse; background:#D5B874"><tr>
    <td style="padding:0 0 0 0.6em">a\\</td>
    <td style="padding:0.2em 0.28em 0.2em 0.10em;">
      <table style="border-spacing:0 0.2em">
        <tr>
          <td style="padding:0" rowspan="2">
            <div style="font-size:100%; color:#644709; line-height:1em; position:relative; left:0.25em">⎧<br>⎨<br>⎩</div>
          </td>
          <td style="padding:0 0.35em; background:#E5CD94">\\\{b</td>
          <td style="padding:0" rowspan="2">
            <div style="font-size:100%; color:#644709; line-height:1em; position:relative; right:0.25em">⎫<br>⎬<br>⎭</div>
          </td>
        </tr>
        <tr><td style="padding:0 0.35em; background:#E5CD94">c\,d</td></tr>
      </table>
    </td>
  </tr></table>
</td>
</tr><tr>
  <td style="border-top:solid 1px #ccc; padding:0 0 0 0.6em"><div style="padding:0.35em 0.5em; margin:0; background:#ddd">{a,b{c{,{d}}e}f</div></td>
  <td style="border-top:solid 1px #ccc; padding:0"><div style="padding:0; color:#665">&#10230;</div></td>
  <td style="border-top:solid 1px #ccc; padding:0.4em 0.6em 0.4em 0">
  <table style="border-spacing:0 0.2em; border-collapse:collapse; background:#D5B874"><tr>
    <td style="padding:0 0 0 0.6em">{a,b{c</td>
    <td style="padding:0.2em 0.1em 0.2em 0.1em;">
      <table style="border-spacing:0 0.2em">
        <tr>
          <td style="padding:0" rowspan="2">
            <div style="font-size:100%; color:#644709; line-height:1em; position:relative; left:0.25em">⎧<br>⎨<br>⎩</div>
          </td>
          <td style="padding:0 0.35em; background-color:#E5CD94; background-image: linear-gradient(-45deg, #E5CD94 25%, #D5B874 25%, #D5B874 50%, #E5CD94 50%, #E5CD94 75%, #D5B874 75%, #D5B874); background-size: 0.5em 0.5em;">&zwnj;</td>
          <td style="padding:0" rowspan="2">
            <div style="font-size:100%; color:#644709; line-height:1em; position:relative; right:0.25em">⎫<br>⎬<br>⎭</div>
          </td>
        </tr>
        <tr><td style="padding:0 0.35em; background:#E5CD94">{d}</td></tr>
      </table>
    </td>
    <td style="padding:0 0.28em 0 0">e}f</td>
  </tr></table>
</td>
</tr></table>
<!-- END OF "PARSING" SIDE-DIAGRAM -->

<ul style="margin-bottom:0.9em">
<li>
An unescaped ''backslash'' which precedes another character, [[wp:Escape_character|escapes]] that character (to force it to be treated as literal). The backslashes are passed along to the output unchanged.
</li>
<li>
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 <u>nearest</u> still unassociated unescaped opening brace to its left (if any). Furthermore, each unescaped ''comma'' is associated with the <u>innermost</u> brace pair that contains it (if any). With that in mind:
<ul>
<li>
Each brace pair that has <u>at least one comma</u> 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.
</li>
<li>
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.
</li>
</ul>
</li>
</ul>

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

{{task heading|Test Cases}}

:::{| class="wikitable" style="white-space: nowrap;"
|-
! Input<br><small style="font-weight:normal">''(single string)''</small>
! Ouput<br><small style="font-weight:normal">''(list/array of strings)''</small>
|- style="vertical-align:top"
|
<code>~/{Downloads,Pictures}/*.{jpg,gif,png}</code>
|
<code>~/Downloads/*.jpg</code><br>
<code>~/Downloads/*.gif</code><br>
<code>~/Downloads/*.png</code><br>
<code>~/Pictures/*.jpg</code><br>
<code>~/Pictures/*.gif</code><br>
<code>~/Pictures/*.png</code><br>
|- style="vertical-align:top"
|
<code>It{{em,alic}iz,erat}e{d,}, please.</code>
|
<code>Itemized, please.</code><br>
<code>Itemize, please.</code><br>
<code>Italicized, please.</code><br>
<code>Italicize, please.</code><br>
<code>Iterated, please.</code><br>
<code>Iterate, please.</code><br>
|- style="vertical-align:top"
|
<code>{,{,gotta have{ ,\, again\, }}more }cowbell!</code>
|
<code>cowbell!</code><br>
<code>more cowbell!</code><br>
<code>gotta have more cowbell!</code><br>
<code>gotta have\, again\, more cowbell!</code><br>
|- style="vertical-align:top"
|
<code>{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}</code>
|
<code>{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}</code><br>
<code>{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}</code>
|}
<hr style="clear:both; margin-bottom:1em;"/>

{{Template:Strings}}


:* &nbsp; [[Brace_expansion_using_ranges]]
<br><br>
