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

Question

问题 给定一个由符号0, 1, &, |, ^和期望的布尔结果值组成的布尔表达式，实现一个函数来计算将表达式括起来以便计算结果的数量。
例
表达1^0|0|1
所需的结果0
输出2, 1^((0|0)|1), 1^(0|(0|1))

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

有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号码并只计算那些不在该号码集中的号码。

这样的id的一种可能性是以位模式表示圆括号：第一个n-1位表示第一级parhentheses，第二个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