Marvin, the robot with a brain the size of a planet, followed some . . . markedly less successful robots as the product line developed. One such was Monroe, the robot — except, to help him recognize his name, he was referred to as Moe. He is sufficiently mentally challenged that he needs external assistance to handle symbolic logic.
Polish notation is the prefix symbolic logic notation developed by Jan Lukasiewicz (1929). [Hence postfix expressions are referred to as being in Reverse Polish Notation — RPN.] The notation developed by Łukasiewicz (referred to as PN below) uses uppercase letters for the logic operators and lowercase letters for logic variables (which can only be true or false). Since prefix notation is selfgrouping, there is no need for precedence, associativity, or parentheses, unlike infix notation. In the following table the PN operator is shown, followed by its operation. Operators not having exactly equivalent C/C++/Java operators are shown in the truth table (using 1 for true and 0 for false). [The operator J is not found in Łukasiewicz’ original work but is included from A.N.Prior’s treatment.]


For every combination of PN operators and variables, an expression is a “wellformed formula” (WFF) if and only if it is a variable or it is a PN operator followed by the requisite number of operands (WFF instances). A combination of symbols will fail to be a “wellformed formula” if it is composed of a WFF followed by extraneous text, it uses an unrecognized character [uppercase character not in the above table or a nonalphabetic character], or it has insufficient operands for its operators. For invalid expressions, report the first error discovered in a lefttoright scan of the expression. For instance, immediately report an error on an invalid character. If a valid WFF is followed by extraneous text, report that as the error, even if the extraneous text has an invalid character.
In addition, every WFF can be categorized as a tautology (true for all possible variable values), a contradiction (false for all possible variable values), or a contingent expression (true for some variable values, false for other variable values).
The simplest contingent expression is simply “p”, true when p is true, false when p is false. One very simple contradiction is “KpNp”, both p and notp are true. Similarly, one very simple tautology is “ApNp”, either p is true or notp is true. For a more complex tautology, one expression of De Morgan’s Law is “EDpqANpNq”.
Sample Input  Sample Output 

q Cp Cpq A01 Cpqr ANpp KNpp Qad CKNppq JDpqANpNq CDpwANpNq EDpqANpNq KCDpqANpNqCANpNqDpq [this is an empty line] 
q is valid: contingent Cp is invalid: insufficient operands Cpq is valid: contingent A01 is invalid: invalid character Cpqr is invalid: extraneous text ANpp is valid: tautology KNpp is valid: contradiction Qad is invalid: invalid character CKNppq is valid: tautology JDpqANpNq is valid: contradiction CDpwANpNq is valid: contingent EDpqANpNq is valid: tautology KCDpqANpNqCANpNqDpq is valid: tautology 