Expression

By definition, a symbolic expression is:

a) a natural number;

b) a name made by a succession of letters that identifies another symbolic expression;

c) a list formed of 0 or more symbolic expressions, separated by a space, delimited by round brackets. An example of symbolic expression created from a list with 3 elements is: (A 2 (3 (B))).

A definition assigns a name to a symbolic expression and it has the following form:

Name = SymbolicExpression

Two symbolic expressions E1 and E2 are equivalent if:

1. E1 is a number, E2 is a number and they have the same value;
   
2. E1 and E2 are the names of two equivalent symbolic expressions;
   
3. E1 and E2 are equivalent lists; two lists are equivalent if they contain the same number of symbolic expressions, and the expressions from the corresponding positions are equivalent.
   
4. The equivalence relation between expressions is transitive (if expression E1 is equivalent to expression E2, and expression E2 is equivalent to expression E3, than we infer that E1 is equivalent to E3).
   
5. If after applying the rules a)-d) you can not decide on the equivalence (or unequivalence) of the expressions, than they will be considered equivalent.

For example:

1. The symbolic expression (1 2) is not equivalent with (2 1).
   
2. The symbolic expressions (1 (2 3) 4) and (1 (2) (3 4)) are not equivalent.
   
3. For the following definitions:
   A = B
   
   B = (1 (2 abc))
   
   abc = (1 34)
   
   X = ((1 (2 abc)) (1 34))
   
   Y = (A abc)
   
   Z = (1 2 abc (1 34))
   
   The symbolic expressions X and Y are equivalent. The symbolic expressions X and Z are not equivalent.
   
4. For the following definitions:
   A = B
   
   C = (D E)
   
   B = (D E)
   
   The expressions A and C are equivalent.
   
5. For the following definitions:
   The symbolic expressions A and B are equivalent (according to rule e).

An interrogation is used for testing the equivalence of two symbolic expressions and it has the following form:

Expression1 ? Expression2

The result of an interrogation is either 0 or 1 ( 0 if the expressions are not equivalent and 1 otherwise).

Write a program that reads from a file a succession of definitions, followed by a series of interrogations and displays the result of the interrogations.

The input contains a succession of expression definitions (each definition on a new line), terminated (on a separate line) with the tag EOD, after which follows a succession of interrogations (one interrogation per line), ended (on a separate line) with the tag EOE.

Constrains and specifications:

The number of definitions is smaller than 30
The number of interrogations is smaller than 30
The number of symbols from a list, different from spaces and brackets, is smaller than 50.
The sign = from a definition, respective the sign ? from an interrogation are bordered by one space.
The name of an expression is at most 8 characters long.
The natural numbers are smaller or equal than 30000
The name of a symbolic expression may appear in the definition of that expression.
In the input file there is a single definition for each symbolic expression.
The order of the definitions in the input file does not matter.
The names of the symbolic expressions are not case sensitive.

The output contains one line for each interrogation from the input file, on which line will be displayed the result of the interrogation (0 or 1).

A = 12
B = 13
BB = 12
Bbb = (12)
G = (1 (1 E))
c = (1 2 3)
D = (1 2 3)
dD = (1 2 6)
E = (1 E)
F = (1 E)
EOD
A ? B
A ? BB
C ? D
c ? DD
E ? E
F ? E
G ? E
BB ? bbb
EOE

0
1
1
0
1
1
1
0

Compiler C C++ Java Python2 Python3

Use advanced editor

Code