如何在這種情況下正確回溯？

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