14
\$\begingroup\$

Imagine a simple SKI calculus expression - for example, (((S α) β) γ). As you can see, each node of the rooted tree has exactly two children. Sometimes though, the parentheses are omitted and the tree is unrooted (just to make the notation clear, I believe). The challenge is to put the parentheses back, so that the tree is binary and rooted again.

The preferable way of I/O is mostly up to you; although the input and output has to at least look like the SKI calculus, and it obviously has to represent a tree.

The rule on adding parentheses is simple: α β γ becomes ((α β) γ) (bind to the left), α β γ δ becomes (((α β) γ) δ), and so on.

You may assume that the input is a correct SKI-calculus expression.

If it wasn't clear enough, you may NOT add more braces than necessary. And if it helps you in any way, you can assume that the input contains no redundant parens (like, for example, (((SK)))).

Examples

S(KS)K => ((S(KS))K)
SS(SK) => ((SS)(SK))
\$\endgroup\$
8
  • 1
    \$\begingroup\$ I'm not sure I understand the challenge completely: does using specifically SKI calculus rather than random letters affect things? \$\endgroup\$ Jun 14, 2020 at 17:13
  • \$\begingroup\$ Well - no, not really, but I'd like to ask specifically about SKI calculus. It doesn't change anything, though \$\endgroup\$ Jun 14, 2020 at 17:22
  • \$\begingroup\$ Does the program have to remove extra, unneeded parentheses? For example, what if the input is (S) or ((S))KK? \$\endgroup\$ Jun 14, 2020 at 17:40
  • \$\begingroup\$ In the second example, would answer of ((SS)((SK))) be wrong? If so, why? \$\endgroup\$
    – Abigail
    Jun 14, 2020 at 17:54
  • 1
    \$\begingroup\$ What are the nesting rules? Does A(BCDE)F become ((A(((BC)D)E))F)? \$\endgroup\$ Jun 14, 2020 at 18:24

2 Answers 2

5
\$\begingroup\$

Perl 5 -p, 37 bytes

s/(\w|\((?1)*\)){2}(?!\))/($&)/&&redo

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ very nice, "regular" expressions parsing a proper context-free language :) \$\endgroup\$
    – ngn
    Jun 15, 2020 at 0:03
2
\$\begingroup\$

Charcoal, 52 bytes

≔⟦⟧ηFθ¿⁼)ι≔⊟υη«F⁼Lη²⊞η⮌E²⊟η¿⁼(ι«⊞υη⊞η⟦⟧≔§η¹η»⊞ηι»⭆¹η

Try it online! Link is to verbose version of code. Outputs a stringified tree-like nest of lists. Explanation:

≔⟦⟧η

Start with an empty tree.

Fθ

Loop over the input characters.

¿⁼)ι

If this is a ), then...

≔⊟υη

... restore the parent node saved below, otherwise:

«F⁼Lη²

If the current node already has two children, then...

⊞η⮌E²⊟η

... remove them and put them in a first child node. (I can't wrap them in a node, since its parent is still pointing to it.)

¿⁼(ι«

If this is a (, then...

⊞υη

... save the current node, ...

⊞η⟦⟧

... push an empty node, ...

≔§η¹η»

... and set that as the current node.

⊞ηι»

Otherwise push the letter to the current node.

⭆¹η

Stringify and output the tree.

56 bytes for pretty output:

≔⟦⟧ηF⁺θI«≔⪫()⪫ηωζF⁼Lη²≔⟦ζ⟧η≡ι(«⊞υη≔⟦⟧η»)«≔⊟υη⊞ηζ»⊞η黧η⁰

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

≔⟦⟧η

Start with an empty tree.

F⁺θI«

Loop over the input characters, but add an extra I to ensure that the final result is wrapped in () if necessary. (If the result can always be wrapped in (), then this can be F⪫()θ« and the last part can be »ζ for an overall saving of 1 byte.)

≔⪫()⪫ηωζ

Get what the bracketed expression would be.

F⁼Lη²≔⟦ζ⟧η

If the current node already has two children then replace it with a node with the bracketed expression.

≡ι

Switch on the current character.

(«⊞υη≔⟦⟧η»

If it's a ( then save the current node and start a new node.

)«≔⊟υη⊞ηζ»

If it's a ) then retrieve the saved node and push the bracketed expression to it.

⊞ηι

Otherwise push the letter to the current node.

»§η⁰

Output the desired expression.

\$\endgroup\$
1
  • \$\begingroup\$ the output is correct; well done. \$\endgroup\$ Jun 14, 2020 at 19:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.