2
\$\begingroup\$

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
\$\endgroup\$
0

1 Answer 1

2
\$\begingroup\$

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';
\$\endgroup\$
1
  • 1
    \$\begingroup\$ And space complexity is only \$O(n)\$. \$\endgroup\$
    – G. Sliepen
    Jun 21 at 13:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.