Skip to content

08.14. Boolean Evaluation

Description

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:


Input: s = "1^0|0|1", result = 0



Output: 2

Explanation: Two possible parenthesizing ways are:

1^(0|(0|1))

1^((0|0)|1)

Example 2:


Input: s = "0&0&0&1^1|0", result = 1



Output: 10

Note:

  • There are no more than 19 operators in s.

Solutions

Solution 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def countEval(self, s: str, result: int) -> int:
        @cache
        def dfs(s):
            res = [0] * 2
            if s in '01':
                res[int(s)] = 1
                return res
            for k, op in enumerate(s):
                if op in '&^|':
                    left, right = dfs(s