Problem

Given a boolean expression with following symbols: T & F and following operators filled between symbols:

1
2
3
4

Operators
    &   ---> boolean AND
    |   ---> boolean OR
    ^   ---> boolean XOR

The task is to count the number of ways to parenthesize a given Boolean expression so that it evaluates to True.

Examples

Example 1

1
2
3
4
5
6

Input: symbol[] = {T, F, T}, operator[] = {^, &}
Output: 2
Explanation: 
The given expression is "T ^ F & T". It evaluates `True` in two ways:
1. Parenthesize as "((T ^ F) & T)" -> True
2. Parenthesize as "(T ^ (F & T))" -> True

Example 2

1
2
3
4
5
6
7
8

Input: symbol[] = {T, T, F, T}, operator[] = {|, &, ^}
Output: 4
Explanation: 
Here are 4 ways the expression "T | T & F ^ T" evaluates to true:
1. ((T | T) & (F ^ T))
2. ((T | (T & (F ^ T))))
3. (((T | T) & F) ^ T)
4. (T | (T & (F ^ T)))

Example 3

1
2
3
4
5

Input: symbol[] = {T, T}, operator[] = {|}
Output: 1
Explanation: 
The given expression is "T | T". It evaluates `True` in one way:
1. Parenthesize as "(T | T)" -> True

Example 4

1
2
3
4
5

Input: symbol[] = {T, F}, operator[] = {^}
Output: 1
Explanation: 
The given expression is "T ^ F". It evaluates `True` in one way:
1. Parenthesize as "(T ^ F)" -> True

Similar Problems

Matrix Chain Multiplication

Solution

Method 1 - Dynamic Programming

Reasoning or Intuition

The problem is a variation of dynamic programming where we recursively divide the expression into subproblems based on operators and operands, keeping track of the ways in which the expression evaluates to True and False.

The simplest type of Boolean expression is an expression that contains only one Boolean value, either True (T) or False (F).

For such trivial expressions:

  • If the expression contains T, there is exactly one way to parenthesize it such that it evaluates to True, that is T.
  • If the expression contains F, there is no way to parenthesize it to evaluate to True, since it will always result in False.
Base Cases

To formalise the idea:

  • Let T(i, j) represent the number of ways the Boolean expression from index i to j can be parenthesized such that it evaluates to True.
  • Similarly, let F(i, j) represent the number of ways the expression evaluates to False.

When the expression consists of only one Boolean value (i.e., i == j):

  • T(i, i) = 1 if the operand is T.

  • T(i, i) = 0 if the operand is F.

  • F(i, i) = 0 if the operand is T.

  • F(i, i) = 1 if the operand is F.

  • For each operator, calculate the number of ways operands can evaluate to True and False separately.

  • Depending on the operator (&, |, ^), combine the sub-results using the logical rules of Boolean operations.

  • Memoisation is applied to avoid recalculating results for overlapping subproblems.

Handling Larger Expressions

For expressions longer than a single Boolean value, the problem resembles the Matrix Chain Multiplication problem, where the goal is to partition the expression at different points (operators) and evaluate the sub-expressions. Parentheses can be placed at all possible positions between i and j, splitting the expression into two parts: Expression(i, k) and Expression(k+1, j), where k is the splitting point.

Once the number of ways the sub-expressions evaluate to True is computed, the number of ways the entire expression evaluates to True depends on the operator connecting these sub-expressions.

Boolean Operators and Their Behaviour
When the Operator is & (AND)

For the entire expression Expression(i, j) connected by AND between Expression(i, k) and Expression(k+1, j):

  • The expression evaluates to True only if both sub-expressions are True. Therefore:

    1

     T(i, j) = Σ(T(i, k) * T(k+1, j)) for all k such that i < k < j

  • To compute the number of ways it evaluates to False, note that:

    • At least one of the sub-expressions must evaluate to False. The total number of ways the expression can be parenthesized (whether True or False) is given by Total(i, j):

      1
2

       Total(i, j) = Total(i, k) * Total(k+1, j)
               where Total = T + F

    • Using the difference between total and the ways it evaluates to True:

      1

       F(i, j) = Σ(Total(i, k) * Total(k+1, j) - T(i, k) * T(k+1, j)) for all i < k < j
When the Operator is | (OR)

For the OR operator:

  • The entire expression evaluates to True if either sub-expression is True. Hence:

    1

     T(i, j) = Σ(Total(i, j) - F(i, k) * F(k+1, j)) for all k such that i < k < j

  • Similarly, the expression evaluates to False only if both sub-expressions are False:

    1

     F(i, j) = Σ(F(i, k) * F(k+1, j)) for all i < k < j
When the Operator is ^ (XOR)

For the XOR operator:

  • The expression evaluates to True if one sub-expression is True and the other is False. Thus:

    1

     T(i, j) = Σ((T(i, k) * F(k+1, j)) + (F(i, k) * T(k+1, j))) for all i < k < j

  • On the other hand, the expression evaluates to False if both sub-expressions are either True or False. Hence:

    1

     F(i, j) = Σ((T(i, k) * T(k+1, j)) + (F(i, k) * F(k+1, j))) for all i < k < j

Approach

  1. Recursive Function: Implement a recursive function to evaluate the expression with dynamic programming for efficiency.
  2. Base Cases:
    • Single operand (True or False) directly returns its evaluation count (True = 1, False = 0).
  3. Recursive Logic:
    • Partition the expression into left and right parts based on each operator.
    • Compute the number of ways left and right parts evaluate to True and False.
    • Combine these sub-results depending on the operator logic (&, |, ^).
  4. Dynamic Programming: Use memoisation to store intermediate results for overlapping subproblems.

Code

 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
52
53

#include <iostream>
#include <unordered_map>
#include <string>

using namespace std;

class Solution {
public:
    unordered_map<string, int> memo;

    int countWays(string symbols, string operators, int i, int j, bool isTrue) {
        if (i > j) return 0;
        if (i == j) {
            if (isTrue) return symbols[i] == 'T';
            else return symbols[i] == 'F';
        }

        string key = to_string(i) + " " + to_string(j) + " " + to_string(isTrue);
        if (memo.find(key) != memo.end()) return memo[key];

        int ways = 0;
        for (int k = i; k < j; k++) {
            int leftTrue = countWays(symbols, operators, i, k, true);
            int leftFalse = countWays(symbols, operators, i, k, false);
            int rightTrue = countWays(symbols, operators, k+1, j, true);
            int rightFalse = countWays(symbols, operators, k+1, j, false);

            if (operators[k] == '&') {
                ways += isTrue ? leftTrue * rightTrue : leftTrue * rightFalse + leftFalse * rightTrue + leftFalse * rightFalse;
            }
            else if (operators[k] == '|') {
                ways += isTrue ? leftTrue * rightTrue + leftTrue * rightFalse + leftFalse * rightTrue : leftFalse * rightFalse;
            }
            else if (operators[k] == '^') {
                ways += isTrue ? leftTrue * rightFalse + leftFalse * rightTrue : leftTrue * rightTrue + leftFalse * rightFalse;
            }
        }

        return memo[key] = ways;
    }

    int countWaysToEvaluate(string symbols, string operators) {
        return countWays(symbols, operators, 0, symbols.size() - 1, true);
    }
};

int main() {
    Solution solution;
    string symbols = "TFT";
    string operators = "^&";
    cout << solution.countWaysToEvaluate(symbols, operators) << endl;
    return 0;
}
 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

class Solution {
    HashMap<String, Integer> memo = new HashMap<>();

    int countWays(String symbols, String operators, int i, int j, boolean isTrue) {
        if (i > j) return 0;
        if (i == j) {
            if (isTrue) return symbols.charAt(i) == 'T' ? 1 : 0;
            else return symbols.charAt(i) == 'F' ? 1 : 0;
        }

        String key = i + " " + j + " " + isTrue;
        if (memo.containsKey(key)) return memo.get(key);

        int ways = 0;
        for (int k = i; k < j; k++) {
            int leftTrue = countWays(symbols, operators, i, k, true);
            int leftFalse = countWays(symbols, operators, i, k, false);
            int rightTrue = countWays(symbols, operators, k + 1, j, true);
            int rightFalse = countWays(symbols, operators, k + 1, j, false);

            char operator = operators.charAt(k);
            if (operator == '&') {
                ways += isTrue ? leftTrue * rightTrue : leftTrue * rightFalse + leftFalse * rightTrue + leftFalse * rightFalse;
            } else if (operator == '|') {
                ways += isTrue ? leftTrue * rightTrue + leftTrue * rightFalse + leftFalse * rightTrue : leftFalse * rightFalse;
            } else if (operator == '^') {
                ways += isTrue ? leftTrue * rightFalse + leftFalse * rightTrue : leftTrue * rightTrue + leftFalse * rightFalse;
            }
        }

        memo.put(key, ways);
        return ways;
    }

    int countWaysToEvaluate(String symbols, String operators) {
        return countWays(symbols, operators, 0, symbols.length() - 1, true);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String symbols = "TFT";
        String operators = "^&";
        System.out.println(solution.countWaysToEvaluate(symbols, operators));
    }
}
 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

class Solution:
    def __init__(self):
        self.memo = {}

    def countWays(self, symbols, operators, i, j, isTrue):
        if i > j:
            return 0
        if i == j:
            return 1 if (isTrue and symbols[i] == 'T') or (not isTrue and symbols[i] == 'F') else 0

        key = f"{i} {j} {isTrue}"
        if key in self.memo:
            return self.memo[key]

        ways = 0
        for k in range(i, j):
            leftTrue = self.countWays(symbols, operators, i, k, True)
            leftFalse = self.countWays(symbols, operators, i, k, False)
            rightTrue = self.countWays(symbols, operators, k + 1, j, True)
            rightFalse = self.countWays(symbols, operators, k + 1, j, False)

            operator = operators[k]
            if operator == '&':
                ways += leftTrue * rightTrue if isTrue else leftTrue * rightFalse + leftFalse * rightTrue + leftFalse * rightFalse
            elif operator == '|':
                ways += leftTrue * rightTrue + leftTrue * rightFalse + leftFalse * rightTrue if isTrue else leftFalse * rightFalse
            elif operator == '^':
                ways += leftTrue * rightFalse + leftFalse * rightTrue if isTrue else leftTrue * rightTrue + leftFalse * rightFalse

        self.memo[key] = ways
        return ways

    def countWaysToEvaluate(self, symbols, operators):
        return self.countWays(symbols, operators, 0, len(symbols) - 1, True)


# Example usage
solution = Solution()
symbols = "TFT"
operators = "^&"
print(solution.countWaysToEvaluate(symbols, operators))

Complexity

  • ⏰ Time complexity: O(n^3), as for each partition, problems of size N are solved and there are N´(N-1)/2 partitions.
  • 🧺 Space complexity: O(n^2), due to memoisation storage.