CODEWITHSUNDEEP
c++algorithmbacktracking
iori
iori

Reputation: 35

How to backtrack correctly in this case?

Problem Given a boolean expression consisting of the symbols 0, 1, &, |, ^ and a desired boolean result value, 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 0
Output 2, 1^((0|0)|1), 1^(0|(0|1))

My idea is to use backtracking, and evaluate an expression of the form a operator b. For example
1^0|0|1
-------
0123456

There are 3 possible evaluations: 0, 2, 4, more specifically, I have:
(1) evaluate at 0 -> 1|0|1
(2) evaluate at 0 -> 1|1
(3) evaluate at 0 -> 1

Then I backtrack at (2), to evaluate at position 2... The idea is very simple, but it produced duplicate result. The number of ways for result = 1 should be 3 but my approach yields 4.

bool evaluate(const string& expr) {
    assert(expr.length() == 3);
    assert(expr[0] == '0' || expr[0] == '1');
    assert(expr[1] == '^' || expr[1] == '|' || expr[1] == '&');
    assert(expr[2] == '0' || expr[2] == '1');

    bool result;
    bool a = (expr[0] == '1' ? 1 : 0);
    bool b = (expr[2] == '1' ? 1 : 0);

    switch (expr[1]) {
        case '^' :
            result = a ^ b;
            break;

        case '|' :
            result = a | b;
            break;

        case '&' :
            result = a & b;
            break;
    }

    return result;
}

void transform_at(string& s, int start) {
    bool result = evaluate(s.substr(start, 3));
    string left = s.substr(0, start);
    string right = s.substr(start + 3);
    result ? left.append(1, '1') : left.append(1, '0');
    s = left + right;
}

int count_parenthese_grouping(string expr, const bool result) {
    cout << "[recurse on]: " << expr << endl;
    if (expr.length() == 3 && evaluate(expr) == result) {
        return 1;
    }
    else if (expr.length() == 3 && evaluate(expr) != result) {
        return 0;
    }
    else {
        int operators = expr.length() - 2;
        int total = 0;

        for (int i = 0; i < operators; i += 2) {
            string temp = expr;
            transform_at(expr, i);
            total += count_parenthese_grouping(expr, result);
            expr = temp;
        }

        return total;
    }
}

I couldn't see how this solution generated duplicate result! Could anyone help me out?

Upvotes: 2

Views: 492

Answers (1)

Attila
Attila

Reputation: 28762

The duplication comes from the fact that you can arrive at (1^0)|(0|0) in two ways: first, parenthesize 1^0 then 0|0; second, parenthesize 0|0 then 1^0.

You need to ensure that you only count the same parenthesizing once.

A possible approach is to calculate an identifing number from the parenthesizing, then maintain a set of these id numbers and only count the ones that were not in the set yet.

One possibility for such id would be to represent the parentheses in a bit pattern: the first n-1 bits representing first-level parhentheses, the next n-2 bits representing second-level parentheses (parentheses containing first-level ones), etc.

so for example

(1^0)|0|0   would become 10000
1^(0|0)|0   would become 01000
1^0|(0|0)   would become 00100
(1^0)|(0|0) would become 10100
(1^(0|0))|0 would become 01010
1^((0|0)|0) would become 01001

Upvotes: 2

Related Questions