Different Ways to Evaluate a Boolean Expression
MediumCount true and false ways separately
Problem
Count the ways to parenthesize a boolean expression so it evaluates to true.
Interval DP: split at each operator, combining the true/false counts of both sides.
The idea
For each operator position, combine the counts from the left and right sides according to that operator's truth table. Both counts are needed because an OR can be made true by a false left side and a true right one.
The trick
- State: (start, end, desired result) — the boolean is part of the state.
- AND, OR and XOR each combine the four count products differently.
- O(n³) over operator positions.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — T|T&F^T Values: 0.
1dp[i][j][result] = ways for s[i..j] to equal result2split at each operator combining left/right countsInput
- array
- [0]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- exp = "T|T&F"
- Output:
- 1
- Explanation:
- Different parenthesisations that evaluate to True.
Example 2
- Input:
- exp = "T^T^F"
- Output:
- 0
- Explanation:
- 0 ways give True.
Example 3
- Input:
- exp = "T"
- Output:
- 1
- Explanation:
- A single T is already True → 1.
Practice this problem:GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.