2

問題0, 1, &, |, ^記号と目的のブール結果値で 構成されるブール式が与えられた場合、結果として評価されるように式を括弧で囲む方法の数をカウントする関数を実装します。式の望ましい結果出力の
例
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;
    }
}

このソリューションがどのように重複した結果を生成したのかわかりませんでした！誰か助けてもらえますか？

4

1 に答える 1

2

重複は、2 つの方法で (1^0)|(0|0) に到達できるという事実から生じます。次に、0|0 の後に 1^0 を括弧で囲みます。

同じ括弧を 1 回だけカウントするようにする必要があります。

可能なアプローチは、括弧から識別番号を計算し、これらの ID 番号のセットを維持し、まだセットに含まれていないものだけをカウントすることです。

このような id の 1 つの可能性は、ビット パターンで括弧を表すことです。最初の n-1 ビットは第 1 レベルの括弧を表し、次の n-2 ビットは第 2 レベルの括弧 (第 1 レベルの括弧を含む) を表します。

たとえば

(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
于 2012-06-14T00:16:05.737 に答える