Evaluate Boolean Expression to True
Partition DP & MCM DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Counting Ways to Parenthesize a Boolean Expression for a True Result, Dynamic Programming, Recursion, Memoization, Tabulation, Boolean Logic, Operator Precedence, Modulo Arithmetic, Time Complexity, Space Complexity, Overlapping Subproblems, Optimal Substructure, Partition DP, bit manipulation, dynamic programming, memoization, divide and conquer, tabulation, recursion base case, state space definition, recursion, time complexity analysis, Partition DP.
Given a boolean expression expression consisting of operands ('T' for true, 'F' for false) and operators ('|' for OR, '&' for AND, '^' for XOR), find the number of ways to parenthesize the expression such that it evaluates to 'true'. The result should be returned modulo 1000000007. You are not allowed to change the order of operands and operators. Only the grouping of sub expressions can be changed using parentheses. Input Format: A single string expression, representing the boolean expression. The expression will always be valid and follow the pattern: operand, operator, operand, operator, ..., operand. Output Format: An integer representing the number of ways to evaluate the expression to true, modulo 1000000007. Constraints: The length of expression (N) will be between 1 and 200. expression will only contain 'T', 'F', '&', '|', '^'. The first and last characters of expression will always be operands ('T' or 'F'). Operators will always be at odd indices (1, 3, 5, ...). Example 1: Input: expression = "T|T&F" Output: 1 Explanation: The only way to get the result as true is: (T) | (T&F) = T | F = T Example 2: Input: expression = "F|T^F" Output: 2 Explanation: There are 2 possible ways to get the result as true: 1. (F|T) ^ F = T ^ F = T 2. F | (T^F) = F | T = T