2008/2009 SOUTHERN CALIFORNIA REGIONAL
 ACM INTERNATIONAL COLLEGIATE PROGRAMMING CONTEST

 Problem 5
 Symbolic Logic Mechanization

Polish Notation (PN) is the prefix symbolic logic notation developed by Jan Lukasiewicz (1929).1 The notation developed by Lukasiewicz uses upper-case letters for the logic operators and lower-case letters for logic variables (which can only be true or false). Since prefix notation is self-grouping, there is no need for precedence, associativity, or parentheses, unlike infix notation. The first table below shows the PN operators and the corresponding logical operation. Operators not having exactly equivalent C/C++/Java operators are shown in the adjacent truth table. [The operator J is not found in Lukasiewicz' original work but is included from A. N. Prior's treatment.]

 PN Operator Operation Cpq Conditional Np NOT Kpq AND Apq (Inclusive) OR Dpq NAND Epq Equivalence Jpq Exclusive OR

 Truth Tables p q Cpq Dpq Epq F F T T T F T T T F T F F T F T T T F T
For every combination of PN operators and variables, an expression is a "well-formed formula" (WFF) if and only if it is a variable or it is a PN operator followed by the requisite number of operands. A combination of symbols will fail to be a "well-formed formula" if it is composed of a WFF followed by extraneous text, it uses an unrecognized character [upper-case character not in the above table or a non-alphabetic character], or it has insufficient operands for its operators.
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", p and not-p cannot both be true. Similarly, one very simple tautology is "ApNp", either p is true or not-p is true. For a more complex tautology, one expression of De Morgan's Law is "EDpqANpNq".
Your program is to read character strings and determine if each string is a WFF. If the string is a WFF, categorize it; if not, describe the error.
Each input line will begin in the first column and contain a single character string to be evaluated. The character string will contain only alphanumeric characters (no blanks or punctuation) that is to be evaluated as a potential WFF. Each character string will contain between 1 and 255 characters and will use at most ten variables.
For each character string, print a line containing the string starting in the first column, followed by a single space, the text "is valid:" or "is invalid:" depending on its status as a WFF, another single space, and a status message describing the string. If the string is a valid WFF, print the expression category in lower case ("tautology", "contradiction", or "contingent"). For invalid strings, report the first error discovered in a left-to-right scan of the string. Immediately report an error on an invalid character as "invalid character". If a valid WFF is followed by extraneous text, report "extraneous text" as the error, even if the extraneous text has an invalid character. If a string is missing an operand, report "insufficient operands" as the error. No trailing whitespace is to appear on an output line.

 Sample Input

q
Cp
Cpq
A01
Cpqr
KNpp
CKNppq
CDpwANpNq

 Output for the Sample Input

q is valid: contingent
Cp is invalid: insufficient operands
Cpq is valid: contingent
A01 is invalid: invalid character
Cpqr is invalid: extraneous text
CKNppq is valid: tautology
CDpwANpNq is valid: contingent

### Footnotes:

1Hence postfix expressions are referred to as being in Reverse Polish Notation-RPN.

File translated from TEX by TTH, version 3.77.
On 18 Nov 2008, 22:26.