Write the function to count the number of ways of parenthesizing the expression

Problem

Given a boolean expression consisting of the symbols 0,1, &, |, and ^, and a

desired boolean result value result, implement a function to count the number

of ways of parenthesizing the expression such that it evaluates to result.

Example)

Expression: 1^0|0|1

Desired result: false (0)

Output: 2 ways. 1^( (0|0)|1) and 1^(0|(0|1)).

This is the last questions from "Cracking Coding" for Recursion & Dynamic programming.

I guess this book call "Memoization" part of Dynamic programming, a dynamic programming, which is not actually correct. 

Basic recursion approach

Upshot

Coming up with the recursion pattern for this problem is to first find the very high level  view of the problem.

Given expression, 1^0|0|1  and expected value, e, we can see the following basic cases:
# of ways to put parentheses = count( 1^(0|0|1), e) + count( (1^0)|(0|1), e ) + count( (1^0|0)|1), e )

Recursively, count( 1^(0|0|1), e)  = count(1, e) $\times$ count(0|0|1, e) etc.
Each time we break up the expression into two parts and call count on each part recursively.

Cases for each operand

Now, let's consider the possible cases for operands
For OR operator, "|", we consider both e = true and e = false.

Case 1)  e = true, we consider three possible cases:

TRUE | TRUE, TRUE | FALSE, FALSE | TRUE


count( expr1 | expr2, true) = count(expr1, true) $\times$ count(expr2, true) + count(expr1, true) $\times$ count(expr2, false)  + count(expr1, false) $\times$ count(expr2, true) 

Case 2)  e = false, we consider one possible case:

FALSE | FALSE

count( expr1 | expr2, false) = count(expr1, false) $\times$ count(expr2, false) 

For AND operator, "&", we also consider both e = true and e = false.

Case 1)  e = true, we consider one possible case:

TRUE & TRUE

count( expr1 & expr2, true) = count(expr1, true) $\times$ count(expr2, true) + count(expr1, true) $\times$ count(expr2, false)  + count(expr1, false) $\times$ count(expr2, true) 

Case 2)  e = false, we consider three possible cases:

FALSE & FALSE, TRUE & FALSE, FALSE & TRUE


count( expr1 & expr2, false) = count(expr1, true) $\times$ count(expr2, false) + count(expr1, false) $\times$ count(expr2, true)  + count(expr1, false) $\times$ count(expr2, false) 

Lastly, for XOR operator, "^", we also consider both e = true and e = false.

Case 1)  e = true, we consider two possible cases:

TRUE ^ FALSE, FALSE ^ TRUE

count( expr1 & expr2, true) = count(expr1, true) $\times$ count(expr2, false) + count(expr1, false) $\times$ count(expr2, true)  

Case 2)  e = false, we consider two possible cases:

TRUE ^ TRUE, FALSE ^ FALSE


count( expr1 & expr2, false) = count(expr1, true) $\times$ count(expr2, true) + count(expr1, false) $\times$ count(expr2, false)  

Now, we are ready to write the first algorithm, which will run in $O(N \times N!)$
Here is the complete code using recursion. 

	include<iostream>
	#include<map>
	#include<string>
	using namespace std;
	bool is_op(char c)
	{
	return c=='|'|| c=='&' || c =='^';
	}
	int evaluate(string expr, bool expected, int s, int e)
	{
	if (s == e)
	{
	if (expr[s] == '1' && expected)
	return 1;
	if (expr[s] == '0' && !expected)
	return 1;
	return 0;
	}
	int c = 0;
	for (int i = s+1; i<= e; i++)
	{
	char op = expr[i];
	if (!is_op(op))
	continue;
	if(expected) //expected = true
	{
	if (op == '|')
	{
	// 1|1 1|0 0|1
	c+= evaluate(expr, true, s, i-1)*evaluate(expr, true, i+1, e);
	c+= evaluate(expr, true, s, i-1)*evaluate(expr, false, i+1, e);
	c+= evaluate(expr, false, s, i-1)*evaluate(expr, true, i+1, e);
	} else if (op == '^')
	{
	// 0^1 1^0
	c+= evaluate(expr, false, s, i-1)*evaluate(expr, true, i+1, e);
	c+= evaluate(expr, true, s, i-1)*evaluate(expr, false, i+1, e);
	} else if (op =='&')
	{
	// 1&1
	c+= evaluate(expr, true, s, i-1)*evaluate(expr, true, i+1, e);
	}
	} else {
	//expected = false
	if (op == '|')
	{
	// 0|0
	c+= evaluate(expr, false, s, i-1)*evaluate(expr, false, i+1, e);
	} else if (op == '^')
	{
	// 1^1 0^0
	c+= evaluate(expr, false, s, i-1)*evaluate(expr, false, i+1, e);
	c+= evaluate(expr, true, s, i-1)*evaluate(expr, true, i+1, e);
	} else if (op =='&')
	{
	// 1&0 0&1 0&0
	c+= evaluate(expr, true, s, i-1)*evaluate(expr, false, i+1, e);
	c+= evaluate(expr, false, s, i-1)*evaluate(expr, true, i+1, e);
	c+= evaluate(expr, false, s, i-1)*evaluate(expr, false, i+1, e);
	}
	}
	}
	return c;
	}
	int main() {
	string expr = "1^0|0|1";
	bool expected = false;
	int count = evaluate(expr, expected, 0, expr.length()-1);
	cout<<"ways to put parentheses to make "<< expected <<" for "<<expr<<" : "<<count<<endl;
	return 1;
	}

view raw count_ways_to_put_parentheses.cpp hosted with ❤ by GitHub

More efficient recursion with Memoization

Previous algorithm process the same problems repeated during the recursion. 

We can avoid this duplications by caching the intermediate results in the lookup table. 

The following code uses the Memoization. Only difference is the routine checking the std::map before perform the recursion and adding the resultant count to the std::map before returning the count at the end of the function.

	#include<iostream>
	#include<map>
	#include<string>
	using namespace std;
	bool is_op(char c)
	{
	return c=='|'|| c=='&' || c =='^';
	}
	int evaluate(string expr, bool expected, int s, int e, map<string, int>& cache)
	{
	if (s == e)
	{
	if (expr[s] == '1' && expected)
	return 1;
	if (expr[s] == '0' && !expected)
	return 1;
	return 0;
	}
	string key = to_string(s)+"_"+to_string(e)+"_"+to_string(expected);
	map<string, int>::iterator found;
	if ( (found =cache.find(key)) != cache.end())
	return found->second;
	int c = 0;
	for (int i = s+1; i<= e; i++)
	{
	char op = expr[i];
	if (!is_op(op))
	continue;
	if(expected) //expected = true
	{
	if (op == '|')
	{
	// 1|1 1|0 0|1
	c+= evaluate(expr, true, s, i-1, cache)*evaluate(expr, true, i+1, e, cache);
	c+= evaluate(expr, true, s, i-1, cache)*evaluate(expr, false, i+1, e, cache);
	c+= evaluate(expr, false, s, i-1, cache)*evaluate(expr, true, i+1, e, cache);
	} else if (op == '^')
	{
	// 0^1 1^0
	c+= evaluate(expr, false, s, i-1, cache)*evaluate(expr, true, i+1, e, cache);
	c+= evaluate(expr, true, s, i-1, cache)*evaluate(expr, false, i+1, e, cache);
	} else if (op =='&')
	{
	// 1&1
	c+= evaluate(expr, true, s, i-1, cache)*evaluate(expr, true, i+1, e, cache);
	}
	} else {
	//expected = false
	if (op == '|')
	{
	// 0|0
	c+= evaluate(expr, false, s, i-1, cache)*evaluate(expr, false, i+1, e, cache);
	} else if (op == '^')
	{
	// 1^1 0^0
	c+= evaluate(expr, false, s, i-1, cache)*evaluate(expr, false, i+1, e, cache);
	c+= evaluate(expr, true, s, i-1, cache)*evaluate(expr, true, i+1, e, cache);
	} else if (op =='&')
	{
	// 1&0 0&1 0&0
	c+= evaluate(expr, true, s, i-1, cache)*evaluate(expr, false, i+1, e, cache);
	c+= evaluate(expr, false, s, i-1, cache)*evaluate(expr, true, i+1, e, cache);
	c+= evaluate(expr, false, s, i-1, cache)*evaluate(expr, false, i+1, e, cache);
	}
	}
	}
	cache[key] = c;
	return c;
	}
	int main() {
	map<string, int> cache;
	string expr = "1^0|0|1";
	bool expected = false;
	int count = evaluate(expr, expected, 0, expr.length()-1, cache);
	cout<<"ways to put parentheses to make "<< expected <<" for "<<expr<<" : "<<count<<endl;
	return 1;
	}

view raw count_ways_to_put_parentheses_memoization.cpp hosted with ❤ by GitHub