StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I have been doing something like this recently, and it took me a lot of time to solve this, so here's how I do it. There may be a simpler algorithm for this though.</p> <p>You can write a recursive descent parser to transform the text into the tree. Make the strings leaf nodes that holds that string and the matched pair of braces an internal node. Each leaf node can contain more than one string.</p> <p>For example, this:</p> <pre><code>/a/{b,c}/{d,e{f,g,h}}/i </code></pre> <p>can become:</p> <pre><code>( ["/a/"] { ( ["b"] ) ( ["c"] ) } ["/"] { ( ["d"] ) ( ["e"] { ( ["f"] ) ( ["g"] ) ( ["h"] ) } ) } ["i"] ) </code></pre> <p>Try to look at it as a tree, where <code>["stringA", "stringB"]</code> denotes a leaf node, and matched pair of braces represents an internal node. There are 2 types of internal node, one that can choose between one of the alternatives (I use <code>{}</code> in this example) and one that combines all the combination (I use <code>()</code> here).</p> <p>So, the above tree would go like this:</p> <pre><code>( ["/a/"] { ["b"] ["c"] } ["/"] { ["d"] ( ["e"] { ["f"] ["g"] ["h"] } ) } ["i"] ) </code></pre> <p>then</p> <pre><code>( ["/a/"] ["b", "c"] ["/"] { ["d"] ( ["e"] ["f", "g", "h"] ) } ["i"] ) </code></pre> <p>then</p> <pre><code>( ["/a/"] ["b", "c"] ["/"] { ["d"] ["ef", "eg", "eh"] } ["i"] ) </code></pre> <p>then</p> <pre><code>( ["/a/"] ["b", "c"] ["/"] ["d", "ef", "eg", "eh"] ["i"] ) </code></pre> <p>and finally, you end up with a single leaf node, which are all the combinations:</p> <pre><code>["/a/b/di", "/a/b/efi", "/a/b/egi", "/a/b/ehi", "/a/c/di", "/a/c/efi", "/a/c/egi", "/a/c/ehi"] </code></pre> <p>Then you can pretty print it.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload