Boolean Parenthesization: True Evaluations Count
Given a boolean expression with symbols (T for true, F for false) and operators (&, |, ^), how many ways can you parenthesize it to make the result evaluate to true?
Key Insights
- Boolean parenthesization is a classic interval DP problem where you split expressions at each operator and combine subproblem results using truth table logic
- The key insight is tracking both true AND false counts for each substring—you need both because operators like XOR require knowing false combinations to compute true results
- This pattern appears whenever you’re counting ways to evaluate or combine elements with binary operations, from compiler optimization to circuit analysis
The Parenthesization Problem
Given a boolean expression with symbols (T for true, F for false) and operators (&, |, ^), how many ways can you parenthesize it to make the result evaluate to true?
Consider the expression T ^ F & T. Without parentheses, the evaluation order is ambiguous. You could evaluate it as (T ^ F) & T = T & T = T or as T ^ (F & T) = T ^ F = T. Both happen to give true, but that’s not always the case. The problem asks: count all parenthesizations that yield true.
This isn’t just an academic exercise. Compilers face similar problems when optimizing boolean expressions. Circuit designers need to understand how gate arrangements affect outputs. Decision tree analysis often reduces to counting valid evaluation paths. The pattern shows up more often than you’d expect.
Understanding the Problem Space
Let’s establish the structure. A valid expression alternates between symbols and operators: symbol operator symbol operator symbol.... If you have n symbols, you have n-1 operators. We’ll index symbols at even positions (0, 2, 4…) and operators at odd positions (1, 3, 5…).
Walk through T ^ F & T manually:
Symbols: T, F, T (positions 0, 2, 4)
Operators: ^, & (positions 1, 3)
Parenthesization 1: (T ^ F) & T
T ^ F = T
T & T = T ✓
Parenthesization 2: T ^ (F & T)
F & T = F
T ^ F = T ✓
Both evaluate to true, so answer = 2
Why can’t we brute force this? The number of ways to parenthesize n operands is the Catalan number C(n-1), which grows as O(4^n / n^(3/2)). For 10 operands, that’s 4,862 parenthesizations. For 20, it’s over 1.7 billion. Exponential growth kills brute force fast.
Here’s what naive recursion looks like:
def count_true_naive(symbols, operators):
"""Naive recursive solution - exponential time complexity."""
n = len(symbols)
def count(start, end, want_true):
# Base case: single symbol
if start == end:
is_true = symbols[start] == 'T'
return 1 if (is_true == want_true) else 0
total = 0
# Try each operator as the "last" operation
for k in range(start, end):
# Left subexpression: symbols[start..k]
# Right subexpression: symbols[k+1..end]
# Operator between them: operators[k]
left_true = count(start, k, True)
left_false = count(start, k, False)
right_true = count(k + 1, end, True)
right_false = count(k + 1, end, False)
op = operators[k]
if want_true:
if op == '&':
total += left_true * right_true
elif op == '|':
total += left_true * right_true + left_true * right_false + left_false * right_true
elif op == '^':
total += left_true * right_false + left_false * right_true
else:
if op == '&':
total += left_false * right_false + left_true * right_false + left_false * right_true
elif op == '|':
total += left_false * right_false
elif op == '^':
total += left_true * right_true + left_false * right_false
return total
return count(0, n - 1, True)
This recalculates the same subproblems repeatedly. Time for DP.
Dynamic Programming Approach
The optimal substructure is clear: to evaluate expression from index i to j, pick some operator k in between as the “root” operation. The left side (i to k) combines with the right side (k+1 to j) via operator k.
Here’s the critical insight: you need to track both true and false counts. Why? Consider XOR: T ^ F = T and F ^ T = T. To count ways to get true from XOR, you need left_true * right_false + left_false * right_true. You can’t compute this without knowing false counts.
Define:
T[i][j]= number of ways substring from symbol i to symbol j evaluates to trueF[i][j]= number of ways substring from symbol i to symbol j evaluates to false
The recurrence for each operator:
For operator op at position k between symbols i..k and k+1..j:
AND (&):
T contribution: T[i][k] * T[k+1][j]
F contribution: F[i][k] * F[k+1][j] + T[i][k] * F[k+1][j] + F[i][k] * T[k+1][j]
OR (|):
T contribution: T[i][k] * T[k+1][j] + T[i][k] * F[k+1][j] + F[i][k] * T[k+1][j]
F contribution: F[i][k] * F[k+1][j]
XOR (^):
T contribution: T[i][k] * F[k+1][j] + F[i][k] * T[k+1][j]
F contribution: T[i][k] * T[k+1][j] + F[i][k] * F[k+1][j]
These are just truth tables converted to counting formulas.
Implementation: Bottom-Up DP Solution
def count_parenthesizations(expression: str) -> int:
"""
Count ways to parenthesize boolean expression to evaluate to true.
Expression format: "T^F&T" (alternating symbols and operators)
Returns: number of parenthesizations that yield true
"""
# Parse expression
symbols = expression[::2] # Characters at even indices
operators = expression[1::2] # Characters at odd indices
n = len(symbols)
if n == 0:
return 0
# T[i][j] = ways for symbols[i..j] to be true
# F[i][j] = ways for symbols[i..j] to be false
T = [[0] * n for _ in range(n)]
F = [[0] * n for _ in range(n)]
# Base case: single symbols
for i in range(n):
if symbols[i] == 'T':
T[i][i] = 1
F[i][i] = 0
else:
T[i][i] = 0
F[i][i] = 1
# Fill by increasing substring length
for length in range(2, n + 1): # length = number of symbols
for i in range(n - length + 1):
j = i + length - 1
# Try each split point
for k in range(i, j):
# Left: symbols[i..k], Right: symbols[k+1..j]
# Operator between them: operators[k]
left_t, left_f = T[i][k], F[i][k]
right_t, right_f = T[k + 1][j], F[k + 1][j]
op = operators[k]
if op == '&':
T[i][j] += left_t * right_t
F[i][j] += left_f * right_f + left_t * right_f + left_f * right_t
elif op == '|':
T[i][j] += left_t * right_t + left_t * right_f + left_f * right_t
F[i][j] += left_f * right_f
elif op == '^':
T[i][j] += left_t * right_f + left_f * right_t
F[i][j] += left_t * right_t + left_f * right_f
return T[0][n - 1]
Complexity analysis:
- Time: O(n³) — two nested loops for i,j pairs (O(n²)), inner loop for split points (O(n))
- Space: O(n²) — two n×n tables
Optimizations and Variations
For large expressions, results grow astronomically. Use modular arithmetic:
def count_parenthesizations_mod(expression: str, MOD: int = 10**9 + 7) -> int:
"""Memoized version with modular arithmetic for large results."""
symbols = expression[::2]
operators = expression[1::2]
n = len(symbols)
from functools import lru_cache
@lru_cache(maxsize=None)
def solve(i: int, j: int, want_true: bool) -> int:
# Base case
if i == j:
is_true = symbols[i] == 'T'
return 1 if (is_true == want_true) else 0
total = 0
for k in range(i, j):
left_t = solve(i, k, True)
left_f = solve(i, k, False)
right_t = solve(k + 1, j, True)
right_f = solve(k + 1, j, False)
op = operators[k]
if want_true:
if op == '&':
total += left_t * right_t
elif op == '|':
total += left_t * right_t + left_t * right_f + left_f * right_t
elif op == '^':
total += left_t * right_f + left_f * right_t
else:
if op == '&':
total += left_f * right_f + left_t * right_f + left_f * right_t
elif op == '|':
total += left_f * right_f
elif op == '^':
total += left_t * right_t + left_f * right_f
total %= MOD
return total
return solve(0, n - 1, True)
Memoization often has cleaner code than tabulation for this problem. The cache handles the dependency ordering automatically.
Testing and Edge Cases
import unittest
class TestBooleanParenthesization(unittest.TestCase):
def test_single_true(self):
self.assertEqual(count_parenthesizations("T"), 1)
def test_single_false(self):
self.assertEqual(count_parenthesizations("F"), 0)
def test_two_symbols_and(self):
self.assertEqual(count_parenthesizations("T&T"), 1)
self.assertEqual(count_parenthesizations("T&F"), 0)
self.assertEqual(count_parenthesizations("F&F"), 0)
def test_two_symbols_or(self):
self.assertEqual(count_parenthesizations("T|F"), 1)
self.assertEqual(count_parenthesizations("F|F"), 0)
def test_two_symbols_xor(self):
self.assertEqual(count_parenthesizations("T^F"), 1)
self.assertEqual(count_parenthesizations("T^T"), 0)
def test_example_expression(self):
# T ^ F & T has 2 ways to be true
self.assertEqual(count_parenthesizations("T^F&T"), 2)
def test_all_true_and(self):
# T & T & T - only one way, always true
self.assertEqual(count_parenthesizations("T&T&T"), 2)
def test_impossible_expression(self):
# F & F & F - can never be true
self.assertEqual(count_parenthesizations("F&F&F"), 0)
def test_longer_expression(self):
# T | T & F ^ T
result = count_parenthesizations("T|T&F^T")
self.assertGreater(result, 0)
if __name__ == "__main__":
unittest.main()
When to Apply This Pattern
Boolean parenthesization is a specific instance of interval DP (also called range DP). The pattern applies when:
- You’re combining contiguous subarrays/substrings
- The combination depends on a binary operation at the split point
- You need to count or optimize over all possible split orderings
Related problems include matrix chain multiplication (minimize scalar multiplications), optimal BST construction, and burst balloons. The structure is identical: define states over intervals, iterate by interval length, try all split points.
If you see a problem asking “count ways to evaluate” or “find optimal ordering of operations,” think interval DP. The boolean parenthesization pattern—tracking multiple result types (true/false, or min/max) for each interval—transfers directly.