Your program has to read lambda expression and to do 3 basic operations of the lambda calculation: calculate the “spent” variables, calculate the free variables, and do substitutions.
The language of the lambda expressions (expressions from now on) is described with the following three cases and no one else:
'a'
to 'z'
are
expressions (variables).
'\'
, followed by v, followed by the character
'.'
followed B (\
v.
B) is an expression
(abstraction).
'('
, followed by F, followed by the character ' '
(space), followed by A, followed by the character ')'
((
F
A)
) is an expressionn (application).
The set of spent variables VG(E) of an expression E is
the set of all the variables from 'a'
to 'z'
that
appear in the expression E, in any way. Equally,
VG(E)=  ⎧ ⎪ ⎨ ⎪ ⎩ 

The set of the free variables VL(E) of an expression E is defined:
VL(E) =  ⎧ ⎪ ⎨ ⎪ ⎩ 

The substitution E[x := E′] of a variable v in an expression E by other expression E′ is defined:
E[x := E′] =  ⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ 

Notice that, when E has the form \
v.
B, it is not
possible to do the substitution. This can always be
corrected applying an alpha conversion, described in the next lines,
in the expression \
v.
B replacing v with a no spent
variable. However, the inputs of the problems will be in a way that
you will never need to do an alpha conversion to do a substitution.
Input
A test data is a sequence of calculations, each one of them takes a line. The calculations can be “G E”, “L E” or “S x E E′”, where E and E′ are valid expressions and x is a variable. No line will take more than 2000 characteres. In the calculation of types S we assure you that the substitution can be done it, without being necessary that you do any alpha conversion in any moment.
Output
For each calculation, your program must print a line with the answer. It must print the spent variables VG(E) of E if the petition is of the type G, the free variables VL(E) of E if is of the type L, and the substitution E[x := E′] if the petition is of the type S. It must print a set of variables as a sequence in alphabetical order (look the instances). Notice that the result of the substitution may be longer than 2000 characters.
Scoring
Tests with less than 200 expressions that only contain calculation petitions of type G.
Tests with less than 200 expressions that only contain calculation petitions of type L.
Tests with less than 200 expressions that only contain calculation petitions of type S.
Observation (not related to the problem)
If you are able to solve this problem, you are very close to be able to evaluate lambda expressions. We describe the necessary steps below.
The change in the name of the variable v in expressions like
\
v.
B creates equivalent expressions.
Any expression like (\
x.
B
A)
is reduced to B[x := A], where may have been necessary
to apply an alpha conversion to x.
B
renaming x to no spent variable.
It is said that an expression is in a normal form when no more beta reductions can be applied to any of its subexpressions.
Input
G x G \x.(x \y.(x y)) G (x y) G \x.(x y) G (\x.x f) G (\x.(x \x.x) f) G (\y.\x.y x) G (((\c.\t.\e.((c t) e) \a.\b.a) a) b)
Output
x xy xy xy fx fx xy abcet
Input
L x L \x.(x \y.(x y)) L (x y) L \x.(x y) L (\x.x f) L (\x.(x \x.x) f) L (\y.\x.y x) L (((\c.\t.\e.((c t) e) \a.\b.a) a) b)
Output
x xy y f f x ab
Input
S x x y S y y y S x x (x z) S x (x x) (x z) S x (x (y x)) (\x.(f f) g) S x \x.x (a a) S x \y.x (a a) S x \y.(x \x.(x x)) (a z)
Output
y y (x z) ((x z) (x z)) ((\x.(f f) g) (y (\x.(f f) g))) \x.x \y.(a a) \y.((a z) \x.(x x))