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     qCpqDpqEpq
    F     FTTT
    F     TTTF
    T     FFTF
    T     TTFT
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
 KNpp is valid: contradiction
 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.