Tautology

Problem code: TAUT

All submissions for this problem are available.

Write a program that checks if the given logical expression is a tautology. The logical expression is a tautology if it is always true, regardless of logical value of its variables.

Input

On the first line there is the number of expressions to check (at most 35). The expression is in a prefix notation, that means that operator precedes its arguments. The following logical operators will be used: 

C - and 
D - or
I - implies
E - if, and only if
N - not

The variables will be lowercase letters (a-z). There will be no more than 16 different letters in the expression. The length of the expression will not exceed 111 characters.

Output

For each expression write one word: YES if it is a tautology, NO in other case.

Example

Sample input:
7
IIpqDpNp
NCNpp
Iaz
NNNNNNNp
IIqrIIpqIpr
Ipp
Ezz


Sample output:
YES
YES
NO
NO
YES
YES
YES
Author: admin
Date Added: 1-12-2008
Time Limit: 7 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

I finally got this correct.

figgles @ 14 Oct 2009 12:41 PM

I finally got this correct. Turns out I had a bug in my NOT evaluation. This problem is fairly easy if you parse everything into a tree and then evaluate the tree.

Good stuff!

I am getting the correct

neeraj399 @ 16 Oct 2009 12:05 AM

I am getting the correct answer on my system for every possible valid input. What is going wrong here on CodeChef with my code? Is there something I am neglecting...

I highly doubt you have tried

triplem @ 16 Oct 2009 04:45 AM

I highly doubt you have tried every possible valid input, that would probably take hundreds of years ;)

You will be making a mistake in your code somewhere, whether it be in reading input, dealing with multiple test cases, dealing with large test cases, or simply some bug in your algorithm.. but there willl be something wrong. Keep checking.

lol... I

neeraj399 @ 16 Oct 2009 03:53 PM

lol... I never obviously meant that by saying "every possible valid input".

Yes I am checking, but its becoming a hassle now.

I think I should give up.

 

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

HELP

Program should read from standard input and write to standard output. After you submit a solution you can see your results by clicking on the [My Submissions] tab on the problem page. Below are the possible results:

 

  • Accepted Your program ran successfully and gave a correct answer. If there is a score for the problem, this will be displayed in parenthesis next to the checkmark.
  • Time Limit Exceeded Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach.
  • Wrong Answer Your program compiled and ran succesfully but the output did not match the expected output.
  • Runtime Error Your code compiled and ran but encountered an error. The most common reasons are using too much memory or dividing by zero. For the specific error codes see the help section.
  • Compilation Error Your code was unable to compile. When you see this icon, click on it for more information.

    • If you are still having problems, see a sample solution here.

CodeChef is a global programming communityCodeChef hosts online programming competitions