Boolean Parenthesization

Boolean Parenthesization is a classic interval-DP problem. You are handed a boolean expression with no parentheses, and you have to count how many ways you could add parentheses so the whole thing evaluates to True. The trick is to think about the last operator applied, and to count both the True and the False ways for every sub-expression.

The slow way first

The brute-force idea is to literally generate every possible parenthesization. Each operator could be the outermost (last) one, and inside each side you recurse again. The number of full parenthesizations of n operands is a Catalan number, which grows roughly like 4^n. For even a medium expression that is hopeless.

The question to ask: what is the smallest piece I keep recomputing? It is the count for a sub-expression — the span of operands from i to j. The brute force solves that same span over and over. If we store each span's answer once, we get a clean dynamic program.

The idea: count True and False for every span

Define two tables over operand spans i..j:

• T[i][j] — number of parenthesizations of the span that evaluate to True
• F[i][j] — number that evaluate to False

We need both, because combining two sides depends on their False counts too (an and is False if either side is False). For a single operand the answer is trivial: T gives T=1, F=0; F gives T=0, F=1. For a longer span we pick each operator k inside it as the last operation, look up the already-computed left counts and right counts, and combine them by that operator's truth table.

The combine rules, given left counts (lt, lf) and right counts (rt, rf) and tot = (lt+lf)*(rt+rf):

• and (&): True needs both sides True → T += lt*rt, the rest go to F.
• or (|): True unless both sides False → T += tot - lf*rf, and F += lf*rf.
• xor (^): True when the sides differ → T += lt*rf + lf*rt, the rest are False.

Walk through it

Step through the animation. We fill the smallest spans first (single operands on the diagonal), then length-2 spans like T | T, T & F, F ^ T, then length-3 spans, and finally the whole expression. Each time we widen a span we slide the k pointer across its inner operators, read the left/right counts the tables already hold, and add the combined True-ways. The final answer lands in T[0][n-1].

Pseudocode

ops  = operators of expr          # the odd-position symbols
vals = operands of expr           # the even-position T / F symbols
T, F = n x n tables of zeros
 
for each i:                       # base case: one operand
    T[i][i] = 1 if vals[i] == "T" else 0
    F[i][i] = 1 if vals[i] == "F" else 0
 
for length = 2 .. n:
    for each start i (with end j = i + length - 1):
        for each operator k strictly inside i..j:
            read left counts  (lt, lf) = T[i][k],  F[i][k]
            read right counts (rt, rf) = T[k+1][j], F[k+1][j]
            tot = (lt + lf) * (rt + rf)
            combine by ops[k] into T[i][j] and F[i][j]
 
return T[0][n-1]                  # ways the whole expression is True

The Python solution

def count_true(expr):
    ops = expr[1::2]              # operators between operands
    vals = expr[0::2]             # operands, each 'T' or 'F'
    n = len(vals)
    T = [[0] * n for _ in range(n)]
    F = [[0] * n for _ in range(n)]
    for i in range(n):           # base case: single operand
        T[i][i] = 1 if vals[i] == 'T' else 0
        F[i][i] = 1 if vals[i] == 'F' else 0
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            for k in range(i, j):              # split at operator ops[k]
                lt, lf = T[i][k], F[i][k]
                rt, rf = T[k + 1][j], F[k + 1][j]
                tot = (lt + lf) * (rt + rf)
                if ops[k] == '&':
                    T[i][j] += lt * rt; F[i][j] += tot - lt * rt
                elif ops[k] == '|':
                    T[i][j] += tot - lf * rf; F[i][j] += lf * rf
                else:
                    T[i][j] += lt * rf + lf * rt; F[i][j] += lt * rt + lf * rf
    return T[0][n - 1]

• ops and vals slice the alternating string: even positions are operands, odd positions are operators.
• T and F are n x n tables; T[i][j] is the True-count for the operand span i..j.
• The first loop fills the diagonal — a single operand is True or False with exactly one parenthesization.
• length grows the span; for each span we set j and loop k over every inner operator as the last operation.
• lt, lf, rt, rf are the left and right True/False counts, read straight from the tables (already computed because they cover shorter spans).
• The if / elif / else is the combine step — each operator routes tot into True or False counts by its truth table.
• The answer is T[0][n-1]: the number of full parenthesizations of the whole expression that are True.

Complexity

The two n x n tables are the O(n^2) space; the three nested loops (length, i, k) give O(n^3) time. That is the signature shape of interval DP: a span, a split point inside it, and answers combined from two shorter spans.

When this pattern shows up

Practice