Expand compressed brain-flak This challenge was posted as part of the April 2018 LotM challenge, as well as for Brain-flak's 2nd birthday



I was thinking about what the most efficient way to encode brain-flak programs would be. The obvious thing to do, since there are only 8 valid characters, is to map each character to a 3-bit sequence. This is certainly very effective, but it's still very redundant. There are some features of brain-flak code that we could take advantage of to shorten the encoding. 


The nilads, which are all represented by 2 matched brackets, really act as a single unit of information rather than 2. If we replaced each bracket with a single byte character, this would make the encodings much smaller without losing any data.
This one is less obvious, but the closing bytes of the monads are redundant too. Think you could guess what the '?' characters represent in the following snippet?

 {(({}?&lt;&gt;?&lt;&gt;?


If we assume the input is valid brain-flak code, then there is only one option for each of those question marks. This means that we can unambiguously use a close monad character to represent every closing bracket. This has the added benefit of keeping the character set small, which would greatly help if we wanted to use a huffman encoding. Since the close monad character will most likely be the most common character by a wide margin, it could be represent by a single bit, which is hugely efficient. 


These two tricks will let us compress brain-flak code via the following algorithm:


Replace every closing bracket of a monad with |. Or in other words, replace every closing bracket that is not preceded by it's opening match with a bar. So...

(({})&lt;(()()())&gt;{})


would become

(({}|&lt;(()()()||{}|

Replace every nilad with it's closing bracket. Therefore, matched brackets with nothing in them use the following mapping:

() --&gt; )
{} --&gt; }
[] --&gt; ]
&lt;&gt; --&gt; &gt;


Now our last example becomes:

((}|&lt;()))||}|

Remove trailing | characters. Because we know that the total number of bars should equal the total number of ({[&lt; characters, if there are bars at the end missing, we can infer them. So an example like:

({({})({}[()])})


would become

({(}|(}[)



Your challenge for today is to reverse this process.

Given a string of compressed brain-flak containing only the characters (){}[]&lt;&gt;|, expand it into the original brain-flak code. You can assume that the input will always expand to valid brain-flak. This means that no prefix of the input will ever contain more | than ({[&lt; characters.

The input will not contain trailing | characters. These must be inferred from context.

As usual, you can submit either a full program or a function, and input/output formats are permissive. And since this is a code-golf, your code will be scored by the length of the source code in bytes, the smaller the score the better.

Test cases

Here are some test cases. If you would like more, you can generate your own test cases with this python script and the Brain-Flak Wiki, which is where the majority of these test cases come from.

#Compressed code
#Original code

())))
(()()()())


([([}()||||(&gt;||{(})|&gt;|}{((&lt;}|||&gt;}|}&gt;}
([([{}(())])](&lt;&gt;)){({}())&lt;&gt;}{}{((&lt;{}&gt;))&lt;&gt;{}}{}&lt;&gt;{}

({(}|(}[)|||}
({({})({}[()])}{})


(((()))||(](((}}||(}([(((}))||||(]((}}|}|}}|||]||]|[))||(}))|}(}|(}]]|}
((((()()()))([]((({}{}))({}([((({}()())))]([](({}{}){}){}{})))[]))[])[()()])({}()()){}({})({}[][]){}
Brain-Flak, 952 916 818 bytes

{(({})[(((()()()()()){}){}){}])((){[()](&lt;{}&gt;)}{}){{}(({})()&lt;&gt;)(&lt;&gt;)}{}(&lt;&gt;)&lt;&gt;(({})[(((()()()){}){}()){({}[()])}{}])((){[()](&lt;{}&gt;)}{})({}&lt;&gt;{})&lt;&gt;(({})[((((()()()()()){}){})){}{}])((){[()](&lt;{}&gt;)}{})({}&lt;&gt;{})&lt;&gt;(({})[(((((()()()()()){}){}){}())){}{}])((){[()](&lt;{}&gt;)}{})({}&lt;&gt;{}){{}(&lt;(&lt;&gt;({})()()&lt;&gt;)&gt;)}{}&lt;&gt;(({})[(((()()()()()){}){}){}()])((){[()](&lt;{}&gt;)}{}){{}(({})[()])(&lt;&gt;)&lt;&gt;(&lt;({}&lt;{({}&lt;&gt;)&lt;&gt;}{}&gt;)&gt;)&lt;&gt;{({}&lt;&gt;)&lt;&gt;}{}(&lt;&gt;)}{}(&lt;&gt;)&lt;&gt;(({})[(((((()()()()()){})){}{}())){}{}])((){[()](&lt;{}&gt;)}{})({}&lt;&gt;{})&lt;&gt;(({})[((((()()()()()){}){})()){}{}])((){[()](&lt;{}&gt;)}{})({}&lt;&gt;{})&lt;&gt;(({})[(((((()()()()()){}){}){}())()){}{}])((){[()](&lt;{}&gt;)}{})({}&lt;&gt;{}){{}&lt;&gt;(&lt;(({})[()()])(&lt;&gt;)&lt;&gt;(&lt;({}&lt;{({}&lt;&gt;)&lt;&gt;}{}&gt;)&gt;)&lt;&gt;{({}&lt;&gt;)&lt;&gt;}{}&gt;)}{}&lt;&gt;(({})[(((((()()()()()){}){})()){}{}){}])((){[()](&lt;{}&gt;)}{}){{}{}(&lt;(&lt;&gt;{}&lt;&gt;)&gt;)}{}(&lt;&gt;)&lt;&gt;(&lt;({}&lt;{({}&lt;&gt;)&lt;&gt;}{}&gt;)&gt;)&lt;&gt;{({}&lt;&gt;)&lt;&gt;}{}&lt;&gt;}{}{({}&lt;&gt;)&lt;&gt;}&lt;&gt;


Saved 360 bytes by calculating opposing brackets relatively rather than from scratch (e.g. ')' = '(' + 1 instead of (((5 * 2) * 2) * 2) + 1)

Saved 34 bytes with some direct replacements from DJMcMayhem

Saved 10 bytes by overlapping the &gt;]} handling code

Saved 118 bytes by deduplicating rolls

Saved 40 bytes by taking advantage of the empty stack to simplify the first roll

Saved 48 bytes by marking EOF with -1, enabling more concise roll code

Saved 36 bytes by using the stock equals logic instead of my own

Saved 98 bytes thanks to Jo King finding a more efficient way to build the output

Try it online!

First time golfing in Brain-Flak, so there are probably some really big improvements, but it works. Lots of copy/paste to handle each bracket type, and big thanks to the automatic integer generator and the Roll snippet from here.

Explanation here, TIO formats it more easily

Bonus answer:

Compressed Brain-Flak 583 bytes

{((}|[((()))))|}|}|}||(){[)|(&lt;}|||}|{}((}|)&gt;|(&gt;||}(&gt;|&gt;((}|[((()))|}|})|{(}[)|||}||(){[)|(&lt;}|||}|(}&gt;}|&gt;((}|[(((()))))|}|}||}}||(){[)|(&lt;}|||}|(}&gt;}|&gt;((}|[((((()))))|}|}|})||}}||(){[)|(&lt;}|||}|(}&gt;}|{}(&lt;(&gt;(}|))&gt;||||}&gt;((}|[((()))))|}|}|})||(){[)|(&lt;}|||}|{}((}|[)||(&gt;|&gt;(&lt;(}&lt;{(}&gt;|&gt;|}||||&gt;{(}&gt;|&gt;|}(&gt;||}(&gt;|&gt;((}|[((((()))))|}||}})||}}||(){[)|(&lt;}|||}|(}&gt;}|&gt;((}|[(((()))))|}|}|)|}}||(){[)|(&lt;}|||}|(}&gt;}|&gt;((}|[((((()))))|}|}|})|)|}}||(){[)|(&lt;}|||}|(}&gt;}|{}&gt;(&lt;((}|[))||(&gt;|&gt;(&lt;(}&lt;{(}&gt;|&gt;|}||||&gt;{(}&gt;|&gt;|}|||}&gt;((}|[((((()))))|}|}|)|}}|}||(){[)|(&lt;}|||}|{}}(&lt;(&gt;}&gt;||||}(&gt;|&gt;(&lt;(}&lt;{(}&gt;|&gt;|}||||&gt;{(}&gt;|&gt;|}&gt;|}{(}&gt;|&gt;|&gt;


Try it online!

(Note that the above link does not run because TIO doesn't have a Compressed Brain-Flak interpreter. You can find a transpiler to Brain-Flak here)

I have checked that this is valid by transpiling to Brain-Flak using this tool, now efficient enough that timing out is unlikely.