Formula Equivalence

Time limit1sMemory limit256 MB

Summary

Decide whether two Boolean formulas with AND, OR, and NOT over at most 16 variables agree on every truth assignment.

Level: Medium5 of 10
Topics: Brute force, Recursion
Solved: No attempts yet

Problem

A propositional formula is generated by the following grammar.

 <formula> ::= <variable> | ~<formula> | ( <formula> ) | <formula> <operator> <formula>
<operator> ::= ^ | V
<variable> ::= one letter from a-z or A-Z, except the character V

^ is boolean AND, V is boolean OR, and ~ is boolean NOT.

An interpretation assigns true or false to every variable that occurs in a formula. Once an interpretation is fixed, the truth value of the formula follows from applying the boolean operations to the variable values in the standard way.

Two formulae are equivalent if they produce the same truth value under every possible interpretation. An interpretation here assigns a value to every variable that occurs in either of the two formulae.

Given two formulae, decide whether they are equivalent.

Input

The first line holds one formula and the second line holds the other. A variable is a single letter, and the character V is reserved for the OR operator, so it is never a variable name. Whitespace can occur anywhere inside a line.

Each line is at most 1000 characters including whitespace, and the two formulae together use at most 16 distinct variables.

Output

Print 1 if the two formulae are equivalent, and 0 otherwise.

Notes

~ applies to the single term right after it and binds more tightly than ^ and V. ^ and V have the same precedence and group from the left. For example, x ^ y V z is the same as (x ^ y) V z, and ~x ^ y is the same as (~x) ^ y.

Examples5

Example 1
Input
```
x ^ y
y ^ x
```
Expected output
```
1
```
Example 2
Input
```
A ^ (~y V z)
(A^~y) V (A ^ z)
```
Expected output
```
1
```
Example 3
Input
```
a V (b ^ ~b) V (c ^ ~c)
a
```
Expected output
```
1
```
Example 4
Input
```
~x ^ ~y
~(x V y)
```
Expected output
```
1
```
Example 5
Input
```
a ^ b ^ c ^ d
a V b V c V d
```
Expected output
```
0
```