Combinatory logic is a simple language that is used for descibing computational expressions. An expression consists of parentheses, variables and operators S and K. In this task we will consider only those expressions that do not contain variables. Write a program that will read in an expression in combinatory logic, reduce it (i.e. evaluate it as much as possible) and output the whole procedure.
The input contains a string consisting of letters S and K and validly-nested parentheses. Operators S and K act on other operators and expressions that follow them in the following way:
- Kxy = x,
- Sxyz = xz(yz),
where x, y and z represent some expressions. In an expression with multiple operators the evaluation is done from left to right. Examples of evaluation can be found in sample tests below.
The expression will not contain redundant parentheses. Parentheses are redundant if their removal does not change the meaning of the expression. In particular, we can always remove parenthesis that enclose a single symbol, e.g. expression (S) becomes S. Moreover, we can always remove left-aligned parentheses, e.g. (((SK)K)S)S becomes SKKSS. Another example: Some parentheses in the expression (S((KK)S(K))) can be removed so that the expression becomes S(KKSK).
If the operator S or K is not followed by a sufficient number of arguments, the evaluation can not be done. The argument is always the shortest non-empty string that follows the operator and is a valid expression. In the expression SK(SK)SK the (three) arguments of the first S operator are: K, (SK) and S. The last symbol (i.e. K) is not an argument of the S operator, since S only takes 3 arguments.
Write a program that will read in an expression and reduce it. Your program should output the current expression after each single evaluation. If there are many possible operators that can be evaluated, you should always choose the the leftmost one. It is guaranteed that this procedure ends in a finite number of steps and that total size of the output will not exceed 20\,000 characters.
The first line contains a string that is composed of letters S and K and validly-nested parentheses. The string will not contain unnecessary parentheses.
The length of the string will not exceed 1000.
Output all the steps in the procedure of reduction. The expressions in the output should not contain redundant parentheses. For the exact format see the examples below.
The total size of the output will not exceed 20\,000 characters.
SKKK =KK(KK) =K
S(SK)(KS)(SKK) =SK(SKK)(KS(SKK)) =K(KS(SKK))(SKK(KS(SKK))) =KS(SKK) =S
In the first example, we first evaluate the leftmost S operator, and then the leftmost K operator.
In the second example, we evaluate the leftmost operator in each step.
In the third example, none of the operators has a sufficient number of arguments, therefore the expression can not be reduced.
In the fourth example, the leftmost operator (namely, the S operator) has an insufficient number of arguments, therefore we evaluate the leftmost K operator.
In the fifth example, none of the operators has a sufficient number of arguments, therefore nothing can be reduced. The leftmost K operator only has one arguments, since its "scope" is only within the parentheses.
- submit and test your solution
- post or read questions and answers about this task