558. 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).

Constraints - the expression has between `1` and `100` symbols - symbols are `T` or `F` - operators are `&`, `|` or `^`