11411번 - Equivalence 다국어

A propositional formula is generated by the following grammar:

 <formula> ::= <variable> | ~<formula> | ( <formula> ) | <formula> <operator> <formula>
<operator> ::= ^ | V
<variable> ::= a-zA-Z (except character V)

where ‘^’ encodes boolean AND, ‘V’ encodes boolean OR.

An interpretation is a truth-assignment for all variables ocurring in a formula. The truth-value of a formula with respect to an interpretation can be determined by applying boolean operations on the values of variables, in the standard way.

Two propositional formulae are equivalent if they produce the same truth-value for all possible interpretations.

The input file will contain two formulae generated by the above grammar. The formulae are separated by the newline character. Variables are encoded by alphabetic characters, except the character ‘V’ which is reserved for encoding OR . Each formula will have at most 51 variables. Whitespaces can occur freely anywhere in the input. 

The output must be 1 if the two formulae are equivalent, and 0 otherwise.

In your implementation, you do not need to take into account operator precedence (priority). For instance, a formula such as:

x ^ y V z

will be presented as either

(x ^y) V z or
x ^ (y V z).