Career cup 9.11

BooleanExpression.java

package Chapter9;

import java.util.ArrayList;
import java.util.HashMap;

public class BooleanExpression {
    private enum Opertor {
	AND, OR, XOR
    }

    private ArrayList<Boolean> operands;
    private ArrayList<Opertor> operators;

    public BooleanExpression(String s) {
	operands = new ArrayList<>();
	operators = new ArrayList<>();
	try {
	    for (int i = 0; i < s.length(); i += 2) {
		operands.add(s.charAt(i) == '1');
		if(i + 1 < s.length())
		    operators.add(s.charAt(i+1) == '|' ? Opertor.OR : (s.charAt(i+1) == '&' ? Opertor.AND : Opertor.XOR));
	    }
	    if (operands.size() != operators.size() + 1)
		throw new Exception("not valid representation");
	} catch (Exception e) {
	    e.printStackTrace();
	}
    }

    public boolean evaluate(boolean fir, boolean sec, Opertor op) {
	if (op == Opertor.OR) return fir || sec;
	if (op == Opertor.AND) return fir && sec;
	if (op == Opertor.XOR) return fir != sec;
	return false;
    }

    public int findCount(boolean b) {
	return findCount(b, 0, operands.size() - 1, new HashMap<String, Integer>());
    }

    private int findCount(boolean expected, int start, int end,
	    HashMap<String, Integer> countMap) {
	// base case
	boolean fir = operands.get(start);
	boolean sec = operands.get(end);
	int count = 0;
	String key = start + "," + end;

	if (start == end) {
	    count = operands.get(start) == expected ? 1 : 0;
	    countMap.put(key, count);
	    return count;
	} else if (start + 1 == end) {
	    count = evaluate(fir, sec, operators.get(start)) == expected ? 1: 0;
	    countMap.put(key, count);
	    return count;
	}

	if (countMap.containsKey(key)) {
	    return countMap.get(key);
	}

	// if expected is true
	// go through possible operators
	count = 0;
	if (expected) {
	    for (int i = start; i < end; i++) {
		Opertor op = operators.get(i);
		switch (op) {
		case AND:
		    count += findCount(true, start, i, countMap) * findCount(true, i + 1, end, countMap);
		    break;
		case OR:
		    count += findCount(true, start, i, countMap) * findCount(false, i + 1, end, countMap);
		    count += findCount(false, start, i, countMap) * findCount(true, i + 1, end, countMap);
		    count += findCount(true, start, i, countMap) * findCount(true, i + 1, end, countMap);
		    break;
		case XOR:
		    count += findCount(true, start, i, countMap) * findCount(false, i + 1, end, countMap);
		    count += findCount(false, start, i, countMap) * findCount(true, i + 1, end, countMap);
		    break;
		}
	    }
	} else {
	    // if expected is false
	    for (int i = start; i < end; i++) {
		Opertor op = operators.get(i);
		switch (op) {
		case AND:
		    count += findCount(false, start, i, countMap) * findCount(true, i + 1, end, countMap);
		    count += findCount(true, start, i, countMap) * findCount(false, i + 1, end, countMap);
		    count += findCount(false, start, i, countMap) * findCount(false, i + 1, end, countMap);
		    break;
		case OR:
		    count += findCount(false, start, i, countMap) * findCount(false, i + 1, end, countMap);
		    break;
		case XOR:
		    count += findCount(true, start, i, countMap) * findCount(true, i + 1, end, countMap);
		    count += findCount(false, start, i, countMap) * findCount(false, i + 1, end, countMap);
		    break;
		}
	    }
	}
	countMap.put(key, count);
	return count;
    }

    public static void main(String[] args) {
	BooleanExpression b = new BooleanExpression("1^0|0|1");
	System.out.println("total count = " + b.findCount(false));
    }
}