如何计算将布尔表达式字符串括起来以评估所需结果的方法数

Question

直接来自 CTCI，8.14：给定一个由符号 0（假）、1（真）、&（与）、| 组成的布尔表达式 (OR) 和 ^(XOR) 以及所需的布尔结果值 result 实现一个函数来计算将表达式括起来的方式的数量，以便它评估结果。

我正在尝试一种蛮力方法来计算每个可能的组合，如果匹配所需的结果，则将其添加到数组（组合）并返回该结果长度。它似乎适用于大多数表达式，但不适用于给出的第二个示例。我似乎缺少什么？

function countEval(s, goalBool, combos = []) {
    // on first call make s into array since theyre easier to work with
    if (!(s instanceof Array)) {
        // and turn 1s and 0s into their bool equivalent
        s = s.split('').map((item) => {
            if (item === '1') {
                return true;
            } else if (item === '0'){
                return false;
            } else {
                return item;
            }
        });
    }
    if (s.length === 1 && s[0] === goalBool) {
        combos.push(s[0]); // can be anything really
    } else {
        for (let i = 0; i < s.length - 2; i = i + 2) {
            // splice out the next 3 items
            const args = s.splice(i, 3);
            // pass them to see what they evaluate too
            const result = evalHelper(args[0], args[1], args[2]);
            // splice that result back in s array
            s.splice(i, 0, result);
            // pass that array to recurse
            countEval(s, goalBool, combos);
            // remove said item that was just put in
            s.splice(i, 1);
            // and reset array for next iteration
            s.splice(i, 0, ...args);
        }
    }
    return combos.length;
}

function evalHelper(a, op, b) {
    if (op === '|') {
        return a || b;
    } else if (op === '&') {
        return a && b;
    } else if (op === '^') {
        return a !== b;
    }
}

给出了两个例子，它适用于第一个，但不适用于第二个......

console.log(countEval('1^0|0|1', false)); // 2, correct
console.log(countEval('0&0&0&1^1|0', true)); // 30, should be 10!?!?!

Answer 1

错误

您的程序未考虑重叠。

例子

考虑您的程序时s = '1|1|1|1'。

在其中一次深度优先搜索迭代中，您的算法将减少s = (1|1)|1|1。然后在同一个搜索中更深的递归级别，您的算法将减少s = (1|1)|(1|1)。现在s完全减少了，所以你增加了连击的长度。

在不同的深度优先搜索迭代中，您的算法将首先减少s = 1|1|(1|1)。然后在同一个搜索中更深的递归级别，您的算法将减少s = (1|1)|(1|1)。现在s完全减少了，所以你增加了连击的长度。

请注意，对于这两种情况，s括号的方式相同，因此您的程序不会考虑重叠。

更好的解决方案

很多时候，当问题是询问可以完成的方法的数量时，这通常是动态编程可能是潜在解决方案的一个重要指标。这个问题的递归关系有点棘手。

我们只需要选择一个“原则”运算符，然后确定左侧和右侧可以评估为trueor 的方式数false。然后，基于“原则”运算符和目标布尔值，我们可以推导出表达式可以评估为目标布尔值的方法数的公式，假设我们选择的运算符是“原则”运算符。

代码

function ways(expr, res, i, j, cache, spaces) {
  if (i == j) {
    return parseInt(expr[i]) == res ? 1 : 0;
  } else if (!([i, j, res] in cache)) {
    var ans = 0;
    for (var k = i + 1; k < j; k += 2) {
      var op = expr[k];
      var leftTrue = ways(expr, 1, i, k - 1, cache);
      var leftFalse = ways(expr, 0, i, k - 1, cache);
      var rightTrue = ways(expr, 1, k + 1, j, cache);
      var rightFalse = ways(expr, 0, k + 1, j, cache);
      if (op == '|') {
        if (res) {
          ans += leftTrue * rightTrue + leftTrue * rightFalse + leftFalse * rightTrue;
        } else {
          ans += leftFalse * rightFalse;
        }
      } else if (op == '^') {
        if (res) {
          ans += leftTrue * rightFalse + leftFalse * rightTrue;
        } else {
          ans += leftTrue * rightTrue + leftFalse * rightFalse;
        }
      } else if (op == '&') {
        if (res) {
          ans += leftTrue * rightTrue;
        } else {
          ans += leftFalse * rightFalse + leftTrue * rightFalse + leftFalse * rightTrue;
        }
      }
    }
    cache[[i, j, res]] = ans;
  }
  return cache[[i, j, res]];
}

function countEval(expr, res) {
  return ways(expr, res ? 1 : 0, 0, expr.length - 1, {});
}