Boolean evaluation

Given a boolean expression consisting of the symbols 0 (false), 1 (true), & (AND), | (OR), and ^ (XOR), and a desired boolean result value result, implement a function to count the number of ways of parenthesising the expression such that it evaluates to result.

EXAMPLES:

countEval("1^0|0|1", false) -> 2;

countEval("0&0&0&1^1|0", true) -> 10

This is my implementation; any feedback/suggestions would be very much appreciated.

#include <iostream>
#include <string>
#include <algorithm>

inline bool charToBool (const char& c1) {
if(c1 == '1') return true;
else return false;
}

// the par function recursively calls itself such that it can
// "create" every possible parenthesisation around every operation.
// Next, it counts the number of boolean values that were calculated

// returns count of true possibile booleans,
// respectively count of false possibile booleans,
// in all iterations of paranthesisation of
// str expression from [first, last)

std::pair<int, int> par(const std::string& str, const int first, const int last) {

// substrLen is the length of the current parenthesis

int substrLen = last-first;

// base condition

if(substrLen == 1){
if(charToBool(str[first])) return {1, 0};
else return {0, 1};
}

std::pair<int, int> total = {0, 0};

// function par iterates through all possible parenthesis lengths
// from index first, then recursively calls itself
// for the rest of said expression str

for(int len = 1; len <= substrLen-2; len+=2) {

// pairs left and right represent the left parenthesis,
// respectively right parenthesis of expressions,
// compared to the token of operation

std::pair<int, int> left = par(str, first, first+len);
std::pair<int, int> right = par(str, first+len+1, last);

switch(str[first+len]) {

case '|':

total.first += left.first*right.second + left.second*right.first + left.first*right.first;
total.second += left.second*right.second;
break;

case '&':

total.first += std::min(left.first, right.first);
total.second += left.first*right.second + left.second*right.first + left.second*right.second;
break;

case '^':

total.first += left.first*right.second + left.second*right.first;
total.second +=  left.first*right.first + left.second*right.second;
break;
}
}
return total;
}

// the countEval function returns count
// of target bool, after parenthesizing
// through the par function

int countEval(const std::string& str, const bool& target) {

// checks if string is valid
// (it must be of uneven size)

if(str.size() % 2 == 0) return 0;

std::pair<int, int> res = par(str, 0, str.size());

// first number of pair res is the true number count
// second number of pair res is the false number count

if(target) return res.first;
else return res.second;
}

int main() {

const std::string str = "0&0&0&1^1|0";
int res = countEval(str, true);

std::cout << "res = " << res << '\n';

return 0;
}

// TIME COMPLEXITY: O(n^3);
// SPACE COMPLEXITY : o(n^2);
// where n is the length of std::string str


1 Answer

Time complexity cannot be $$\n^3\$$. There are just too many ways to parenthesize the string, and the code inspects them all.

I run an experiment counting a number of calls to par for the strings of different length. and the results (length of string vs number of calls) are

7 27
9 81
11 243
13 729
15 2187
17 6561


which curiously enough fits (exactly) the $$\N = 3^{(n-1)/2}\$$ relation. (Note that $$\(n-1)/2\$$ is a number of operators in a string). It will be an interesting exercise in combinatorics to prove that.

    total.first += std::min(left.first, right.first);


looks like a bug to me. It should be

    total.first += left.first * right.first;


All indices should be size_t rather than int.

An implementation of charToBool is anti-idiomatic. It is a long way to say

    return c1 == '1';

• And space complexity is only $O(n)$. Jun 21 at 13:06