What if function application was right-associative?

Question

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

Answer 1

JavaScript, 71 bytes

Saved 2 bytes by Arnauld.

f=(e,l='',r=e.shift())=>(r=r>{}?r:r<f&&f(e))?f(e,l[1]?`(${l})`+r:l+r):l

Try it online!

• l, r are two operand

Answer 2

Perl 5 -p, 73 bytes

1while$e='(\w|\((?1)*\))',s/$e$e(?=$e)/($&)/;1while s/\(($e*)\)(?!$e)/$1/

Try it online!

Answer 3

Jelly, 60 bytes

;Ṫ$FL$¡1ĿØ(jƊ¹ŒḊ?€
=þØ(Ä_Ż}ỊṖʋ/aSƲœp⁸;2ĿW$}¥2/Ẏ3œṖW;¥2/ẎƲÐLÇ

Try it online!

A full program taking a string argument and printing the result to STDOUT. Uses recursion in both links, but in both cases replacing 1Ŀ or 2Ŀ with ß fails to work.

Answer 4

Retina 0.8.2, 94 bytes

+1`((\w|(\()|(?<-3>\)))+?(?(3)^)){2}(?!\))
($&)
+`\(((\w|(\()|(?<-3>\)))+)\)(?(3)^)(?=\)|$)
$1

Try it online! Link includes test cases. Explanation:

+1`

Make the first possible substitution each time, looping until no more substitutions are possible. This means that in the case of abcde, only ab is surrounded the first time, then (ab)c the second time, et cetera.

((\w|(\()|(?<-3>\)))+?(?(3)^)){2}(?!\))
($&)

Put parentheses around any pair of expressions that does not already have one.

+`\(((\w|(\()|(?<-3>\)))+)\)(?(3)^)(?=\)|$)
$1

Remove any parentheses not needed under right association.

Answer 5

Charcoal, 53 bytes

Ｆ⁺(Ｓ¿⁼ι(⊞υ⟦⟧«Ｆ⁼ι)≔⪫⊟υωιＦ‹¹Ｌ§υ±¹⊞υ⟦⪫()⪫⊟υω⟧⊞§υ±¹ι»⪫⊟υω

Try it online! Link is to verbose version of code. Explanation:

Ｆ⁺(Ｓ

Loop over the input with an extra ( prefixed as this is golfier then setting up the stack manually.

¿⁼ι(⊞υ⟦⟧«

For each (, push a new empty list to the stack.

Ｆ⁼ι)

If the next character is a ), then...

≔⪫⊟υωι

the next term is actually the joined list at the top of the stack.

Ｆ‹¹Ｌ§υ±¹

If the list at the top of the stack already has two terms, then...

⊞υ⟦⪫()⪫⊟υω⟧

... replace it with a list of a () wrapped term.

⊞§υ±¹ι

Push the current term to the list at the top of the stack.

»⪫⊟υω

Join and output any remaining terms.