S and K

You may wonder what is the simplest computer we can build that can still perform useful computation. Over the years theoretical computer scientists have devised several simple models of computation, such as Turing machines and the lambda calculus. In this problem we explore an even simpler system, devised in 1924 by Moses Schönfinkel, that uses only the two letters $S$ and $K$. We arrange these letters into a binary tree to give them structure: every leaf of the tree is either an $S$ or a $K$.

We encode such a binary tree as a string as follows. A leaf is written as either $S$ or $K$. An internal (non-leaf) node is written as $(ab)$, where $a$ is the string for its left child and $b$ is the string for its right child. For example, one such tree is written as the string $((SK)K)$.

The tree is transformed by repeatedly applying the rules below. On each step we try the rules in the given order — rule (1) first, then rule (2), and so on — and as soon as one rule performs a transformation we start over, checking again from rule (1) at the root of the whole tree.

1. If the tree has the form $((Ka)b)$, where $a$ and $b$ are arbitrary subtrees, replace the whole tree with just the subtree $a$.
2. If the tree has the form $(((Sa)b)c)$, where $a$, $b$, and $c$ are arbitrary subtrees, replace it with $((ac)(bc))$ — one copy each of $a$ and $b$, and two copies of $c$.
3. Otherwise, apply these rules recursively to the subtree that is the left child of the current node.
4. Otherwise, apply these rules recursively to the subtree that is the right child of the current node.
5. If no rule can be applied anywhere, print the string representation of the resulting tree and stop.

How do these simple rules perform computation? We first fix a representation of the natural numbers. Many are possible; the most popular is due to Alonzo Church. Define zero as $0 = (K((SK)K))$ and a successor operator $\sigma = (S((S(KS))K))$. The natural numbers are then $1 = (\sigma 0)$, $2 = (\sigma 1)$, $3 = (\sigma 2)$, and so on, each time substituting the subtree we defined for every symbol such as $\sigma$ and $0$. So the number $4$ is represented by the tree

$$\displaystyle 4 = ((S((S(KS))K))((S((S(KS))K))((S((S(KS))K))((S((S(KS))K))(K((SK)K))))))$$

Notice that this has four occurrences of the subtree $\sigma$ followed by the subtree $0$. Numbers encoded this way can be added using the subtree

$$\displaystyle + = ((S((SK)K))(K(S((S(KS))K))))$$

For example, if we build the tree $((+3)4)$ — again replacing $+$, $3$, and $4$ with their subtrees — and apply the transformation rules, we eventually reach the tree for $7$. Multiplication can be done with the simpler subtree $* = ((S(KS))K)$. However, results produced by some operators such as $*$ may not literally look like the numbers defined above, even though they behave the same way. We can apply a normalization operator

$$\displaystyle N = ((S((S((SK)K))(K(S((S(KS))K)))))(K(K((SK)K))))$$

to make equivalent numbers look identical. For instance, applying the transformation rules to the tree $(N((*2)4))$ produces the tree for $8$.

With a little more work we can build trees for other operations one expects in a programming language, such as comparisons, conditionals, and recursion, and combine them into larger programs. For example, the following tree computes factorials:

$$\displaystyle \begin{align*} ! &= ((((SS)K)((S(K((SS)(S((SS)K)))))K))((S(K(S((S((S((S((SK)K))(K(K(K((SK)K)))))) \\ &\mathrel{\phantom=} (KK)))(K((S((S(KS))K))(K((SK)K))))))))((S(K(S((S(KS))K))))((S((S(KS))K)) \\ &\mathrel{\phantom=} (K((S(K(S(K(S(K((S((SK)K))(K(K((SK)K))))))))))((S((S(KS))((S(K(S(KS)))) \\ &\mathrel{\phantom=} ((S(K(S(KK))))((S((S(KS))K))(K((S((S(KS))((S(K(S(K((S((S(KS))((S(KK))((S(KS)) \\ &\mathrel{\phantom=} ((S(K(S((SK)K))))K)))))(KK))))))((S((S(KS))K))(K((S((SK)K))(KK))))))) \\ &\mathrel{\phantom=} (K((S((SK)K))(KK))))))))))(K(K((S((S((S(KS))((S(KK))((S(KS)) \\ &\mathrel{\phantom=} ((S(K(S((SK)K))))K)))))(KK)))((SK)K))))))))))) \end{align*}$$

If we combine it with the normalization operator and the number $4$ and apply the transformation rules to the tree $(N(!4))$, we obtain the tree representing $24$ (that is, $4!$).

The input consists of several strings, each representing a tree, one tree per line. No input line contains more than $1000$ characters. The last line of the input is blank.

For each input line except the final blank line, repeatedly apply the transformation rules to the given tree until no further transformation is possible (rule 5), then print, on its own line, the string representation of the resulting tree. Note that for some trees, such as

$$\displaystyle (((S((SK)K))((SK)K))((S((SK)K))((SK)K)))$$

the rules can be applied forever; no such tree appears in the test data.