Pattern visualizer
Boolean Parenthesization
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. Animated on: exp = "T|T&F^T" (T/F symbols with &, |, ^ operators). Count the ways to parenthesize exp so it evaluates to true..
trueDP[i][j] = ways to combine every split k using T/F counts of the two halves
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.
1FUNCTION countWays(exp):2 n <- number of T/F symbols in exp3 FOR i FROM 0 TO n - 1:4 trueDP[i][i] <- 1 IF exp[2*i] = 'T' ELSE 05 falseDP[i][i] <- 1 IF exp[2*i] = 'F' ELSE 06 FOR length FROM 2 TO n:7 FOR i FROM 0 TO n - length:8 j <- i + length - 19 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