CareerCup

Use dp as follows:
DP1[i][j] = Number of ways to evaluate exp(i,j) as true
DP2[i][j] = Number of ways to evaluate exp(i,j) as false

Now use memoization to evaluate and return DP[0][n].

Following is an implementation in python:

class Solver:
	def count_ways(self , exp):
		print exp,
		self.exp = exp
		n = (len(exp)+1)/2
		self.true_lookup  = [[-1 for j in xrange(n+1)] for i in xrange(n+1)]
		self.false_lookup = [[-1 for j in xrange(n+1)] for i in xrange(n+1)]
		for i in xrange(n):
			self.true_lookup[i][i+1]  = 1 if exp[2*i] else 0
			self.false_lookup[i][i+1] = 0 if exp[2*i] else 1
		
		return self.eval_true(0,n)
		
	def eval_true(self , start , end):
		if self.true_lookup[start][end]!=-1:
			return self.true_lookup[start][end]
		count = 0
		for i in xrange(start+1 , end):
			if self.exp[2*i-1] == '&':
				count += self.eval_true(start,i)*self.eval_true(i,end)
			elif self.exp[2*i-1] == '|':
				count += self.eval_true(start,i)*self.eval_true(i,end)
				count += self.eval_true(start,i)*self.eval_false(i,end)
				count += self.eval_false(start,i)*self.eval_true(i,end)
			elif self.exp[2*i-1] == '^':
				count += self.eval_true(start,i)*self.eval_false(i,end)
				count += self.eval_false(start,i)*self.eval_true(i,end)
		
		self.true_lookup[start][end] = count
		return count
	
	def eval_false(self , start , end):
		if self.false_lookup[start][end]!=-1:
			return self.false_lookup[start][end]
		
		count = 0
		for i in xrange(start+1 , end):
			if self.exp[2*i-1] == '&':
				count += self.eval_true(start,i)*self.eval_false(i,end)
				count += self.eval_false(start,i)*self.eval_false(i,end)
				count += self.eval_false(start,i)*self.eval_true(i,end)
			elif self.exp[2*i-1] == '|':
				count += self.eval_false(start,i)*self.eval_false(i,end)
			elif self.exp[2*i-1] == '^':
				count += self.eval_true(start,i)*self.eval_true(i,end)
				count += self.eval_false(start,i)*self.eval_false(i,end)
		
		self.false_lookup[start][end] = count
		return count

s = Solver()
print s.count_ways([True , "&" , True , "|" , False])
print s.count_ways([True , "&" , False , "|" , False])
print s.count_ways([True , "^" , False , "|" , False])
print s.count_ways([True , "^" , False , "&" , False])

code optimization

# -*- coding: utf-8 -*-

__author__ = 'ouyhui'

class BooleanSatisfiabilitySolver:
    def count_ways(self, expression):
        self.expression = expression
        n = (len(expression) + 1) / 2
        self.total_count = [1 for i in xrange(n - 1)]
        for i in xrange(n - 1):
            if i == 0:
                continue
            sum = 0
            for j in xrange(i):
                sum += self.total_count[j] * self.total_count[i - j -1]
            self.total_count[i] = sum
        self.true_count = [[-1 for j in xrange(n + 1)] for i in xrange(n + 1)]
        for i in xrange(n):
            self.true_count[i][i + 1] = 1 if expression[2 * i] else 0
        return self.evaluate(0, n, True)


    def evaluate(self, start, end, result=True):
        count = 0
        if self.true_count[start][end] > -1:
            count = self.true_count[start][end]
        else:
            for i in range(start + 1, end):
                operator = self.expression[2 * i - 1]
                if operator == '&':
                    count += self.evaluate(start, i) * self.evaluate(i, end)
                elif operator == '|':
                    count += self.total_count[i-start-1] * self.total_count[end-i-1] \
                             - self.evaluate(start, i, False) * self.evaluate(i, end, False)
                else:
                    count += self.evaluate(start, i) * self.evaluate(i, end, False)
                    count += self.evaluate(start, i, False) * self.evaluate(i, end)
            self.true_count[start][end] = count
        if result:
            return count
        else:
            return self.total_count[end - start - 1] - count

Recursive solution

#include <string>
#include <vector>
#include <boost/tokenizer.hpp>

int num_true(const std::vector<std::string>& exp, int s, int e);
int num_false(const std::vector<std::string>& exp, int s, int e);

int num_ways_evaluate_true(const std::string& exp)
{
    boost::char_separator<char> sep(" ");
    boost::tokenizer<boost::char_separator<char>> tokens(exp, sep);
    std::vector<std::string> exp_v;
    for (const auto& token : tokens)
    {
        exp_v.push_back(token);
    }
    return num_true(exp_v, 0, exp_v.size() - 1);
}

int num_true(const std::vector<std::string>& exp, int s, int e)
{
    if (s == e) return (exp[s] == "true") ? 1 : 0;
    int num = 0;
    for (auto i = s + 1; i < e; i += 2)
    {
        if (exp[i] == "&")
        {
            num += num_true(exp, s, i - 1) * num_true(exp, i + 1, e);
        }
        else if (exp[i] == "|")
        {
            num += num_true(exp, s, i - 1) * num_true(exp, i + 1, e);
            num += num_false(exp, s, i - 1) * num_true(exp, i + 1, e);
            num += num_true(exp, s, i - 1) * num_false(exp, i + 1, e);
        }
        else if (exp[i] == "^")
        {
            num += num_false(exp, s, i - 1) * num_true(exp, i + 1, e);
            num += num_true(exp, s, i - 1) * num_false(exp, i + 1, e);
        }
    }
    return num;
}

int num_false(const std::vector<std::string>& exp, int s, int e)
{
    if (s == e) return (exp[s] == "false") ? 1 : 0;
    int num = 0;
    for (auto i = s + 1; i < e; i += 2)
    {
        if (exp[i] == "&")
        {
            num += num_false(exp, s, i - 1) * num_false(exp, i + 1, e);
            num += num_false(exp, s, i - 1) * num_true(exp, i + 1, e);
            num += num_true(exp, s, i - 1) * num_false(exp, i + 1, e);
        }
        else if (exp[i] == "|")
        {
            num += num_false(exp, s, i - 1) * num_false(exp, i + 1, e);
        }
        else if (exp[i] == "^")
        {
            num += num_false(exp, s, i - 1) * num_false(exp, i + 1, e);
            num += num_true(exp, s, i - 1) * num_true(exp, i + 1, e);
        }
    }
    return num;
}