Ways to Bracket a Boolean Expression
An expression alternates symbols and operators, for example T|F&T. Symbols are T for
true and F for false. Operators are & for and, | for or, and ^ for exclusive or.
Count the ways to fully bracket the expression so that it evaluates to TRUE.
Print the count modulo 1000000007.
T|F&T -> 2 (T|(F&T)) and ((T|F)&T)
T&F -> 0
T|T|T -> 2 both bracketings give true
## Why one table is not enough
Every problem in this topic so far carries one value per interval. Here that fails: to count
the TRUE bracketings of a range, you need to know how many bracketings of each SUB-range
give true AND how many give false, because ^ and | produce true from a false operand.
So two tables:
T[i][j] = bracketings of symbols i..j evaluating to true
F[i][j] = bracketings of symbols i..j evaluating to false
Tracking both outcomes rather than only the one asked for is the move, and it is the same shape as problem 550 carrying both extremes: the answer for one value needs the other as an ingredient.
## The recurrence
Split at each operator. With lt, lf for the left part and rt, rf for the right:
``` & true: lt*rt false: lt*rf + lf*rt + lf*rf
| true: lt*rt + lt*rf + lf*rt false: lf*rf
^ true: lt*rf + lf*rt false: lt*rt + lf*rf ```
Each line is the truth table written as a count: every combination of a left bracketing and a right bracketing is a distinct whole bracketing, so the counts MULTIPLY, and the cases that produce the desired value ADD.
Getting those six lines right is the problem. Each one can be checked against the operator's truth table in isolation, which is worth doing rather than trusting the pattern.
## A sanity check worth running
For any range, T[i][j] + F[i][j] must equal the number of bracketings of that range, which
is the Catalan number C(len-1). For three symbols that is 2, for four it is 5.
T|T|T answers 2 and every bracketing gives true, so F is 0 and the total is 2. F&F&F
answers 0 and the total is still 2, all false.
That invariant catches an error in any one of the six lines, and it costs nothing to check by hand on a small input.
## Indexing
Symbols are at even positions of the input string and operators at odd ones. The operator
between symbol k and symbol k+1 is ops[k].
Mixing up the two indexings is the other common error, and it shows up as an answer that is right for expressions with one operator and wrong for longer ones.
## Boundaries
A single symbol has exactly one bracketing: T answers 1 and F answers 0.
The count grows like the Catalan numbers, so the modulus is load-bearing.
## Cost
Time O(n^3) where n is the number of symbols. Space O(n^2).