Boolean Evaluation Problem in Java
In the field of Computer Science and Engineering, evaluating boolean expressions is a fundamental activity with several applications. Boolean expressions are made up of boolean values (TRUE or FALSE) and logical operators (AND, OR, XOR) that specify the relationships and conditions between these values. Consider the expression 'exp' as a string, with operands being boolean values (TRUE or FALSE) and operators being logical connectives (AND, OR, XOR). The goal is to provide a reliable method for evaluating a given boolean statement and calculating the number of ways it can result in a TRUE answer.
Example
Input
Symbol [] = {T, T, F, T}
Operator [] = {|, &, ^}
Output
4
Explanation
The given expression is "T | T & F ^ T", it evaluates true in 4 ways ((T|T)&(F^T)), (T|(T&(F^T))), (((T|T)&F)^T) and (T|((T&F)^T)).
Approach 1: Using Recursion
The recursive function, in this case 'findWays', is designed to handle these problems by repeatedly calling itself with reduced or modified inputs to determine the number of ways a boolean expression can be parenthesized to result in a 'TRUE' evaluation
Algorithm
Step 1: Define a function findWays that takes four parameters:
Step 1.1: exp: The boolean expression in the form of a string, st: Starting index for the current sub-expression.
Step 1.2: end: Ending index for the current sub-expression, isTrue: Boolean indicating whether the current sub-expression should evaluate to 'TRUE' or 'FALSE.'
Step 2: If st > end, return false as this sub-expression is invalid.
Step 2.1: If st is equal to end, if isTrue is true: Return true if the current element is 'T'; otherwise, return false.
Step 2.2: If isTrue is false: Return true if the current element is 'F'; otherwise, return false.
Step 3: Initialize an integer variable ans to 0. Run a loop over exp for st + 1 <= k <= end - 1 and do the following: Calculate the number of ways the left part of the expression can be true and false (leftTrue and leftFalse) by making recursive calls to findWays.
Step 4: Calculate the number of ways the right part of the expression can be true and false (rightTrue and rightFalse) by making recursive calls to findWays. Set isTrue to true if finding ways for 'TRUE' is required; otherwise, set it to false.
Step 5: Based on the operator at position k in the expression, update ans using the truth table: For 'AND', update ans += leftTrue * rightTrue, for 'OR', update ans += leftTrue * rightTrue + leftTrue * rightFalse + leftFalse * rightTrue.
Step 6: For 'XOR', update ans += leftTrue * rightFalse + leftFalse * rightTrue. Return true if ans is greater than 0; otherwise, return false.
Step 7: In the main method, define a boolean expression as a string, e.g., "T|F&T^F".
Step 8: Call the findWays function with the expression, starting index 0, ending index expression.length() - 1, and the target of finding ways for 'TRUE.'
Step 9: Print the result indicating whether the expression can be parenthesized to evaluate to 'TRUE.'
Filename: BooleanExpressionParenthesization.java
public class BooleanExpressionParenthesization {
public static int findWays(String exp, int st, int end, boolean isTrue) {
// Base cases
if (st > end) {
return 0;
}
if (st == end) {
if (isTrue) {
return exp.charAt(st) == 'T' ? 1 : 0;
} else {
return exp.charAt(st) == 'F' ? 1 : 0;
}
}
// Recursive calls
int ans = 0;
for (int k = st + 1; k <= end - 1; k += 2) {
int leftTrue = findWays(exp, st, k - 1, true);
int leftFalse = findWays(exp, st, k - 1, false);
int rightTrue = findWays(exp, k + 1, end, true);
int rightFalse = findWays(exp, k + 1, end, false);
// Combine results based on operator and isTrue
if (exp.charAt(k) == '&') {
if (isTrue) {
ans += leftTrue * rightTrue;
} else {
ans += leftTrue * rightFalse + leftFalse * rightTrue + leftFalse * rightFalse;
}
} else if (exp.charAt(k) == '|') {
if (isTrue) {
ans += leftTrue * rightTrue + leftTrue * rightFalse + leftFalse * rightTrue;
} else {
ans += leftFalse * rightFalse;
}
} else if (exp.charAt(k) == '^') {
if (isTrue) {
ans += leftTrue * rightFalse + leftFalse * rightTrue;
} else {
ans += leftTrue * rightTrue + leftFalse * rightFalse;
}
}
}
return ans;
}
public static void main(String[] args) {
String expression = "T|F&T^F";
int result = findWays(expression, 0, expression.length() - 1, true);
System.out.println("Number of ways the expression can be parenthesized to evaluate to TRUE: " + result);
}
}
Output:
Number of ways the expression can be parenthesized to evaluate to TRUE: 5
Time Complexity
The time complexity of the provided algorithm is exponential, specifically O(3^n), where 'n' is the length of the input boolean expression. It is because, in the worst case, the algorithm explores all possible combinations of parenthesization for each sub-expression. The recursive calls and the loop over operators contribute to this exponential time complexity.
Space Complexity
The space complexity is O(n), where 'n' is the length of the input boolean expression. The space complexity is primarily determined by the recursion stack, which grows with each recursive call. Since there can be at most 'n' recursive calls in the stack, the space complexity is linear with respect to the length of the input expression.
Approach 2: Memorization
In the context of the Boolean Evaluation problem, the memorization approach aims to improve upon the naive recursive solution by eliminating redundant computations of overlapping subproblems. The problem involves finding the number of ways a given boolean expression can be parenthesized to evaluate to 'TRUE.' The recursive solution without memorization suffers from exponential time complexity due to redundant computations of subproblems.
Algorithm
Step 1: Define a function findWays that takes the following parameters:
Step 1.1: exp: The boolean expression in the form of a string, st: Starting index for the current sub-expression, end: Ending index for the current sub-expression.
Step 1.2: isTrue: Boolean indicating whether the current sub-expression should evaluate to 'TRUE' or 'FALSE.', memo: Memoization table to store previously computed results for subproblems.
Step 2: If st is greater than end, return 0, indicating an invalid sub-expression.
Step 2.1: If st is equal to end: If isTrue is true, return 1 if the current element is 'T'; otherwise, return 0. If isTrue is false, return 1 if the current element is 'F'; otherwise, return 0.
Step 3: Check if the result for the current sub-expression is already memorized in the memo table.
Step 3.1: If the memorized result exists (i.e., memo[st][end][isTrue ? 1 : 0] != -1), return the memorized result.
Step 4: Initialize a variable ans to 0 to accumulate the result. Iterate over all possible positions k for operators within the current sub-expression.
Step 5: For each operator position k, recursively compute the number of ways for left and right sub-expressions to evaluate to 'TRUE' and 'FALSE' separately, considering all possible combinations of operators and operands.
Step 6: Combine the results based on the operator at position k and the value of isTrue.
Step 7: After computing the result for the current sub-expression, store the result in the memo table at the corresponding indices (memo[st][end][isTrue ? 1 : 0]). Return the result computed for the current sub-expression.
Step 8: In the main method initialize the boolean expression string and create a memorization table of appropriate size initialized with -1 values.
Step 9: Call the findWays function with the boolean expression, starting index 0, ending index equal to the length of the expression minus 1, a boolean indicating evaluation to 'TRUE', and the memorization table. Print the result obtained from the function call.
Filename: BooleanExpressionEvaluationMemoization.java
import java.util.Arrays;
public class BooleanExpressionEvaluationMemoization {
public static int findWays(String exp, int st, int end, boolean isTrue, int[][][] memo) {
// Base cases
if (st > end) {
return 0;
}
if (st == end) {
if (isTrue) {
return exp.charAt(st) == 'T' ? 1 : 0;
} else {
return exp.charAt(st) == 'F' ? 1 : 0;
}
}
// Check if result is memoized
if (memo[st][end][isTrue ? 1 : 0] != -1) {
return memo[st][end][isTrue ? 1 : 0];
}
// Recursive calls
int ans = 0;
for (int k = st + 1; k <= end - 1; k += 2) {
int leftTrue = findWays(exp, st, k - 1, true, memo);
int leftFalse = findWays(exp, st, k - 1, false, memo);
int rightTrue = findWays(exp, k + 1, end, true, memo);
int rightFalse = findWays(exp, k + 1, end, false, memo);
// Combine results based on operator and isTrue
if (exp.charAt(k) == '&') {
if (isTrue) {
ans += leftTrue * rightTrue;
} else {
ans += leftTrue * rightFalse + leftFalse * rightTrue + leftFalse * rightFalse;
}
} else if (exp.charAt(k) == '|') {
if (isTrue) {
ans += leftTrue * rightTrue + leftTrue * rightFalse + leftFalse * rightTrue;
} else {
ans += leftFalse * rightFalse;
}
} else if (exp.charAt(k) == '^') {
if (isTrue) {
ans += leftTrue * rightFalse + leftFalse * rightTrue;
} else {
ans += leftTrue * rightTrue + leftFalse * rightFalse;
}
}
}
// Memoize the result
memo[st][end][isTrue ? 1 : 0] = ans;
return ans;
}
public static void main(String[] args) {
String expression = "T|F&T^F";
int[][][] memo = new int[expression.length()][expression.length()][2];
for (int[][] array2D : memo) {
for (int[] array1D : array2D) {
Arrays.fill(array1D, -1);
}
}
int result = findWays(expression, 0, expression.length() - 1, true, memo);
System.out.println("Number of ways the expression can be parenthesized to evaluate to TRUE: " + result);
}
}
Output:
Number of ways the expression can be parenthesized to evaluate to TRUE: 5
Time Complexity
The time complexity of the algorithm is O(n^3), where 'n' is the length of the input boolean expression. This complexity arises from the nested loops and recursive calls within the findWays function. In each recursive call, there is a nested loop that iterates over all possible positions of operators within the current sub-expression.
Space Complexity
The space complexity of the algorithm is O(n^3), where 'n' is the length of the input boolean expression. The memoization table memo is a 3-D array of size [n][n][2], where each cell stores an integer value representing the number of ways a sub-expression can evaluate to 'TRUE' or 'FALSE.'
Approach 3: Bottom-Up Dynamic Programming
The Bottom-Up Dynamic Programming approach described for the Boolean Expression Evaluation problem offers a more efficient solution by systematically computing the number of ways to parenthesize the expression to evaluate to 'TRUE' for increasing sub-expression lengths.
Algorithm
Step 1: Initialize a 3-D dynamic programming (DP) table, dp, to store the number of ways expressions of different lengths and truth values can be parenthesized to evaluate to 'TRUE' or 'FALSE'.
Step 2: The table dp[i][j][0] represents the number of ways the expression from index 'i' to index 'j' evaluates to 'FALSE'.
Step 3: The table dp[i][j][1] represents the number of ways the expression from index 'i' to index 'j' evaluates to 'TRUE'. Both values are initialized to 0.
Step 4: The algorithm iterates over the expression string for increasing sub-expression lengths ('gap') and indices ('j' and 'k'), computing the number of ways each sub-expression can be parenthesized to evaluate to 'TRUE' or 'FALSE'.
Step 5: At each iteration, the algorithm computes the number of ways the left and right sub-expressions evaluate to 'TRUE' or 'FALSE' and combines them based on the operator at position 'k + 1'.
Step 6: The updates to the DP table are made iteratively, bottom-up, from smaller sub-expressions to larger ones, ensuring that all subproblems are solved before computing solutions for larger sub-expressions.
Step 7: After completing the iterations, the final result is stored in dp[0][n - 1][1], representing the number of ways the entire expression can be parenthesized to evaluate to 'TRUE'.
Step 8: The algorithm returns the value stored in dp[0][n - 1][1], providing the total number of ways the expression can be parenthesized to evaluate to 'TRUE'.
Filename: BooleanExpressionEvaluationBottomUp.java
public class BooleanExpressionEvaluationBottomUp {
public static int evaluateBooleanExpression(String exp) {
int n = exp.length();
int[][][] dp = new int[n][n][2];
// Initialize dp table
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dp[i][j][0] = 0; // Initialize number of ways for FALSE
dp[i][j][1] = 0; // Initialize number of ways for TRUE
}
}
// Base cases (single character expressions)
for (int i = 0; i < n; i += 2) {
if (exp.charAt(i) == 'T') {
dp[i][i][1] = 1; // 'T' evaluates to TRUE
} else {
dp[i][i][0] = 1; // 'F' evaluates to FALSE
}
}
// Bottom-up DP
for (int gap = 2; gap < n; gap += 2) {
for (int j = 0; j < n - gap; j += 2) {
int end = j + gap;
for (int k = j; k < end; k += 2) {
int leftTrue = dp[j][k][1];
int leftFalse = dp[j][k][0];
int rightTrue = dp[k + 2][end][1];
int rightFalse = dp[k + 2][end][0];
// Update dp table based on operator at k + 1
if (exp.charAt(k + 1) == '|') {
dp[j][end][1] += leftTrue * rightTrue + leftTrue * rightFalse + leftFalse * rightTrue;
dp[j][end][0] += leftFalse * rightFalse;
} else if (exp.charAt(k + 1) == '&') {
dp[j][end][1] += leftTrue * rightTrue;
dp[j][end][0] += leftTrue * rightFalse + leftFalse * rightTrue + leftFalse * rightFalse;
} else if (exp.charAt(k + 1) == '^') {
dp[j][end][1] += leftTrue * rightFalse + leftFalse * rightTrue;
dp[j][end][0] += leftTrue * rightTrue + leftFalse * rightFalse;
}
}
}
}
return dp[0][n - 1][1]; // Return the number of ways to evaluate the entire expression to TRUE
}
public static void main(String[] args) {
String expression = "T|F&T^F";
int result = evaluateBooleanExpression(expression);
System.out.println("Number of ways the expression can be parenthesized to evaluate to TRUE: " + result);
}
}
Output:
Number of ways the expression can be parenthesized to evaluate to TRUE: 5
Time Complexity
The time complexity of the algorithm is O(n^3), where 'n' is the length of the input boolean expression 'exp'. The algorithm iterates over all possible sub-expression lengths ('gap') and indices ('j' and 'k'), leading to O(n^3) iterations.
Space Complexity
The space complexity of the algorithm is also O(n^3). The algorithm utilizes a 3-D DP table, dp, of size [n][n][2] to store the number of ways expressions of different lengths and truth values can be parenthesized to evaluate to 'TRUE' or 'FALSE'.