Flatten a Stack Cats program

Question

Stack Cats is a reversible, stack-based language. Its reversible nature makes for somewhat weird loops. This challenge is about the conditional loop (...). When these loops are nested in certain ways, it's possible to transform the code to reduce the nesting depth. Here are the rules (where A and B stand for an arbitrary snippets):

1. When one loop starts with another loop, we can extract the inner loop to the front: ((A)B) becomes (A)(B).
2. When one loop ends with another loop, we can extract the inner loop to the end: (B(A)) becomes (B)(A).
3. Empty loops, (), can be removed from the program entirely. As a corollary (in conjunction with the other rules), ((A)) is equivalent to (A).

The only nested loops that will remain are of the form (A(B)C), where A, B and C are non-empty.

The Challenge

You're given a valid Stack Cats program and your task is to reduce the nesting level of loops as much as possible, leaving no empty loops, using the above transformations.

A valid Stack Cats program...

• ... consists only of the characters ()/\<>[]{}!"*+-:=ITX^_|.
• ... has mirror symmetry (e.g. \(]{}!{}[)/ is a valid program, but /|/ isn't).
• ... has correctly matched and nested () and {} ([], <> and \/ don't necessarily need to be matched as usual, although they'll appear in pairs due to the mirror symmetry requirement).

You can take either a string or a list of characters as input, but output needs to be presented in the same format.

You may write a program or a function and use any of our standard methods of receiving input and providing output. Note that these loopholes are forbidden by default.

This is code-golf, so the shortest valid answer – measured in bytes – wins.

Test Cases

Test cases are two lines each (input and output), separated by empty lines. Note that one output is empty. You also need to support the empty input (which should result in empty output).

(((=+|+=)))
(=+|+=)

({(=+|+=)})
({(=+|+=)})

((\)/)I(\(/))
(\)(/)I(\)(/)

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


((<|>((X((T)))[_]))\^/(([_](((T))X))<|>))
(<|>)(X)(T)([_])(\^/)([_])(T)(X)(<|>)

Answer 1

Retina 0.8.2, 113 107 67 66 bytes

+`\(\)|(\()?(\(((\()|(?<-4>\))|[^()])*(?(4)@)\))(?(1)|(\)))
$5$2$1

Try it online! Includes 3 4 byte saving thanks to @MartinEnder. Explanation:

+`

Repeatedly apply the substitution until there are no matches.

\(\)|

Match an empty loop (in which case nothing is captured so the substitution simply deletes it) or:

(\()?

Optionally match a (. This is captured in group 1 if it matched, but not if it didn't.

(\(

Capture the main body of the match in group 2 and match a (.

(
 (\()
|
 (<-4>\))
|
 [^()]
)*

Repeatedly match either a (, capturing it in group 4, or a ), removing a capture from group 4 (failing if there isn't one), or something else.

(?(4)@)

Ensure that there are no spare captures left in group 4.

\))

End capture group 2 with another ).

(?(1)|(\)))

If capture group 1 was empty, then capture a ) in capture group 5. (So exactly one of those two groups will have a capture).

$5$2$1

Move the bracket captured in either group 1 or group 5 to the other side of group 2. This has the effect of moving the inner loop to the front or the end of the outer loop depending on which side it matched.

Answer 2

Stax v1.0.3+, 76 65 64 62 58 bytes^CP437

îÜ•$o,Γ{í]Üf╒9♦╛üΣóç*\$ñ₧└ΦJ♠¥c╥jóu≥3E.╘ⁿ◄◘W₧<¶┼7úê╟┴zç↨aG

70 bytes when unpacked,

{{.((:/Yc{Z{40=+_41=-c^Ci~^Fdy,,\32&jEa:{a:{a4l$c}Md}X!:Rx!:Rc.()z:rgp

Run and debug online!

Explanation

{.((:/Yc{Z{40=+_41=-c^Ci~^Fdy,,\32&jEa:{a:{a4l$c}Md is a block that separates A((B)C)D into four parts and convert it to A(B)(C)D.

X!:Rx!:R executes the block on the input string (step 1), then reflects the string (string reflection in Stax refers to reversing the string plus replacing (translating) (<[{/ with (to) \}]>) ) and execute the block on the string obtained, and then reflect it back (step 2). Step 2 is essentially converting (A(B)) to (A)(B).

c.()z:r remove all empty loops (step 3).

gp is a generator that finds the fix point of an iteration. In this case the string is iterated with the 3-step process until it no longer changes.

Implicit output.

Answer 3

Python 3, 226 223 212 206 bytes

Okay, here is an attempt to solve this in a language that doesn't support recursive regex.

lambda s:g(g(s,*'()'),*')(').replace('()','')
def g(s,t,u):
 m,*a={},;i=v=0
 for c in s:
  i+=1;a+=[i]*(c==t)
  if c==u:*a,x=a;m[x]=i;v=m.get(x+1)
  if v:return g(s[:x]+s[x+1:v]+t+s[v:],t,u)
 return s[::-1]

Try it online!

Edits:

• Refactored [::-1] to save 6 bytes, thanks to Mr.Xcoder.

The g function is the basic building block, which finds an occurrence of ((A)B), changes it to (A)(B), then applies itself to the result until no more transformation is possible.

The main steps are:

• Apply g to the input normally.
• Apply g to the input flipped. This run finds the occurrence of ))A(B( in the reversed input, which effectively handles (A(B)).
• Remove any occurrence of ().

The problem is, g has so bad control structure that trying to one-line it made it bloat badly, so I don't think major improvement is possible based on this solution.