c++ - 在这种情况下如何正确回溯？

Question

问题给定一个由符号 0、1、&、|、^ 和所需的 bool 结果值组成的 bool 表达式，实现一个函数来计算将表达式括起来的方式的数量，使其计算结果.
示例
表达式 1^0|0|1
期望的结果 0
输出 2, 1^((0|0)|1), 1^(0|(0|1))

我的想法是使用回溯，并计算 a operator b 形式的表达式。例如
1^0|0|1
--------
0123456

有 3 个可能的评估:0, 2, 4，更具体地说，我有:
(1) 在 0 -> 1|0|1
计算(2) 在 0 -> 1|1
处计算(3) 在 0 -> 1 处求值

然后我在 (2) 处回溯，在位置 2 处求值...这个想法很简单，但它产生了重复的结果。 result = 1 的方法数应该是 3 但我的方法产生 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;
    }
}

我看不出这个解决方案是如何生成重复结果的!谁能帮帮我？

Answer 1

重复是因为您可以通过两种方式到达 (1^0)|(0|0):首先，将 1^0 括起来，然后将 0|0 括起来；其次，括号 0|0 然后 1^0。

您需要确保只对相同的括号计数一次。

一种可能的方法是从括号中计算出一个标识号，然后维护一组这些标识号，并只计算不在该集合中的标识号。

这种 id 的一种可能性是用位模式表示括号:前 n-1 位表示一级括号，接下来的 n-2 位表示二级括号(包含一级括号的括号)等

例如

(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