UVA – 11108 – Tautology   Leave a comment


Just another boring problem

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Tautology {
	public static int map(char c) {
		if (c == 'p')
			return 0;
		if (c == 'q')
			return 1;
		if (c == 'r')
			return 2;
		if (c == 's')
			return 3;
		if (c == 't')
			return 4;
		return -1;
	}

	public static boolean evaluate(int mask, char[] arr) {
		Stack<Boolean> res = new Stack<Boolean>();
		for (int i = arr.length - 1; i >= 0; i--) {
			if (map(arr[i]) != -1)
				res.push((1 << map(arr[i]) & mask) != 0);
			else {
				if (arr[i] == 'K') {
					boolean a = res.pop();
					boolean b = res.pop();
					res.push(a && b);
				}
				if (arr[i] == 'A') {
					boolean a = res.pop();
					boolean b = res.pop();
					res.push(a || b);
				}
				if (arr[i] == 'N')
					res.push(!res.pop());
				if (arr[i] == 'C') {
					boolean a = res.pop();
					boolean b = res.pop();
					res.push(!a || b);
				}
				if (arr[i] == 'E') {
					boolean a = res.pop();
					boolean b = res.pop();
					res.push(a == b);
				}
			}
		}
		return res.pop();
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		while (true) {
			char[] s = in.readLine().toCharArray();
			if (s.length == 1 && s[0] == '0')
				return;
			boolean ok = true;
			for (int i = 0; i < 1 << 5; i++) {
				ok = ok && evaluate(i, s);
			}
			if (ok)
				System.out.println("tautology");
			else
				System.out.println("not");
		}
	}

	static class InputReader {
		private BufferedReader reader;
		private StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream));
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}
	}
}
Advertisements

Posted July 5, 2012 by epicrado in Iterative

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: