Parsing A Boolean Expression

count ways expression returns true

Boolean Evaluation to True

Problem

You are given a boolean expression made of these characters:

• T means true.
• F means false.
• & means logical AND.
• | means logical OR.
• ^ means logical XOR.

The operators sit between the operands, like T|F&T.

Count the number of ways to put parentheses in the expression so that the result is true.

Examples

Example 1

Input: expression = "T^F|F"
Output: 2

• (T ^ F) | F = T | F = T
• T ^ (F | F) = T ^ F = T
• Both ways give true, so the answer is 2.

Example 2

Input: expression = "F&T"
Output: 0

• There is only one way: (F & T), which is false.
• So the answer is 0.

Example 3

Input: expression = "T|T&F^T"
Output: 4

• ((T | T) & F) ^ T = true
• (T | (T & F)) ^ T = false
• (T | T) & (F ^ T) = true
• T | ((T & F) ^ T) = true
• T | (T & (F ^ T)) = true
• Four ways give true, so the answer is 4.

Main Idea

This is a Partition DP problem. It is similar to Matrix Chain Multiplication.

Where to split

• In the expression, operands and operators take turns: operand, operator, operand, operator, and so on.
• So every operator is at a fixed spot, and we can split the expression at each operator.
• When we split at an operator, the left side and the right side become two smaller expressions.

Why we need both counts

For each part, we need to know two numbers:

• The number of ways it can become true.
• The number of ways it can become false.

We need both, because operators mix them in different ways. For example, to make true with |, we can use true | false, false | true or true | true. So we always find leftTrue, leftFalse, rightTrue and rightFalse.

Rules for each operator

We multiply the counts, because every way on the left can be joined with every way on the right.

The DP state

solve(i, j, isTrue) means: the number of ways to put parentheses in expression[i..j] so that the result is isTrue.

Base cases

• If i > j, the range is empty. Return 0.
• If i === j, there is only one character.
  • When isTrue is true: return 1 if the character is T, otherwise 0.
  • When isTrue is false: return 1 if the character is F, otherwise 0.

Solution: Recursion + Memoization (Top-Down)

function countWays(expression) {
    const n = expression.length;

    // dp[i][j] saves the answers for both true and false
    // -1 means "not solved yet"
    const dp = Array.from({ length: n }, () =>
        Array.from({ length: n }, () => ({ true: -1, false: -1 }))
    );

    function solve(i, j, isTrue) {
        // empty range
        if (i > j) return 0;

        // single character
        if (i === j) {
            if (isTrue) return expression[i] === 'T' ? 1 : 0;
            else return expression[i] === 'F' ? 1 : 0;
        }

        // answer is already saved
        if (isTrue && dp[i][j].true !== -1) return dp[i][j].true;
        if (!isTrue && dp[i][j].false !== -1) return dp[i][j].false;

        let ways = 0;

        // split at every operator (operators are at a gap of 2)
        for (let k = i + 1; k < j; k += 2) {
            const leftTrue = solve(i, k - 1, true);
            const leftFalse = solve(i, k - 1, false);
            const rightTrue = solve(k + 1, j, true);
            const rightFalse = solve(k + 1, j, false);

            const op = expression[k];

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

        // save the answer and return it
        if (isTrue) return (dp[i][j].true = ways);
        return (dp[i][j].false = ways);
    }

    // the whole expression, and we want the result to be true
    return solve(0, n - 1, true);
}

How the Code Works

Let us go through the code step by step.

Step 1: Create the dp table

• dp[i][j] is an object with two values: true and false.
• dp[i][j].true is the number of ways expression[i..j] becomes true.
• dp[i][j].false is the number of ways it becomes false.
• We fill both with -1. This means "not solved yet". A real count is never negative.

Step 2: Check the base cases

• Empty range: i > j returns 0.
• One character: The character is either T or F.
  • It gives exactly one way to match its own value, and zero ways to match the other value.

Step 3: Check the saved answer

• If the answer for (i, j, isTrue) is already in the table, we return it.
• This is what makes the solution fast.

Step 4: Loop over every operator

• k is the position of the operator we split at.
• We start from i + 1, because the first character is an operand.
• We jump by 2, because the next operator is two places later.
• The loop stops when k < j, because the last character is also an operand.

Step 5: Find the four sub-answers

• leftTrue and leftFalse come from the range i to k - 1.
• rightTrue and rightFalse come from the range k + 1 to j.

Step 6: Combine with the operator rule

• We read the operator at expression[k].
• We use the table above, based on whether we want true or false at this level.
• We add the result to ways. Each split is a different way to put parentheses, so we add the ways from all splits.

Step 7: Save and return

• We store ways in dp[i][j] and return it.
• The main call is solve(0, n - 1, true). It asks for the ways to make the whole expression true.

Dry Run

Let us take expression = "T^F|F".

The indexes are: 0 = T, 1 = ^, 2 = F, 3 = |, 4 = F.

We call solve(0, 4, true). The operators are at index 1 and index 3.

Split at k = 1 (operator ^):

• Left part is T. So leftTrue = 1 and leftFalse = 0.
• Right part is F|F. Here F | F is false. So rightTrue = 0 and rightFalse = 1.
• For ^ and true: leftTrue * rightFalse + leftFalse * rightTrue = 1 * 1 + 0 * 0 = 1.

Split at k = 3 (operator |):

• Left part is T^F. Here T ^ F is true. So leftTrue = 1 and leftFalse = 0.
• Right part is F. So rightTrue = 0 and rightFalse = 1.
• For | and true: leftTrue * rightTrue + leftTrue * rightFalse + leftFalse * rightTrue = 0 + 1 + 0 = 1.

Total: 1 + 1 = 2.

This matches the expected output.

Complexity

• Time Complexity: O(n³)
  • n is the length of the expression.
  • There are about n * n ranges (i, j), and each range has two states (true and false).
  • Each state is solved only once, and it runs a loop over k that takes up to O(n).
  • So the total is n * n * n = O(n³).
• Space Complexity: O(n²)
  • The dp table has n * n cells, and each cell holds two values.
  • The recursion stack uses up to O(n) extra space.

Version with Modulo

The number of ways can grow very large. So most platforms ask for the answer modulo 1000000007.

There is one thing to be careful about in JavaScript. A normal number is safe only up to about 9 * 10^15. If we multiply two numbers close to 10^9, the result is about 10^18, and we lose accuracy. So we use BigInt for the math.

function countWays(expression) {
    const MOD = 1000000007n;
    const n = expression.length;

    const dp = Array.from({ length: n }, () =>
        Array.from({ length: n }, () => ({ true: -1n, false: -1n }))
    );

    function solve(i, j, isTrue) {
        // empty range
        if (i > j) return 0n;

        // single character
        if (i === j) {
            if (isTrue) return expression[i] === 'T' ? 1n : 0n;
            else return expression[i] === 'F' ? 1n : 0n;
        }

        // answer is already saved
        if (isTrue && dp[i][j].true !== -1n) return dp[i][j].true;
        if (!isTrue && dp[i][j].false !== -1n) return dp[i][j].false;

        let ways = 0n;

        for (let k = i + 1; k < j; k += 2) {
            const leftTrue = solve(i, k - 1, true);
            const leftFalse = solve(i, k - 1, false);
            const rightTrue = solve(k + 1, j, true);
            const rightFalse = solve(k + 1, j, false);

            const op = expression[k];

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

            // keep the number small
            ways %= MOD;
        }

        if (isTrue) return (dp[i][j].true = ways);
        return (dp[i][j].false = ways);
    }

    // convert BigInt back to a normal number
    return Number(solve(0, n - 1, true));
}

Note: The logic is the same as the first solution. The only changes are BigInt values (the n suffix) and the ways %= MOD line.

Comparison with Matrix Chain Multiplication

Summary

• This is a Partition DP problem, like Matrix Chain Multiplication.
• We split the expression at every operator. So the loop jumps by 2.
• Each part needs two counts: the ways to get true and the ways to get false.
• Each operator has its own rule to combine the left and right counts. We multiply the counts of the two sides and add the results of all splits.
• Base cases:
  • An empty range gives 0.
  • A single character gives 1 only if it matches the value we want.
• The dp table saves both answers for each range, so no range is solved twice.
• For big inputs, use the modulo 1000000007 and BigInt in JavaScript.
• The solution runs in O(n³) time and uses O(n²) space.