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
No trailing whitespace is to appear on an output line.
PN Operator|| ||Operation|
Apq|| ||(Inclusive) OR|
Jpq|| ||Exclusive OR|
| || Truth Tables|
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
1Hence postfix expressions are referred
to as being in Reverse Polish Notation-RPN.
File translated from
On 18 Nov 2008, 22:26.