Java - Boolean Parenthesization Problem
Problem Statement
Given a Boolean expression S containing T (true), F (false), & (AND), | (OR), ^ (XOR),
Find the number of ways to parenthesize S so that the result is True.
Example 1
Input: S = "T|F&T^T"
Output: 4
Explanation:
- (T | (F & (T ^ T))) → True
- ((T | F) & (T ^ T)) → True
- (T | (F & T)) ^ T → True
- ((T | (F & T)) ^ T) → True
Approach 1: Recursive Solution
We recursively evaluate all possible parenthesizations.
public class BooleanParenthesization {
public static int countWays(String s, int i, int j, boolean isTrue) {
if (i > j) return 0; // Invalid case
if (i == j) { // Base case: single character
if (isTrue) return s.charAt(i) == 'T' ? 1 : 0;
else return s.charAt(i) == 'F' ? 1 : 0;
}
int ways = 0;
for (int k = i + 1; k < j; k += 2) { // Operators at odd positions
int leftTrue = countWays(s, i, k - 1, true);
int leftFalse = countWays(s, i, k - 1, false);
int rightTrue = countWays(s, k + 1, j, true);
int rightFalse = countWays(s, k + 1, j, false);
char operator = s.charAt(k);
if (operator == '&') {
if (isTrue) ways += leftTrue * rightTrue;
else ways += leftFalse * rightTrue + leftTrue * rightFalse + leftFalse * rightFalse;
} else if (operator == '|') {
if (isTrue) ways += leftTrue * rightTrue + leftTrue * rightFalse + leftFalse * rightTrue;
else ways += leftFalse * rightFalse;
} else if (operator == '^') {
if (isTrue) ways += leftTrue * rightFalse + leftFalse * rightTrue;
else ways += leftTrue * rightTrue + leftFalse * rightFalse;
}
}
return ways;
}
public static void main(String[] args) {
String s = "T|F&T^T";
int n = s.length();
System.out.println("Ways to parenthesize for True: " + countWays(s, 0, n - 1, true)); // Output: 4
}
}
Complexity Analysis
Time Complexity: O(2^N) (Exponential)
Space Complexity: O(N) (Recursive Stack)
Approach 2: Memoization (Top-Down DP)
To avoid redundant calculations, we use a HashMap (dp).
import java.util.*;
public class BooleanParenthesizationMemo {
static Map<String, Integer> dp = new HashMap<>();
public static int countWays(String s, int i, int j, boolean isTrue) {
if (i > j) return 0;
if (i == j) return (isTrue == (s.charAt(i) == 'T')) ? 1 : 0;
String key = i + "_" + j + "_" + isTrue;
if (dp.containsKey(key)) return dp.get(key);
int ways = 0;
for (int k = i + 1; k < j; k += 2) {
int leftTrue = countWays(s, i, k - 1, true);
int leftFalse = countWays(s, i, k - 1, false);
int rightTrue = countWays(s, k + 1, j, true);
int rightFalse = countWays(s, k + 1, j, false);
char operator = s.charAt(k);
if (operator == '&') {
if (isTrue) ways += leftTrue * rightTrue;
else ways += leftFalse * rightTrue + leftTrue * rightFalse + leftFalse * rightFalse;
} else if (operator == '|') {
if (isTrue) ways += leftTrue * rightTrue + leftTrue * rightFalse + leftFalse * rightTrue;
else ways += leftFalse * rightFalse;
} else if (operator == '^') {
if (isTrue) ways += leftTrue * rightFalse + leftFalse * rightTrue;
else ways += leftTrue * rightTrue + leftFalse * rightFalse;
}
}
dp.put(key, ways);
return ways;
}
public static void main(String[] args) {
String s = "T|F&T^T";
int n = s.length();
System.out.println("Ways to parenthesize for True: " + countWays(s, 0, n - 1, true)); // Output: 4
}
}
Complexity Analysis
Time Complexity: O(N^3)
Space Complexity: O(N^2)
Approach 3: Bottom-Up Dynamic Programming (Tabulation)
Instead of recursion, we build a DP table iteratively.
import java.util.*;
public class BooleanParenthesizationDP {
public static int countWays(String s) {
int n = s.length();
int[][] trueWays = new int[n][n];
int[][] falseWays = new int[n][n];
for (int i = 0; i < n; i += 2) {
trueWays[i][i] = (s.charAt(i) == 'T') ? 1 : 0;
falseWays[i][i] = (s.charAt(i) == 'F') ? 1 : 0;
}
for (int len = 3; len <= n; len += 2) {
for (int i = 0; i < n - len + 1; i += 2) {
int j = i + len - 1;
for (int k = i + 1; k < j; k += 2) {
int leftTrue = trueWays[i][k - 1];
int leftFalse = falseWays[i][k - 1];
int rightTrue = trueWays[k + 1][j];
int rightFalse = falseWays[k + 1][j];
char operator = s.charAt(k);
if (operator == '&') {
trueWays[i][j] += leftTrue * rightTrue;
falseWays[i][j] += leftFalse * rightTrue + leftTrue * rightFalse + leftFalse * rightFalse;
} else if (operator == '|') {
trueWays[i][j] += leftTrue * rightTrue + leftTrue * rightFalse + leftFalse * rightTrue;
falseWays[i][j] += leftFalse * rightFalse;
} else if (operator == '^') {
trueWays[i][j] += leftTrue * rightFalse + leftFalse * rightTrue;
falseWays[i][j] += leftTrue * rightTrue + leftFalse * rightFalse;
}
}
}
}
return trueWays[0][n - 1];
}
public static void main(String[] args) {
String s = "T|F&T^T";
System.out.println("Ways to parenthesize for True: " + countWays(s)); // Output: 4
}
}
