Как правильно возвращаться в этом случае?

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.

Необходимо убедиться, что вы считаете одну и ту же скобку одной раз.

Возможный подход состоит в том, чтобы вычислить идентификационный номер из скобки, а затем поддерживать набор этих идентификационных номеров и считать только те, которые еще не были установлены.

Одной из возможностей для такого идентификатора было бы представлять круглые скобки в битовой схеме: первые 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