Let A := {=, −, a, b, c, . . ., z, A, B, C, . . ., Z}. We assume that ∗ represent the operation of concatenation between strings. We define the set of formulas over A recursively as follows: • If X belongs to A \ {=, −} then X is formula (variable). • IFX isaformula,soisX∗−. • If X and Y are formulas, so is: X ∗ Y ∗ =. These formulas are understood as logical formulas with connectives - for negation, = for equivalence and A{=, −} as variables. That is = and − are not variables. Also, variables a and A are considered different. Similarly b is different to B and so on. Of course our formulas are given in Reverse Polish Notation (RPN). We can evaluate a formula for a given boolean input {0, 1} and the output is either 0 or 1 as usual. A formula is a tautology if it evaluates to 1 for every input. For example ‘aa=’ is a tautology while ‘aa=−’ is not. Note that ‘aa=’ represents the formula ‘a=a’ in the standard infix notation and ‘aa=−’ represents the formula ‘−[a=a]’. Input The first line is a natural number N less than 100. Then, there are N lines, each one is a string over A. Every string is of size less than 200 characters. Output You must display N lines, each one with 3 possible answers: incorrect, tautology or formula. Answer number i gives the output of string number i. The output is ‘incorrect’ if the input string is not a formula. The output is ‘formula’ if the input string is a formula that is not a tautology. The output is ‘tautology’ if the input string is a formula that is a tautology. Note: Perhaps some students have no idea on how to evaluate a formula in RPN form. However I assume that she/he knows how to do it in the standard form, hence I need only to describe how to convert a RPN formula into a standard infix form. We define f(X) the translation of a RPN formula X by recursion as follows: We assume that X, Y, Z represent formulas.
2/2 A B A=B 001 010 100 111 The truth table for - is: A -A 01 10 Good luck! Sample Input 3 aa= aa=- ab Sample Output tautology formula incorrect