Boolean Parenthesization
Given a boolean expression of T/F literals joined by the operators &, |, ^, count the number of ways to fully parenthesize it so that it evaluates to True, modulo 109+7.
Input: one line: the expression, e.g. T^F&T.
Output: the number of True-yielding parenthesizations mod 109+7.
Constraints:
- number of literals between 1 and 200
Sample Tests
Input 1
T^F&T
Output 1
2
Input 2
T
Output 2
1
Input 3
F
Output 3
0
Input 4
T|F
Output 4
1
Discussion (opens after you solve — no spoilers before)
No comments yet.