DSA Tracker

Visualize

Boolean Parenthesization

trueDP[i][j] = ways to combine every split k using T/F counts of the two halves

time O(n^3)space O(n^2)

The last operator applied is always the one at some split k between symbols i and j — everything to its left and right is fully parenthesized first. That means a true/false count for symbols i..j only needs the true/false counts of the two halves at every possible k, combined through the truth table of the operator at k. Because '|' and '^' can each be reached by a false half too, tracking ONLY the true count is not enough — falseDP has to be filled alongside trueDP the whole way, which is the one thing that makes this harder than a plain interval sum.

Details

Animated on: exp = "T|T&F^T" (T/F symbols with &, |, ^ operators). Count the ways to parenthesize exp so it evaluates to true.

Problem:Boolean ParenthesizationHard

trueDP[i][j] = ways to combine every split k using T/F counts of the two halves

step 1 / 10

trueDP[i][j]/falseDP[i][j] = ways symbols i..j parenthesize to T / F

Symbol 0 is 'T' alone, so trueDP[0][0] = 1 and falseDP[0][0] = 0 — a lone symbol is exactly one thing, never both.

Pseudocode
1FUNCTION countWays(exp):
2  n <- number of T/F symbols in exp
3  FOR i FROM 0 TO n - 1:
4    trueDP[i][i] <- 1 IF exp[2*i] = 'T' ELSE 0
5    falseDP[i][i] <- 1 IF exp[2*i] = 'F' ELSE 0
6  FOR length FROM 2 TO n:
7    FOR i FROM 0 TO n - length:
8      j <- i + length - 1
9      FOR k FROM i TO j - 1:
10        COMBINE trueDP[i][k], falseDP[i][k] AND trueDP[k+1][j], falseDP[k+1][j] USING exp[2*k+1]
11        ADD result TO trueDP[i][j], falseDP[i][j]
12  RETURN trueDP[0][n-1]

← / → step · space play · Home restart

Every step in words

Show all 10 steps
  1. Symbol 0 is 'T' alone, so trueDP[0][0] = 1 and falseDP[0][0] = 0 — a lone symbol is exactly one thing, never both.
  2. Symbol 1 is 'T' alone, so trueDP[1][1] = 1 and falseDP[1][1] = 0 — a lone symbol is exactly one thing, never both.
  3. Symbol 2 is 'F' alone, so trueDP[2][2] = 0 and falseDP[2][2] = 1 — a lone symbol is exactly one thing, never both.
  4. Symbol 3 is 'T' alone, so trueDP[3][3] = 1 and falseDP[3][3] = 0 — a lone symbol is exactly one thing, never both.
  5. '|' at 0|1 combines 1T/0F with 1T/0F -> +1T/+0F. Summed over every split: 1T/0F for symbols 0..1.
  6. '&' at 1|2 combines 1T/0F with 0T/1F -> +0T/+1F. Summed over every split: 0T/1F for symbols 1..2.
  7. '^' at 2|3 combines 0T/1F with 1T/0F -> +1T/+0F. Summed over every split: 1T/0F for symbols 2..3.
  8. '|' at 0|1 combines 1T/0F with 0T/1F -> +1T/+0F; '&' at 1|2 combines 1T/0F with 0T/1F -> +0T/+1F. Summed over every split: 1T/1F for symbols 0..2.
  9. '&' at 1|2 combines 1T/0F with 1T/0F -> +1T/+0F; '^' at 2|3 combines 0T/1F with 1T/0F -> +1T/+0F. Summed over every split: 2T/0F for symbols 1..3.
  10. '|' at 0|1 combines 1T/0F with 2T/0F -> +2T/+0F; '&' at 1|2 combines 1T/0F with 1T/0F -> +1T/+0F; '^' at 2|3 combines 1T/1F with 1T/0F -> +1T/+1F. Summed over every split: 4T/1F for symbols 0..3 — the whole expression is true in 4 way(s).

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Boolean Parenthesization in the editorAll Dynamic Programming problemsBack to roadmap