# Explicit-ify APL expressions involving trains

Related: Clearly parenthesize APL trains

## Background

In the most basic form, APL has two kinds of tokens: arrays and functions. For this challenge, we will use a lowercase letter a-z for an array, and an uppercase letter A-Z for a function. Furthermore, we will assume each character is a token of its own; Fx is equivalent to F x.

APL has two ways to call a function: monadic (taking one argument) and dyadic (taking two arguments). Monadic application is written in prefix F x, and dyadic one is written in infix x F y. There's nothing like "operator precedence"; an APL expression is always evaluated from right to left, which can be overridden with parentheses ().

x F G y -> x F (G y)
F x G y -> F (x G y)
x F y G z -> x F (y G z)
(F x) G H y -> (F x) G (H y)


A train is a way to compose functions to derive a more complex function. In essence, a train is formed when the rightmost token is a function. Here are the rules for 2- and 3-token trains:

(F G H) x -> (F x) G (H x)
(u G H) x -> u G (H x)
(G H) x -> G (H x)

x (F G H) y -> (x F y) G (x H y)
x (u G H) y -> u G (x H y)
x (G H) y -> G (x H y)


For 4-token and longer trains, the rightmost 3 tokens are recursively grouped to form a derived function until 2 or 3 tokens remain. As a whole, it can be thought of as follows:

Odd-length trains
(V D V D ... V D V) x -> (V x) D (V x) D ... (V x) D (V x)
x (V D V D ... V D V) y -> (x V y) D (x V y) D ... (x V y) D (x V y)

Even-length trains
(M V D V D ... V D V) x -> M (V x) D (V x) D ... (V x) D (V x)
x (M V D V D ... V D V) y -> M (x V y) D (x V y) D ... (x V y) D (x V y)


If an array u appears at the V position (other than the last), replace the cooresponding (V x) or (x V y) simply with u. An array appearing at M or D position is a syntax error.

Note that trains may also have sub-expressions that evaluate to an array or a function:

x ((D a) F G (u H J) K) y
Expand 5(odd)-token train, leftmost V position being an array (D a)
-> (D a) F (x G y) (u H J) (x K y)
Expand 3(odd)-token train (u H J)
-> (D a) F (u H (x G y) J (x K y))


## Challenge

Given a line of APL expression that evaluates to an array (which may or may not include one or more trains), convert it into an equivalent expression without a train.

You can assume that the input is valid under the rules stated above, and it doesn't contain any spaces. You don't need to worry too much about parentheses or spaces in the output; lacking or redundant parentheses/spaces are fine as long as they represent the equivalent expression.

Standard rules apply. The shortest code in bytes wins.

## Test cases

x(XY)y -> X(xYy)
uKKKv -> uKKKv
U(xVW)yZa -> UxVWyZa
MnP(QRsTU)VWx -> MnP(QVWx)RsTUVWx
x(XXxYYYdDD)y -> (xXy)XxY(xYy)YdDxDy
a((DEF)GHJ)Kb -> (D(aGKb)HaJKb)EF(aGKb)HaJKb
c((k(PQRSTU)m)(VW)(XY)(ZA)BCD)n -> V(P(kQm)R(kSm)T(kUm))WZ(XcYn)A(cBn)C(cDn)

• explicitize
– ngn
Jun 5, 2020 at 11:47

# APL (Dyalog Classic), 63 59 58 54 52 51 bytes

∊⍎'.[A-Z].'⎕r'{0::&⍵⋄''() '',⍪⍺&⍵}'⊢'\w'⎕r'''&'''⊢⍞


Try it online!

put all letters in quotes, replace uppercase letters with dfns that return either "(left) self right" or "self right" depending on the presence of a left arg, and execute.

# Python3, 887 bytes:

def p(s):
r=[]
while s and(S:=s[0])!=')':
if S.isalpha():r+=[s[0]]
if'('==S:r+=[(K:=p(s[1:]))[0]];s=K[1]
s=s[1:]
return r,s
F=lambda x:(O:=ord(str(x)[0]))<=91 and(64<O<91 or all(F(i)for i in x[-2:]))
R=lambda x:[i for i in x if i]
def f(s,l=0,r=0):
if F(s):
J=[]
while s:
if F(S:=s.pop(0))==0:J+=[S]
else:
if len(s)>1 and F(s[0])==0:J+=[[S,s.pop(0)]]
else:J+=[S]
s=J
c,s=[f([*s[0]])]if(t:=F(s[0])==0)else[],s[t:]
c+=[f(R([l,s[0],r]))]if(S:=sum(map(F,s))%2)else[];s=s[S:]
while s:
if F(s[0])==0:c+=[s[0]];s=s[1:];continue
a,b=s[:2];c+=[a,f(R([l,b,r]))if F(b) else f(b)];s=s[2:]
return f(c)
c=[]
while s:
if F(j:=s.pop(0)) and type(j)==list:
c+=[f(j,l=c and not F(c[-1])and c.pop(),r=f(s))]
else:c+=[j]
return c
P=lambda e,l=0:e if str==type(e)else '('*(Y:=(l>0 and len(e)>1))+''.join(P(i,l+1)for i in e)+')'*Y
M=lambda s:P(f(p(s)[0]))


Try it online!

This ended up being longer than I had originally anticipated, but this is an intriguing problem, and I thought I would add a non-APL, parsing-based solution.