Under construction

Still being built. Things may change

Logical Expression Equivalence

Time limit1sMemory limit128 MB

Summary
Parse two concatenated boolean expressions with C-style operator precedence and decide if they are logically equivalent for all variable assignments.
Level

Medium6 of 10

Topics
String, Brute force, Bit manipulation
Solved
No attempts yet

Problem

Two logical expressions are given. For each test case, determine whether the two expressions produce the same result for every assignment of their variables.

Input

The first line contains the number of test cases T.

Each test case is given on one line. The two logical expressions that must be compared are written consecutively with no delimiter, so your program must separate the two expressions from that line.

An expression may contain variables a through z, binary operators |, &, ^, the unary operator ~, and parentheses. All other characters are ignored.

Operator precedence follows the C-language order ~, &, ^, |. Binary operators associate from left to right within the same precedence level.

Each expression contains at most 10 distinct variables and at most 100 operators.

Output

For each test case, let N be the test case number starting from 1.

If the two expressions are logically equivalent, print the following format.

Data set N: Equivalent

If they are logically different, print the following format.

Data set N: Different

Examples1

  1. Example 1

    Input
    3
a ^b&(b|a)~b^ a
a^b&(b|a)(a^(b&(b|a)))
~~~~z~~z
    Expected output
    Data set 1: Different
Data set 2: Equivalent
Data set 3: Equivalent