UVa 10847

From Algorithmist
Jump to navigation Jump to search

10847 - Basic Tautologies[edit]

Summary[edit]

Write a program to check whether given expression is a valid Reverse Polish Notation formula under given constraints, and if it is a tautology.

Explanation[edit]

The truth tables given in the problem statement use {0, 1} for the truth values, but it is more natural here to use -1 for false, and +1 for truth. Then the operator "=" becomes just the usual multiplication, and "-" is multiplication by -1.

The expression is a tautology, if it evaluates to +1 regardless of the variables' values, and this can only happen when these two conditions are satisfied:

  1. the minus sign occurs an even number of times,
  2. each of the variables occurs an even number of times.

Input[edit]

3
aa=
aa=-
ab

Output[edit]

tautology
formula
incorrect