[Question]
  [
[Brain-Flak](https://github.com/DJMcMayhem/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](https://codegolf.stackexchange.com/a/95404/69059) 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 `0`s. (If there are two `0`s 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 `0`s.
* `{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 a semantically equivalent Brain-Flak program with no push-pop redundancies as defined above.
* The output program must not be longer than the result of the algorithm described above.
* 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 [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"), 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 the zero monad
({}<({}{})>{}) -> ({}{}{})
    ^    ^ ^^
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
```
  
[Answer]
# [Haskell](https://www.haskell.org/), ~~995~~ ~~973~~ 873 bytes
*Nitrodon saved me 22 bytes with a way around the monomorphism restriction*
Not *well* golfed, but golfed a bit.
I implement my own parsing library here. Not a wise idea for golf. If I really wanted to make this short I would probably just use an off the shelf one like `parsec`.
I also lose a ton of bytes to the type and instance declarations. This could definitely be done without them and it would probably save bytes.
```
import Control.Monad
newtype P b a=P{h::b->[(b,a)]}
instance Functor(P b)where fmap f(P p)=P$map(f?)?p
instance Applicative(P b)where pure x=P(\y->[(y,x)]);(<*>)=ap
instance Monad(P b)where P p>>=f=P$(>>=uncurry(flip$h.f)).p
f?x=f<$>x
l=s"("
k=s"()"
o=s")"
w=words
p x=pure x
e=P$p[]
x%y=liftM2(++)x y
P p#P q=P$p%q
b q=P(\x->[(b,a)|a:b<-[x],q a])
t=p?b(p$1>0)
s=mapM$b.(==)
a=foldr(#)e
n p=P(\x->[(x,())|[]==h p x])
v=a[s[x]%c%s[y]%c|[x,y]<-w"() <> {} []"]#s"0"
c=v#s""
d 0=a[n(a$s?w"<> [] { } )")*>a[k,n k*>t]%d 0,o%d 1,p""]
d x=a[n(s"<>"#s"[]")*>k#(p?b(`elem`"(<>[]"))%d x,s"{}"%d(x-1),o%d(x+1)]
f z=a[a[p""|z],(s"{"#s"[")%f z,l%f(0>1),s"<"%f(1>0),v%f z]
m=p""#(t%m)<*q
q=P(\x->[([],"")|[]==x])
z=a[s"0"*>p"",(s"["#s"<")*>z<*(s"]"#s">"),l%z%o*>p"<(0)>"]
r=a[n z*>t%r,z%r,q]
u x=head$(u.snd<$>((>>=h r.snd).h(do x<-f$1>0;l;i<-v;o;y<-d 0;s"{}";((x++'0':y++i)++)?m))x)++[x]
```
[Try it online!](https://tio.run/##ZVRRj9owDH7Pr7AC1cVQELfHIwmaJu1pJyHtsRdtgbaiorSlLZDC8dtvDmwHd3toEn/25882FivbrJM8f3vLNlVZt/CtLNq6zMfPZWFjViSHtqsSmMMCrJqfVk9Pi5GOxCK0aM4sK5rWFssEvu@KZVvWguLwsErqBNKNrSAloEI175Mh0hnOqhvla1Xl2dK22T65o1U7Opyai5fO63ShQ4NTIQcalb1jX8q745GO1iolKUE3VbOr606keVb1V@MUcVyxdOZUKvvasVw1XHC29hdyVtJN10EdyjpuWEX61zJYQvmqyDAXdCrP0vb5ixgO0UHHSK83h633B1u28C/x4v6N5tU@LeQocibcgjXIWlXNFqLqP@oJskbRNJ77i7FQCplVaZnHtehhwgqo3tO4UCC@RkapFVBFlGSvbNRQzmAZNFFH12vkws7I0YG6AKnhdIbIcNNr@ISzpdrTg7MYJsQrhO03swOnqMjACc6AHAfaRuuwgPVAtyagwLCk8zGsODfEcxdeQxxOmSgzEdY94Tv5neTJ5jcXUnsYieXChp/OPIiFGz2iTyTc8BENS@FIeWxESV@PJqR8p0s6jgG5wjxIxUQTg3Q4vf2Ewr13GbZRROqJNtigHGzZbcSRCTm/DscPxgv4ngea4r1C5BWkr/coB2Qbb2uOpHYMSh8mxQQ1dVn7HuFIAwjq8Ejf1rAddb5KbNwXu3FTxLQxwu/UCmpv4ngl4hKcHKX@55zm00yO9tNy2skRjXB6GcNUUPfDh8nDUzccZkg7M9sgOnrQ7/e2sVkBCuKSAfhV@AXiBRyMNG1/@7OtfxRk6TtLUEl4Q4C/FByJDBFweTpLKejQqLWmB60N974QOFlI1fy1fBRqcYfQIAkSAonj8Q@ez4iHPiHSY/oCftB8//zxkSMvaqSnr17vvERxdpdA6nuZS3PXzvAexY@y//FI2qM35ORZkaB/FPTR1/Zv8e8dvmMngVf1fy2Ytz8 "Haskell – Try It Online")
# [Haskell](https://www.haskell.org/), Ungolfed
Here's what this looks like ungolfed.
```
balanced :: Parser String
balanced =
  ( choice
    [ string [x]
      <> balanced
      <> string [y]
      <> balanced
    | [x, y] <- ["()", "<>", "{}", "[]"]
    ]
  ) <|> string ""
    <|> string "0"
getBetween :: Int -> Parser String
getBetween pushes
  | pushes > 0 =
  choice
    [ do
      notAhead $ string "<>"
      notAhead $ string "[]"
      start <- string "()" <|> fmap pure (charBy (`notElem` "{})"))
      rest <- getBetween pushes
      pure $ start ++ rest
    , do
      string "{}"
      rest <- getBetween (pushes - 1)
      return $ "{}" ++ rest
    , do
      string ")"
      rest <- getBetween (pushes + 1)
      return $ ')' : rest
    ]
  | pushes == 0 =
  choice
    [ do
      notAhead $ string "<>"
      notAhead $ string "[]"
      notAhead $ char '{'
      notAhead $ char '{'
      notAhead $ char ')'
      start <- choice
        [ string "()"
        , do
          notAhead $ string "()"
          chr <-charBy $ const True
          return [chr]
        ]
      rest <- getBetween pushes
      pure $ start ++ rest
    , do
      string ")"
      rest <- getBetween (pushes + 1)
      return $ ')' : rest
    , pure ""
    ]
getBefore :: Bool -> Parser String
getBefore zeroed
  | zeroed
  =
    choice
      [ pure ""
      , do
        next <- choice $ map char "<{["
        rest <- getBefore zeroed
        return $ next : rest
      , do
        char '('
        rest <- getBefore False
        return $ '(' : rest
      , do
        prefix <- balanced
        guard $ prefix /= ""
        rest <- getBefore zeroed
        return $ prefix ++ rest
      ]
  | otherwise
  =
    choice
      [ do
        next <- choice $ map char "({["
        rest <- getBefore zeroed
        return $ next : rest
      , do
        char '<'
        rest <- getBefore True
        return $ '<' : rest
      , do
        prefix <- balanced
        guard $ prefix /= ""
        rest <- getBefore zeroed
        return $ prefix ++ rest
      ]
mainParser :: Parser String
mainParser =
  do
    before <- getBefore True
    char '('
    inside <- balanced
    guard $ inside /= ""
    char ')'
    between <- getBetween 0
    string "{}"
    after <- many $ charBy $ const True
    end
    return $ before ++ "0" ++ between ++ inside ++ after
zero :: Parser String
zero =
  choice
    [ char '0' *> pure ""
    , choice
      [ char x *> zero <* char y
      | [x, y] <- ["[]", "<>"]
      ]
    , do
      char '('
      zero
      char ')'
      return $ "<(0)>"
    ]
removeZeros :: Parser String
removeZeros =
  choice
    [ do
      notAhead zero
      chr <- charBy $ const True
      rest <- removeZeros
      return $ chr : rest
    , zero <> removeZeros
    , end *> pure ""
    ]
run :: String -> String
run input =
  case
    map snd $ apply (compose mainParser removeZeros) input
  of
    [] ->
      input
    x ->
      head $ map run x
```
[Try it online!](https://tio.run/##zVfdb9s2EH/XX3FwA5hsnS7xYyELSLsVKNACA7anuUJKx3QsTJYESU7sJfnbszvyKJGy3bXYCuwhjnT3u@8PUmvV/Knz/Pnh/AV8VMXtVt1qeJ/rXbbI9YeiaVVxoxt4cf4UZZuqrFv4tdb5dqlhnS2z4jYCEKAWDf6XDvGuLNq6zF9fVVWe3ag2u9MGlmer9mqKjxO4yltdF4YF4vVreUz8U1mopRG8K7OlEUP36qWP/Vm1ioAWIEDEiTzgv1ur2nCz5iqv1soAokLft/tKw6@qbnQNCmZI5xfxW1tjcHCewJyfJ6BkimIKg9rDmze9HIJOwBksGFpJaIyVCv9HUcbZhffb4qYta6fxfq1rSthqoypYIc9XQOKdm2cWI8xPB5cSKk@7V4WhhWpba9iFOgV8hsYLp@FwdjKlrAFXEVa9V5eyf56GLppHGChdlkxGRq03lxOodYNK4nPUxbgAMTWIqUVMgWQ6fq3bbV042MqosmiGSC8XpqWGWXCuQ5LMUMG/cn/oPTfAiiGe575b/jQMnNObqt0fVujaFIcqAuCFcAnxY9K9TYfdEsbR5RpevSIwv/iOCTta2MswS4BfXK2R6Lzc@G6arrIUYmEKdLFkHjcPE6PoBkfzrRknQVNKbr0ty1zSA5sx08u4qtZL6mXtD@st1cN5AvgKQsEbWLhOBJiDWNBAwqOnQUHq8JjIDppap8gl59HQER4Z9knsZjPMGWcPxfplwIKW4BAk2tbqTiPP6CCDZYbZRtm5y23qySsHINFVmS@xB7DO0jZHFFF6@4UkZOTy7SfIT9EwaAxbzNMJisq0B1z7fExLUbZXa62Ww@XX2@0QlSV5PkRujrKi2rYoxqpvVKMH08LCBsiscuV50gtbzw0wcB7MfPggy8Ey3ZR4MDTai@GgXCpMPQtYry75/9SL7VRo/p64NkvC7Ag/yMsgyjABtOcadvt5oXIayOWB31HHmZkjznZKZLueO26@c4mJE3D4nuJQ@1OoR9QwgX1K3s9HQo4mMIoT@n14ot95OrKi9CvNCmKdo5Gh@5SLURTd6vatbu@1LiieD0V7OCwepNo2a5OJR36EBC54Ar1gu3R3XXjWGUVvTzPRfWbi1sM7A0bpWBircd6crWavCTf1X1DTL7nefKEsyJF0xw0Wzag4FkC3Hc/YFC5ewhvWpI/Amcf0ntYqOBnncNnbNmfhmZH8J@XyG3S/OqJ7LMe4XTvNqV@Y2ewHVcZjmg08fhh/P0eOh3X23AwmhgrfUSf@JB/100dT7DXq5j5B2yWepvB7vdUehrM5R2y/tNIf0EL/UZUn1ijPc8ojvCprs0npyD4xwgbyl65Ls0se@0d7tgQFmAdGBokv9M4rGXpII2nqOoof5iPvPujFGVofhGg0ejEODNqeEeOvaH6vcu/06nMnxl/RizeQVbYjRYNVDPbzBhUw5KdZn4vvCYzF/c5wc1q2eAm4z4zXRyvwbRkXPzDj8dcyHoxRn/D4f5nwaKOygmfi4Nz2eFQI9ndhDR2POehIvKNnS30QlYuI2X1EwQpc8AYI98FFdOzwUSv8OCHkRhV73qXHFhvd54OscCyYFTz06Z@zio/sHj4Z9VFEqT1MkqEenCc2lIsxvEyCjTEZNjNf1hFmFMUvLWXPgPBeg4eNvdekkb@OvVYabATSGXC686U/h2NxIZNuaUYRfgCWd/oPlGwOo/WZ33CIBvZrO6mnzhzXy56Joa@kI9j4NmfJgcyESj3MPUZXb4vw88eFhXR7NTZBuQs/bZOmoF7lj2R30/YmwzMtu6syfwz4HwL9LXrXE/mQJjvkwu6ZFMPMZhKpn65BfDYCGEmLzn5EECTemzBysqfB6HMxMmflnI6dpzgW@JPIJEnwAb9ATDImtCCfJA8QNRW9JsKj4OcWkoSQKEP0gDOkEGlAiYmWGGJgs/ujn1AmNtbQXmK5xDSoUeQpiBPfjAnORiZ9qgzNHsihaaL2lAeSmguJgRDaht/juwg72oOQ1roLIX3@Gw "Haskell – Try It Online")
[Answer]
# JavaScript, ~~449~~ ~~600~~ 580 bytes
*-13 bytes thanks emanresu A*
(@WheatWizard wrote their answer first, causing me to look at this challenge; this answer is not intended to steal their glory)
```
x=>{for([...x].reduce((_,b)=>"({[<".includes(b)?(y.unshift([b,--i+"#"]),y[1].push(y[0])):(b==")"&&y[0][2]&&j.push(y[0][1]),x=y.shift()).push(b!="}"|x[3]?b:b+(j.pop()||"-0#")),y=[[]],i=0,j=[]),y=y[0].reduce(g=(a,b)=>b[3]?a+b[0]+b[1]+b.slice(2,-1).reduce(g,"")+b[1]+b.pop():a+b[0]+b[2],"");x!=y;)y=(x=y).replace(/(((<-\d+#|^)([<[({]((-\d+#).+\5)?[\])}>]|X)*)(({-\d+#|^)([<[({]((-\d+#).+\11)?[\])}>]|X)*)*)\((-\d+#)(.*)\12\)(((?!\[\]|<>|\{-|#}).)*){}\12|\((-\d+#)(X)\16\)(((?!\[\]|<>|\{-|#}).)*){}\16|\[-\d+#X-\d+#\]|<-\d+#X-\d+#>/,"$1X$18$17$14$13");return y.replace(/-\d+#|X/g,"")}
```
[Try it online!](https://tio.run/##fZH/bpswEMdfZXFQdFfAidOtq1JMXgPJeBNOaEuEQgShAmGePTsTpen@2GTprPP3cz99yD6yZlcXp3P48XzZVcemKnNeVm8Al07Gw2tVg@Kcd5rX@b7d5QC/A4MyZjCoiPHiuCvbfd6AwS30vD0278XrGZQJwrDw2ZxpDHolND@1zTv0aqURN2CkZMgWC@ertV4sDnedYAw62fNrJsSrZGaSjcx26lFvzcb4QCHVCdBaFq7mDKmMVErroJCr4CCVqytdvlvfbxKyqXPjUmS@IY2MIMObsiBiHYQCP/GAMbzpU6XNZ8xaO/Glm8n@BXsJ1K2LO5UZBS4BIArTvT@3vxBUpGDQANMDcj/9gVuVahxjbRN8QIDh36wQf8MPmN5U4OSIdUoJYDtLibJRbNMhtPMROZHDSLK98wnhT//Hn2yqJjqZrGO@uPEyYJ5IPPHsiZ@e@O6JR9pBnZ/b@vitv49/HSdZTgscLwgMIgB0B2M370jFhtHdSN92@QM "JavaScript (V8) – Try It Online")
A horrific solution that uses string manipulation.
First, it recursively parses the program and adds annotations:
```
original:
(<(()()())>)(({}){}{}({}))
annotated:
(-1#<-2#(-3#()()()-3#)-2#>-1#)(-7#(-8#{}-1#-8#){}-8#{}-3#(-12#{}-0#-12#)-7#)
```
The `-N%`s inside brackets denote matching brackets. Additionally, `{}`s are annotated with the `-N#` of the `()` they pop.
Then, regex substitutions are repeatedly applied until it stabilizes (`X` is used instead of `0`):
(this is an explanation of the old regex; the new one that accounts for more cases is beyond explanation)
```
/\((-\d+#)(.*)\1\)(((?!\[\]|<>|\{-|#}).)*){}\1/X$3$2
 \(                                                   literal open paren
   (-\d+#)                                            group 1, matches a -N#
          (.*)                                        group 2, this is A
              \1\)                                    matching close paren
                  (((?!\[\]|<>|\{-|#}).)*)            group 3, this is B
                    (?!\[\]|<>|\{-|#})                there can be no [], <>, {-, or #}
                                          {}\1        the {} that pops (A)
                                               X$3$2  replace with X, followed by groups 2 and 3
/\[-\d+#X-\d+#\]/X  replace [-N#X-N#] with X
/<-\d+#X-\d+#>/X  replace <-N#X-N#> with X
```
In the actual implementation, these are all combined into a single unioned regex.
The `(0)` case from the original algorithm is just a special case of the `(A)B{}` -> `0BA` transformation, so no special casing is needed for it.
Once it stabilizes, all `X`s (these must be have a sibling) and `-N#`s are removed, and the resulting string is returned.
]