CC150 9.11

9_11.cpp

/* CC150 9.11 */
// count number of ways of parenthesize boolean expression such that it evaluates to result

#include <iostream>
#include <string>
#include <map>

using namespace std;

int countParens(string expr, bool result, map<string, int> &buff)
{
	if (expr.size() == 1) { // single element left, compare to result
		return (expr[0] == '0') ^ result;
	}
	string key = result ? expr + '1' : expr + '0';
	if (buff.find(key) != buff.end()) // expression already evaluated
		return buff[key];
	int count = 0;
	for (size_t i = 1; i < expr.size(); i += 2) {
		char op = expr[i];
		string leftExpr = expr.substr(0, i);
		string rightExpr = expr.substr(i + 1);
		if (result) { // result == true
			switch (op) {
			case '&':
				count += countParens(leftExpr, 1, buff) * countParens(rightExpr, 1, buff);
				break;
			case '|':
				count += countParens(leftExpr, 1, buff) * countParens(rightExpr, 1, buff)
					+ countParens(leftExpr, 1, buff) * countParens(rightExpr, 0, buff)
					+ countParens(leftExpr, 0, buff) * countParens(rightExpr, 1, buff);
				break;
			case '^':
				count += countParens(leftExpr, 1, buff) * countParens(rightExpr, 0, buff)
					+ countParens(leftExpr, 0, buff) * countParens(rightExpr, 1, buff);
			default:
				break;
			}
		}
		else { // result == false
			switch (op) {
			case '&':
				count += countParens(leftExpr, 0, buff) * countParens(rightExpr, 0, buff)
					+ countParens(leftExpr, 0, buff) * countParens(rightExpr, 1, buff)
					+ countParens(leftExpr, 1, buff) * countParens(rightExpr, 0, buff);

				break;
			case '|':
				count += countParens(leftExpr, 0, buff) * countParens(rightExpr, 0, buff);
				break;
			case '^':
				count += countParens(leftExpr, 1, buff) * countParens(rightExpr, 1, buff)
					+ countParens(leftExpr, 0, buff) * countParens(rightExpr, 0, buff);
			default:
				break;
			}
		}
	}
	buff[key] = count;
	return count;
}

int countParens(string expr, bool result)
{
	map<string, int> buff;
	return countParens(expr, result, buff);
}

int main()
{
	string boolExpr;
	cin >> boolExpr;
	bool result;
	cin >> result;
	cout << countParens(boolExpr, result) << " ways. " << endl;
	return 0;
}

catalan.cpp

// NEED DEBUG!!! USE OF CATALAN NUMBER?!!

// Catalan number (C.f. Ex 9.6) maximum: C15 = 9694845
unsigned long long int catalan(int n) {
	unsigned long long int numerator = 1, denominator = 1;
	for (int i = 2; i <= n; ++i) {
		numerator *= (n + i);
		denominator *= i;
	}
	return numerator / denominator;
}

int countParensSimple(string expr, bool result, map<string, int> &buff)
{
	int count = 0; // number of ways to parenthesize expr to yield true
	if (buff.find(expr) == buff.end())
		count = buff[expr];
	else {
		if (expr.size() == 1)
			count = expr[0] == '1' ? 1 : 0;
		for (size_t i = 1; i < expr.size(); i += 2) {
			char op = expr[i];
			string leftExpr = expr.substr(0, i);
			string rightExpr = expr.substr(i + 1);
			switch (op) {
			case '&':
				count += countParensSimple(leftExpr, 1, buff) * countParensSimple(rightExpr, 1, buff);
				break;
			case '|':
			{
				int cntTotal = catalan(leftExpr.size() / 2) * catalan(rightExpr.size() / 2);
				int cntFalse = countParensSimple(leftExpr, 0, buff) * countParensSimple(rightExpr, 0, buff);
				count += cntTotal - cntFalse;
				break;
			}
			case '^':
				count += countParensSimple(leftExpr, 1, buff) * countParensSimple(rightExpr, 0, buff)
					+ countParensSimple(leftExpr, 0, buff) * countParensSimple(rightExpr, 1, buff);
				break;
			default:
				break;
			}
		}
		buff[expr] = count;
	}
	if (result)
		return count;
	else
		return catalan(expr.size() / 2) - count;
}