☕ DSA Java Articles

Topics › Dynamic Programming › MCM DP - Partition DP

Different Ways to Evaluate a Boolean Expression

Medium TUF ID 276 A2Z

Java source ↗ Edit this article ↗

Problem

You are given a boolean expression exp as a string of operands and operators that alternate: operands are T (true) or F (false) and sit at the even indices; operators are & (and), | (or) and ^ (xor) and sit at the odd indices. Count the number of ways to fully parenthesize the expression so that it evaluates to true. Because the count grows very fast, return it modulo 10^9 + 7. This is the problem Striver calls “Evaluate Boolean Expression to True” (DP-52), also known as Boolean Parenthesization.

Two parenthesizations are different when their bracket structures differ, which is the same as saying they apply the operators in a different order. The expression has an odd length; lengths up to a couple of hundred characters are typical, which is what makes an O(n^3) DP acceptable.

Example 1

exp = "T|T&F^T"
answer = 4
// ((T|T)&F)^T = T     (T|(T&F))^T = F     (T|T)&(F^T) = T
// T|((T&F)^T) = T     T|(T&(F^T)) = T

Example 2

exp = "T^F|F"
answer = 2      // (T^F)|F = T and T^(F|F) = T

The key idea: count both outcomes

Like matrix chain multiplication, every full parenthesization has a last operator applied, at some odd index k. It combines a complete parenthesization of the left part exp[i..k-1] with a complete parenthesization of the right part exp[k+1..j]. Different choices of k, or different sub-bracketings on either side, give different overall bracketings, and every bracketing arises exactly once this way. So counts can be multiplied across the two sides and added across choices of k.

The twist is that knowing how many ways each side is true is not enough. An ^ is true when exactly one side is false, and an & is false in three different ways. So each sub-expression must report two numbers: the ways it is true (T) and the ways it is false (F). With L and R for the two sides:

operator ways the result is true ways the result is false
& (and) LT·RT LT·RF + LF·RT + LF·RF
| (or) LT·RT + LT·RF + LF·RT LF·RF
^ (xor) LT·RF + LF·RT LT·RT + LF·RF

That table is the combine helper used by every approach. Each product is reduced modulo 10^9 + 7 before the sum, so all intermediate values stay far below the long limit of about 9.2 × 10^18.

static final long MOD = 1_000_000_007L;

static long combine(char op, boolean wantTrue, long lt, long lf, long rt, long rf) {
    long tt = lt * rt % MOD, tf = lt * rf % MOD, ft = lf * rt % MOD, ff = lf * rf % MOD;
    long ways = switch (op) {
        case '&' -> wantTrue ? tt : tf + ft + ff;
        case '|' -> wantTrue ? tt + tf + ft : ff;
        default -> wantTrue ? tf + ft : tt + ff;            // '^': true when the sides differ
    };
    return ways % MOD;
}

Approach 1: Recursion

Intuition. Let f(i, j, wantTrue) be the number of bracketings of exp[i..j] (with i and j operand positions) that evaluate to wantTrue. A single operand matches or does not: 1 or 0. Otherwise try each operator k = i + 1, i + 3, ..., j - 1 as the last one, get the true and false counts of both sides, and combine them with the table.

Algorithm.

  1. If i == j, return 1 if the operand’s value equals wantTrue, else 0.
  2. For each operator position k between i and j (stepping by 2), compute lt, lf, rt, rf recursively and add combine(...).
  3. Return the sum modulo 10^9 + 7.
static int recursive(String exp) {
    return (int) solve(0, exp.length() - 1, true, exp);
}

static long solve(int i, int j, boolean wantTrue, String exp) {
    if (i == j) return (exp.charAt(i) == 'T') == wantTrue ? 1 : 0;
    long ways = 0;
    for (int k = i + 1; k < j; k += 2) {                    // exp[k] is the operator evaluated last
        long lt = solve(i, k - 1, true, exp), lf = solve(i, k - 1, false, exp);
        long rt = solve(k + 1, j, true, exp), rf = solve(k + 1, j, false, exp);
        ways = (ways + combine(exp.charAt(k), wantTrue, lt, lf, rt, rf)) % MOD;
    }
    return ways;
}

Complexity. Exponential: the number of bracketings of m operands is the Catalan number C(m - 1), and this recursion recomputes shared sub-expressions over and over. Space O(n) for the depth.

Approach 2: Memoization

Intuition. The state is (i, j, wantTrue): O(n^2) ranges times 2. Store each count in dp[i][j][want], with -1 as “not computed” (counts are never negative). Here want is an int (1 for true, 0 for false) so it can index the array.

Algorithm.

  1. Fill dp with -1.
  2. Same recursion; return the cached value when present and store each result.
static int memoization(String exp) {
    int n = exp.length();
    long[][][] dp = new long[n][n][2];
    for (long[][] plane : dp) for (long[] row : plane) Arrays.fill(row, -1);
    return (int) memo(0, n - 1, 1, exp, dp);
}

static long memo(int i, int j, int want, String exp, long[][][] dp) {
    if (i == j) return (exp.charAt(i) == 'T') == (want == 1) ? 1 : 0;
    if (dp[i][j][want] != -1) return dp[i][j][want];
    long ways = 0;
    for (int k = i + 1; k < j; k += 2) {
        long lt = memo(i, k - 1, 1, exp, dp), lf = memo(i, k - 1, 0, exp, dp);
        long rt = memo(k + 1, j, 1, exp, dp), rf = memo(k + 1, j, 0, exp, dp);
        ways = (ways + combine(exp.charAt(k), want == 1, lt, lf, rt, rf)) % MOD;
    }
    return dp[i][j][want] = ways;
}

Complexity. Time O(n^3): O(n^2) states, each scanning O(n) operators. Space O(n^2) for the table plus O(n) stack.

Approach 3: Tabulation

Intuition. Cell (i, j) needs (i, k - 1), a shorter range in the same row, and (k + 1, j), a range starting further right. So process start positions i from right to left and end positions j from left to right, both stepping by 2 because only operand positions are states. The diagonal is the base case: dp[i][i][1] is 1 for T, and dp[i][i][0] is 1 for F.

Algorithm.

  1. For i from n - 1 down to 0 in steps of 2: set the base case for (i, i).
  2. For j from i + 2 up to n - 1 in steps of 2, and for want in {0, 1}: sum combine over the operators between them.
  3. Return dp[0][n - 1][1].
static int tabulation(String exp) {
    int n = exp.length();
    long[][][] dp = new long[n][n][2];                      // [i][j][1] = ways true, [i][j][0] = ways false
    for (int i = n - 1; i >= 0; i -= 2) {
        dp[i][i][1] = exp.charAt(i) == 'T' ? 1 : 0;
        dp[i][i][0] = exp.charAt(i) == 'F' ? 1 : 0;
        for (int j = i + 2; j < n; j += 2) {
            for (int want = 0; want <= 1; want++) {
                long ways = 0;
                for (int k = i + 1; k < j; k += 2) {
                    ways = (ways + combine(exp.charAt(k), want == 1,
                            dp[i][k - 1][1], dp[i][k - 1][0], dp[k + 1][j][1], dp[k + 1][j][0])) % MOD;
                }
                dp[i][j][want] = ways;
            }
        }
    }
    return (int) dp[0][n - 1][1];
}

Dry run on Example 2, "T^F|F" (operands at 0, 2, 4):

range text true false
(4, 4) F 0 1
(2, 2) F 0 1
(2, 4) F|F 0 1
(0, 0) T 1 0
(0, 2) T^F 1 0
(0, 4) T^F|F split at ^: T^(F|F), 1·1 = 1; split at \|: (T^F)|F, 1·1 = 1 total 2

Complexity. Time O(n^3), space O(n^2). As in other interval DPs, the full table is needed.

Edge cases and pitfalls