PROBLEM STATEMENT
We are familiar with the concept of a truth-table for a traditional boolean
logic expression. Consider now extending that concept into a trilean logic
expression. Trilean logic, like boolean logic, has TRUE and FALSE values, but
also has a third, called MAYBE. The logic gates are as follows: AND, OR, XOR,
NOT, INC
AND has two inputs and returns:
TRUE if all inputs evaluate to TRUE
FALSE if all inputs evaluate to FALSE
MAYBE otherwise
OR has two inputs and returns:
TRUE if at least one input evaluates to TRUE
FALSE if all inputs evaluates to FALSE
MAYBE otherwise
XOR has two inputs and returns (in order of precedence):
TRUE if exactly one input evaluates to TRUE
MAYBE if exactly one input evaluates to MAYBE
FALSE otherwise
NOT has one input and returns:
TRUE if input evaluates to FALSE
MAYBE if input evaluates to MAYBE
FALSE if input evaluates to TRUE
INC has one input and returns:
TRUE if input evaluates to MAYBE
MAYBE if input evaluates to FALSE
FALSE if input evaluates to TRUE
DEFINITION
Class name: Trilean
Method name: equivalent
Parameters: String[]
Returns: String[]
The method signature is as follows (make sure it is declared public):
String[] equivalent (String[] expressions);
Each String in expressions will contain a pre-fix notation trilean expression,
such as: "AND NOT X1 OR X2 X3", where the words "AND", "OR", "XOR", "NOT", and
"INC" designate their respective logic gates, and "X<int>" designates an input
to a logic gate.
There may be multiple spaces between operators and operands in the expressions.
You should deal with this.
Two trilean expressions are equivalent if they have identical truth-tables.
That is, for every possible combination of inputs (using all six possible
inputs), both expressions produce identical output. Note that in order for two
truth-tables do be identical, they are not required to have the same number of
inputs. For instance, "AND X1 NOT X1" evaluates to MAYBE for any combination of
inputs. Also, "AND AND X1 NOT X1 AND X2 NOT X2" always evaluates to MAYBE.
Thus, these two expressions ARE equivalent. However, "INC X1" and "INC X2" are
not equivalent, since for the input X1 = TRUE, X2 = MAYBE, "INC X1" evalutate
to FALSE, and "INC X2" evaluates to TRUE.
Given a String[] of prefix notation expressions, determine which of them are
equivalent, grouping the equivalencies represented as "<int> <int> ... <int>"
in Strings. Angle brackets, ellipses, and parentheses included for clarity only.
For instance, if we are given 5 expressions (0, 1, 2, 3, and 4), expressions 0,
2 and 3 are equivalent, and expressions 1 and 4 are equivalent, the correct
return value is {"0 2 3", "1 4"}.
Each String in the return String[] must have the integers in ascending order,
and the Strings must be sorted in ascending order by the first integer in each
String.
Thus, {"0 3 2", "1"} is not correct because the integers in the first String
are not in ascending order, and {"1 2 3", "0"} is not correct because the first
integers of the Strings are not in ascending order.
NOTES
- Prefix notation is the idea of giving the operator first, followed by its
operands, which in turn may be expressions themselves. For instance, "AND AND
AND X1 X2 AND X3 X4 AND X5 X6" in prefix notation is equivalent to "(((X1 AND
X2) AND (X3 AND X4)) AND (X5 AND X6))" in infix notation.
- The only valid X<int> inputs are X1, X2, X3, X4, X5, and X6.
TopCoder will enforce the following restrictions:
* expressions will contain between 1 and 50 elements, inclusive
* Each String in expressions will contain between 1 and 50 characters, inclusive
* Each String in expressions will be contain a correctly formatted prefix
notation logic expression. That is, every input requiring two inputs will have
exactly two inputs, and every input requiring one input will have exactly one
input. Also, there will be no extra data in each String beyond what is required
to define the logic expression.
* Each expression will have no more than the 6 distinct inputs X1, X2, X3, X4,
X5, and X6.
Prefix notation is defined
Examples:
expressions = {"OR X1 X2","AND NOT X1 X2"}
"OR X1 X2":
X1 X2 Result
FALSE FALSE FALSE
FALSE MAYBE MAYBE
FALSE TRUE TRUE
MAYBE FALSE MAYBE
MAYBE MAYBE MAYBE
MAYBE TRUE TRUE
TRUE FALSE TRUE
TRUE MAYBE TRUE
TRUE TRUE TRUE
"AND NOT X1 X2":
X1 X2 Result
FALSE FALSE MAYBE
FALSE MAYBE MAYBE
FALSE TRUE TRUE
MAYBE FALSE MAYBE
MAYBE MAYBE MAYBE
MAYBE TRUE MAYBE
TRUE FALSE FALSE
TRUE MAYBE MAYBE
TRUE TRUE MAYBE
These are not the same. Return value is {"0", "1"}.
Examples:
expressions = {"NOT X1", "NOT X2"}
In order to justifiably compare these two truth tables, we must look at all
possible inputs of X1 and X2
"NOT X1" "NOT X2"
X1 X2 Result X1 X2 Result
FALSE FALSE TRUE FALSE FALSE TRUE
FALSE MAYBE TRUE FALSE MAYBE MAYBE
FALSE TRUE TRUE FALSE TRUE FALSE
MAYBE FALSE MAYBE MAYBE FALSE TRUE
MAYBE MAYBE MAYBE MAYBE MAYBE MAYBE
MAYBE TRUE MAYBE MAYBE TRUE FALSE
TRUE FALSE FALSE TRUE FALSE TRUE
TRUE MAYBE FALSE TRUE MAYBE MAYBE
TRUE TRUE FALSE TRUE TRUE FALSE
These clearly do not have the same result for every input. Return value is
{"0","1"}.
expressions = {"AND X1 X2", "OR X1 NOT X2", "AND X2 X1"}
Expressions 0 and 2 have identical truth-tables and hence are equivalent, but
expression 1 is different.
Return value is {"0 2", "1"}.
expressions = {"AND X1 NOT X1", "AND X2 NOT X2", "AND X3 NOT X3", "AND X1 X2",
"NOT X3"}
Expressions 0, 1, and 2 are equivalent, 3 and 4 are distinct.
Return value is {"0 1 2", "3", "4"}.
expressions = {"XOR INC X1 NOT INC X2","NOT NOT INC INC NOT INC X2","INC INC
INC INC INC NOT INC X2"}
Return value is {"0", "1 2"}.