Cracking Coding Interview - 8.14 Boolean Evaluation

2019-08-27 3 分钟阅读 ARTS-A

Boolean Evaluation: Given a boolean expression consisting of the symbols 0 (false), 1 (true), & (AND), | (OR), and ^ (XOR), and a desired boolean result value result, implement a function to count the number of ways of parenthesizing the expression such that it evaluates to result.

EXAMPLE

1
2

countEval("1^0|0|1", false) -> 2
countEval("0&0&0&1^1|0", true) -> 10

Hints: #148, #168, #197, #305, #327

解法1

对于第一个例子的两个做法是：

1
2

1^(0|(0|1))
1^((0|0)|1)

怎么分析这个问题？

先看两个简单的例子：

1
2
3
4
5
6
7
8

表达式: a | b
加括号: (a) | (b)

表达式: a & b | c
加括号: (a) & (b | c)
       (a & b) | (c)
其中: b | c 可以拆分成 (b) | (c)
     a & b 可以是 (a) & (b)

所以，可以发现加括号实际上可以是一个递归的过程，将表达式根据操作符分割成左右两边，对左右两边再做分割。直到表达式里没有操作符为止，即达到Base Condition。

然后再看表达式的左右两边值得是如何的才能得到期望值：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Required: a | b == true
Solution: a == true && b == true
       OR a == true && b == false
       OR a == false && b == true

Required: a | b == false
Solution: a == false && b == false

Required: a & b == true
Solution: a == true && b == true

Required: a & b == false
Solution: a == true && b == false
       OR a == false && b == true
       OR a == false && b == false

Required: a ^ b == true
Solution: a == true && b == false
       OR a == false && b == true

Required: a ^ b == true
Solution: a == true && b == true
       OR a == false && b == false

所以：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

countEval(a | b, true) = countEval(a, true) * countEval(b, false)
                       + countEval(a, false) * countEval(b, true)
                       + countEval(a, true) * countEval(b, true)

countEval(a | b, false) = countEval(a, false) * countEval(b, false)

countEval(a & b, true) = countEval(a, true) * countEval(b, true)

countEval(a & b, false) = countEval(a, true) * countEval(b, false)
                       + countEval(a, false) * countEval(b, true)
                       + countEval(a, false) * countEval(b, false)
                       
countEval(a ^ b, true) = countEval(a, true) * countEval(b, false)
                       + countEval(a, false) * countEval(b, true)

countEval(a ^ b, false) = countEval(a, true) * countEval(b, true)
                        + countEval(a, false) * countEval(b, false)

所以代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

public int countEval(String expression, boolean expected) {
  if (expression == "") {
    return 0;
  }
  if (expression == "1") {
    return expected ? 1 : 0;
  }
  if (expression == "0") {
    return expected ? 0 : 1;
  }
  int ways = 0;
  for (int i = 1; i < expression.length; i += 2) {
    char op = expression.charAt(i);
    String left = expression.subString(0, i);
    String right = expression.subString(i + 1);
    
    int leftTrue = countEval(left, true);
    int leftFalse = countEval(left, false);
    int rightTrue = countEval(right, true);
    int rightFalse = countEval(right, false);

    if (op == '|') {
      if (expected) {
        ways += leftTrue * rightTrue
              + leftTrue * rightFalse
              + leftFalse * rightTrue;
      } else {
        ways += leftFalse * rightFalse;
      }
    } else if (op == '&') {
      if (expected) {
        ways += leftTrue * rightTrue;
      } else {
        ways += leftTrue * rightFalse
              + leftFalse * rightTrue
              + leftFalse * rightFalse;
      }
    } else if (op == '^') {
      if (expected) {
        ways += leftTrue * rightFalse
              + leftFalse * rightTrue;
      } else {
        ways += leftTrue * rightTrue
              + leftFalse * rightFalse;
      }
    }
  }
  return ways;
}

上面的代码有点长，可以这样计算：

1
2
3
4
5
6
7

左右表达式的总数量 = 左边表达式的总数 * 表达式的总数
                = (左边true + 左边false) * (右边true + 右边false)
因此:
totalCount(a | b) = (countEval(a, true) + countEval(a, false))
                  * (countEval(b, true) + countEval(b, false))

而countEval(a | b, false) = totalCount(a | b) - countEval(a | b, true);

因此可以简化：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

public int countEval(String expression, boolean expected) {
  if (expression == "") {
    return 0;
  }
  if (expression == "1") {
    return expected ? 1 : 0;
  }
  if (expression == "0") {
    return expected ? 0 : 1;
  }
  int ways = 0;
  for (int i = 1; i < expression.length; i += 2) {
    char op = expression.charAt(i);
    String left = expression.subString(0, i);
    String right = expression.subString(i + 1);
    
    int leftTrue = countEval(left, true);
    int leftFalse = countEval(left, false);
    int rightTrue = countEval(right, true);
    int rightFalse = countEval(right, false);
    int total = (leftTrue + leftFalse) * (rightTrue * rightFalse);
    int totalTrue = 0;
    if (op == '|') {
      totalTrue = leftTrue * rightTrue
              + leftTrue * rightFalse
              + leftFalse * rightTrue;
    } else if (op == '&') {
      totalTrue = leftTrue * rightTrue;
    } else if (op == '^') {
      totalTrue = leftTrue * rightFalse
                + leftFalse * rightTrue;
    }
    int subWays = result ? totalTrue : total - totalTrue;
    ways += subWays;
  }
  return ways;
}

解法2

考虑这个表达式a|b&a|b，当分割成(a|b)*(a|b)时，左边的数量右边的数量是一致的，因此可以缓存起来避免重复计算。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

public int countEval(String expression, boolean expected, Map<String, Map<Boolean, Integer>> cache) {
  if (expression == "") {
    return 0;
  }
  if (expression == "1") {
    return expected ? 1 : 0;
  }
  if (expression == "0") {
    return expected ? 0 : 1;
  }
  Map<Boolean, Integer> boolCache = cache.get(expression);
  if (boolCache != null) {
    Integer cacheCount = cache.get(expression).get(result);
    if (cacheCount != null) {
      return cacheCount;
    }
  }
    
  int ways = 0;
  for (int i = 1; i < expression.length; i += 2) {
    char op = expression.charAt(i);
    String left = expression.subString(0, i);
    String right = expression.subString(i + 1);
    
    int leftTrue = countEval(left, true);
    int leftFalse = countEval(left, false);
    int rightTrue = countEval(right, true);
    int rightFalse = countEval(right, false);
    int total = (leftTrue + leftFalse) * (rightTrue * rightFalse);
    int totalTrue = 0;
    if (op == '|') {
      totalTrue = leftTrue * rightTrue
              + leftTrue * rightFalse
              + leftFalse * rightTrue;
    } else if (op == '&') {
      totalTrue = leftTrue * rightTrue;
    } else if (op == '^') {
      totalTrue = leftTrue * rightFalse
                + leftFalse * rightTrue;
    }
    int subWays = result ? totalTrue : total - totalTrue;
    ways += subWays;
  }
  
  if (boolCache == null) {
    boolCache = new HashMap<>();
    cache.put(expression, boolCache);
  }
  boolCache.put(result, ways);
  return ways;
}
Cracking Coding Interview - 8.13 Stack of Boxes
Cracking Coding Interview - 10.1 Sorted Merge

版权

CC BY-NC-ND 4.0

相关文章

评论