Background
In Haskell and many other functional languages, function application f(x)
is simply written as f x
. Also, this form of function application is left-associative, which means f x y z
is ((f x) y) z
, or ((f(x))(y))(z)
.
Haskell also has a binary operator called $
. f $ x
does function application just like f x
, but it is right-associative, which means you can write f $ g $ h $ x
to mean f(g(h(x)))
. If you used Haskell enough, you might have once wondered, "would it be nice if f x
itself were right-associative?"
Now it's about time to see this in action. For the sake of simplicity, let's assume all the identifiers are single-character and omit the spaces entirely.
Challenge
Given a valid expression written using left-associative function application, convert it to the minimal equivalent expression where function application is right-associative. The result must not contain any unnecessary parentheses.
An expression is defined using the following grammar:
expr := [a-z] | "(" expr ")" | expr expr
To explain this in plain English, a valid expression is a lowercase English letter, another expression wrapped in a pair of parens, or multiple expressions concatenated.
I/O can be done as a string, a list of chars, or a list of codepoints. The input is guaranteed to have minimal number of parens under left-associative system.
Standard code-golf rules apply. The shortest code in bytes wins.
Test cases
input -> output
---------------
foo -> (fo)o
b(ar) -> bar
q(uu)x -> (quu)x
abcde -> (((ab)c)d)e
f(g(hx)) -> fghx
g(fx)(hy) -> (gfx)hy
f . g . h $ x
. \$\endgroup\$