Introduction

The boolean parenthesization problem asks how many ways a boolean expression can be parenthesized so that it evaluates to True. A brute-force recursive solution quickly explodes because the same subexpressions are recomputed many times. The standard implementation uses dynamic programming to count true and false outcomes for every subrange of the expression.

Problem Setup

The input is usually split into two strings:

• symbols such as TFT
• operators such as ^&

For example, the expression T ^ F & T can be represented as:

symbols = "TFT"
operators = "^&"

The goal is to count parenthesizations that make the full expression True, not merely to evaluate it once.

Dynamic Programming State

For each subexpression from index i to j, store two values:

• 'true_dp[i][j]: number of ways it evaluates to True'
• 'false_dp[i][j]: number of ways it evaluates to False'

The base case is a single symbol:

• 'T gives one true way and zero false ways'
• 'F gives zero true ways and one false way'

Then expand to longer ranges by picking every possible split point k and combining left and right counts according to the operator at k.

Python Implementation

1def count_true_parenthesizations(symbols, operators):
2    n = len(symbols)
3    true_dp = [[0] * n for _ in range(n)]
4    false_dp = [[0] * n for _ in range(n)]
5
6    for i, ch in enumerate(symbols):
7        true_dp[i][i] = 1 if ch == "T" else 0
8        false_dp[i][i] = 1 if ch == "F" else 0
9
10    for length in range(2, n + 1):
11        for i in range(n - length + 1):
12            j = i + length - 1
13
14            for k in range(i, j):
15                op = operators[k]
16
17                lt = true_dp[i][k]
18                lf = false_dp[i][k]
19                rt = true_dp[k + 1][j]
20                rf = false_dp[k + 1][j]
21
22                total_left = lt + lf
23                total_right = rt + rf
24
25                if op == "&":
26                    true_dp[i][j] += lt * rt
27                    false_dp[i][j] += total_left * total_right - lt * rt
28                elif op == "|":
29                    false_dp[i][j] += lf * rf
30                    true_dp[i][j] += total_left * total_right - lf * rf
31                elif op == "^":
32                    true_dp[i][j] += lt * rf + lf * rt
33                    false_dp[i][j] += lt * rt + lf * rf
34                else:
35                    raise ValueError(f"Unsupported operator: {op}")
36
37    return true_dp[0][n - 1]
38
39
40print(count_true_parenthesizations("TFT", "^&"))

This implementation runs in O(n^3) time because it considers every range and every split point inside that range. The tables take O(n^2) space.

Why the Transition Works

The important idea is that each operator combines counts, not raw boolean values.

If the operator is &, the combined expression is true only when both sides are true. If the operator is |, the combined expression is false only when both sides are false. If the operator is ^, the combined expression is true when the sides differ.

That is why the DP stores both true and false counts. You need both to compute the next range correctly.

Recursive Version Versus DP

A naive recursive implementation mirrors the mathematical definition nicely, but it repeats the same subproblems again and again. Dynamic programming removes that waste by storing answers for subranges once.

For interview and contest settings, memoized recursion is often a good intermediate step. For production-quality clarity and predictable complexity, the bottom-up DP is usually easier to reason about.

Common Pitfalls

• Forgetting to track false counts as well as true counts.
• Misaligning operator indexes with symbol indexes.
• Treating the operators as normal precedence rules. In this problem, every legal parenthesization counts.
• Writing the recursion first and never memoizing it, which causes exponential runtime.
• Returning a boolean instead of the number of valid parenthesizations.

Summary

• Boolean parenthesization is a counting problem, not just an evaluation problem.
• The standard solution stores true and false counts for every subexpression.
• Each operator has its own count-combination rule.
• A bottom-up DP runs in O(n^3) time and O(n^2) space.
• Most bugs come from index mistakes or from forgetting that false counts are part of the state.