# Fix Brain-Flak push-pop redundancy

Brain-Flak is a stack-based esoteric language with eight commands:

()     Evaluates to 1
<>     Switch active stack; evaluates to 0
[]     Evaluates to height of current stack
{}     Pop current stack; evaluates to the popped number
(...)  Execute block and push the result; evaluates as result
<...>  Execute block; evaluates as 0
[...]  Execute block; evaluates as negation of result
{...}  While top of active stack is nonzero, execute block


Write a program or function to detect and remove one common type of push-pop redundancy that often occurs when writing Brain-Flak code.

# Finding Redundancy

To determine whether a push and pop are truly redundant, we must understand which scopes use the return value of instructions:

• The return value of any top-level instruction is ignored.
• (...) will always use the return values of its children.
• <...> will always ignore the top-level instruction of its children.
• {...} will pass the return values of its children to the enclosing scope; that is, their return values will be used if and only if {...} itself is in a scope that uses its return value.
• [...] theoretically works like {...} in this sense; however, you may assume that [...] is always in a scope that cares about return value, thus treating it like (...).

The type of redundancy we are interested in occurs in any substring of the form (A)B{} satisfying the following:

• A is a balanced string; that is, the parentheses around A are matched.
• (A) is in a scope that ignores its return value.
• B does not contain [], <>, or either half of the {...} monad.
• The {} immediately following B pops the value pushed by (A). That is, B has an equal number of {} and ...), and no prefix of B has more {} than ...).

Note that B is typically not a balanced string.

# Removing Redundancy

To remove this redundancy, we temporarily introduce a symbol 0 to the language, which evaluates to 0. With this symbol, a redundant string (A)B{} can be safely replaced by 0BA. Since Brain-Flak does not have a 0 symbol, we must make simplifications to remove it:

• A 0 with a sibling can be removed entirely, as can any top-level 0s. (If there are two 0s as the only children of a monad, only one of them can be removed.)
• [0] and <0> can be simplified to 0.
• If you encounter a (0), find the matching {}; replace the (0) and matching {} with 0s.
• {0} will never happen. If I'm wrong about this, you may have undefined behavior in this case.

# Rules

• Input is a string taken by any reasonable method.
• Input is guaranteed to be valid Brain-Flak code consisting only of brackets.
• Any [...] monads in the input will be in scopes that do not ignore their return values.
• Output is the result of using this algorithm (or another algorithm with the same result) to remove push-pop redundancies in the input program.
• The input might not contain any redundancy; in that case, the input program should be output unchanged.
• If your solution is in Brain-Flak, it should hopefully not detect any redundancy in its own code.
• This is , so the shortest program (in bytes) in each language wins.

# Test cases

With redundancy (with redundant push and pop marked):

Shortest redundancy
({}){} -> {}
^  ^^^

First example from tips post
({}<>)({}()) -> ({}<>())
^    ^ ^^

Second example from tips post
({}<({}<>)><>)(<((()()()){}[((){}{})])>) -> (<((()()()){}[((){}<({}<>)><>{})])>)
^            ^                 ^^

({}<({}{})>{}) -> ({}({}{}))
^    ^ ^^

Inside a loop
{({}{})([{}])} -> {([{}{}])}
^    ^  ^^

Stack height pushed
([][]())({}()) -> ([][]()())
^      ^ ^^

Loop result pushed
({({}[()])}{})(({})) -> (({({}[()])}{}))
^            ^  ^^

Two redundancies
({}<({}{})>)({}{}) -> ({}{}{})
^   ^    ^ ^ ^^^^

Discovered redundancy
(({})){}({}()) -> ({}())
^^  ^^^^ ^^

Chained redundancy
(<(()()())>)(({}){}{}({})) -> (()()()({}))
^      ^         ^^


No redundancy (output should be the same as input):

-empty string-
(({}<>)({}()))         - unlike the second test case, the pushed value is used again
(({}){})               - standard code for doubling the top value on the stack
({}{})<>{}             - push and pop not on same stack
(()){{}{}}             - loop starts between push and pop
({(({}[()]))}{})([]{}) - stack height is used after push