In this problem you are given a boolean expression with symbols 'T', 'F' and operators '&', '|', '^' where:

'T' represents True

'F' represents False

'&' represents boolean AND

'|' represents boolean OR

'^' represents boolean XOR.

This expression will be given in the form of two strings, string-1, will store the T(s) and F(s) and another one, s2 will store the operators. Size of string s2 will be one less than s1. And the expression will be represented by taking one character from each of the strings respectively.

All you have to do is find the number of ways in which the expression can be parenthesized so that the value of expression evaluates to true.

For example:

Sample Input:

TFT
^&

Sample Output: 2

HOW?

The corresponding expression for the given input will be (T^ F & T).

And there are two ways in which this expression can be parenthesized so that the value of expression evaluates to true.

For more clarity of the question, watch this part of the video.

Approach:

Moving On:

Before moving any further it is important for you to know about the behavior of operators very well.

Expressions can be of 3 types:

((left) & (right))

((left) | (right))

((left) ^ (right))

Let say that the left can yield ltc (left true count) number of true and lfc (left false count) number of false. And right can yield rtc (right true count) number of true and rfc (right false count) number of false.

Type-1: ((left) & (right)); If the operator is '&' then the expression can be true for (ltc * rtc) number of times and it can be false for ((ltc * rfc) + (lfc * rfc) +(lfc * rtc)) number of times.

Type-2: ((left) | (right)); if the operator is '|' then the expression can be true for ((ltc * rtc) + (ltc * rfc) +(lfc * rtc)) number of times and it can be false for (lfc * rfc) number of times.

Type-3: ((left) ^ (right)); if the operator is '^' then the expression can be true for ((ltc * rfc) + (lfc * rtc)) number of times and it can be false for ((ltc * rtc) + (lfc * rfc)) number of times.
For more clarity of the above table watch this part of the lecture video.

In order to solve this problem we will use the Gap Strategy of dynamic programming.

In this strategy we use a 2D array of n x n and then we assign some meaning to the cells of the 2D array.

After that we fill the matrix diagonally, moving from smaller problems to the bigger problem.

Let's try to build the solution using an example where String-1 = TFTF and String-2 = &|^.

In this problem we need two 2d arrays dpt[][] (dp storing count of tue) and dpf[][] (dp storing count of false) of (n x n), where n is the length of string-1.

Trivial case for these matrices would be the main diagonal where the cells represent the scenario where there is only one character contributing to the expression which is either a T or F.

So in dpt we will store 1 corresponding to T(s) and 0 corresponding to F(s) in the main diagonal (when gap = 0) because for boolean value T, there is one way we can parenthesize T such that it evaluates True whereas for F, there is no way we can parenthesize it such that it evaluates True.

However in dpf we will store 1 corresponding to F(s) and 0 corresponding to T(s) in the main diagonal (when gap = 0) because for boolean value F, there is one way we can parenthesize F such that it evaluates False whereas for T, there is no way we can parenthesize it such that it evaluates False.

Now to fill the rest of the diagonals of both the matrices we need to use the formulas corresponding to the operator.

However in the next diagonal we can also fill the matrices directly as there is only one operator. So we can use either way to fill it.

First cell of this diagonal is for (T&F) which results in true in zero ways and false in only one way so we store 0 corresponding to this cell in dpt and 1 in dpf.

Second cell for this diagonal is for (F|T) which results in true in only one way and false in zero way, so we store 1 corresponding to this cell in dpt and 0 in dpf.

Last cell corresponds to (T^F) which gives true in one way and false in zero ways, so we store 1 corresponding to this cell in dpt and 0 in dpf.
For more clarity of the above part watch this part of the lecture video.

Let's jump to the next diagonal (at gap = 2).

In this diagonal, first cell corresponds to (T&F|T). This can split in 2 ways ((T&F) | (T)) and ((T) & (F|T)).

If you observe then we have the count corresponding to all the sub-expressions of these 2 expressions. So we can finally use the formulas of type (left | right) and (left & right) for calculating the result rather than doing it manually. Refer the below diagram for understanding of the math of the formulas.

In the diagram, we have portioned the expression at the operators to consider all possibilities.

In (T&F|T), first we partition the expression at '&' and then at '|'.

Then for each expression we calculate the count of true and false for using the respective formula. For more clarity of the above part watch this part of the lecture video.

Similarly we can fill the next cell of this diagonal which correspond to the expression (F|T^F), in both the matrices using the formulas and the previously filled matrices by partitioning the expression at the operators '|' and then '^' for exploring all possibilities. For more clarity of the above part watch this part of the lecture video.

Finally we move to the last diagonal with only one cell which will store the final answer of this.

Complete and final expression for this cell is (T&F|T^F). We can partition this expression at three points. Yes, at all three operators like ((T) & (F|T^F)), ((T&F) | (T^F)) and ((T&F|T) ^ (F)). Now each of these expressions can use the formulas of type-1, 2 and 3 respectively for calculating the count of true and false.
For better mathematical clarification of the above part watch this part of the lecture video and refer to the above diagram.

Let's try to code this!

First of all, we need to define two 2D arrays of n x n (where n is the length of the string-1) to store the count of true and false; let's call them 't' and 'f'. Then to use the gap strategy we need to run a for loop starting from 0 until the gap is less than n. And then we need to initialize two more variables si (starting index) and ei (ending index).

Now inside this for loop, we will run a while loop to fill both the 2D arrays 't' and 'f' diagonally.

On entering the while loop; first of all we handle the trivial case (base case). If the gap is zero then we check if the character at si in string-1 is a 'T', if yes then we put 1 at t[si][ei], if not then we put 0 at t[si][ei].

After that we check if the character at si in string-1 is a 'F', if yes then we put 1 at f[si][ei], if not then we put 0 at f[si][ei].

And if the gap is some other value than 0 then we handle the cases using the formulas and the values stored in 't' and 'f' so far.

For every sub-expression it is important that we consider all the cases by partitioning the expression at each operator; to do so we use another for loop initialized with cp to si until cp is less than ei.

Then we capture the character present at cp in string-2 (operator at which partition is done).

After that we check whether the operator is '&' or '|' or '^'. Then we follow the respective condition's further steps.

In further steps we have coded the formulas (same that we have analyzed already) for calculating the count of true and false for each of the two 2D arrays.

For more clarity of the code, watch part of the video.

import java.io.*;
import java.util.*;
public class Main {
public static int solution(String str1, String str2) {
int n = str1.length();
int[][] t = new int[n][n];
int[][] f = new int[n][n];
for (int gap = 0; gap < n; gap++) {
int si = 0, ei = gap;
while (ei < n) {
if (gap == 0) {
t[si][ei] = str1.charAt(si) == 'T' ? 1 : 0;
f[si][ei] = str1.charAt(si) == 'F' ? 1 : 0;
} else {
for (int cp = si; cp < ei; cp++) {
char sign = str2.charAt(cp);
if (sign == '&') {
t[si][ei] += t[si][cp] * t[cp + 1][ei];
f[si][ei] += ((t[si][cp] * f[cp + 1][ei]) + (f[si][cp] * t[cp + 1][ei])
+ (f[si][cp] * f[cp + 1][ei]));
}
if (sign == '|') {
t[si][ei] += ((t[si][cp] * t[cp + 1][ei]) + (t[si][cp] * f[cp + 1][ei])
+ (f[si][cp] * t[cp + 1][ei]));
f[si][ei] += ((f[si][cp]) * (f[cp + 1][ei]));
}
if (sign == '^') {
t[si][ei] += ((t[si][cp] * f[cp + 1][ei]) + (f[si][cp] * t[cp + 1][ei]));
f[si][ei] += ((t[si][cp] * t[cp + 1][ei]) + (f[si][cp] * f[cp + 1][ei]));
}
}
}
si++;
ei++;
}
}
return (t[0][t[0].length - 1]);
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
String s1 = scn.next();
String s2 = scn.next();
System.out.println(solution(s1, s2));
}
}

java;
true";

Analysis

Time Complexity:

O(N^3)

Similar to what we see in the Matrix Chain Multiplication problem. Since the problem is quite similar to that one, the time complexity is also the same.

Space Complexity:

O(N^2)

Here we had used 2 2D Dp arrays one for storing the number of ways to parenthesize a sub-expression such that it results in true and the other for False.

We hope that this article was helpful. If somehow you are finding it difficult to understand this problem then we advise you to watch our video lecture of this problem.

Trust me it will just get easier to understand after you have watched the solution video.

You can contact us via our website. Doubts, suggestions and feedback are always welcomed.

It is also advised that you follow the sequence of modules and questions which is there on our website.

Keep practicing more and more problems daily. Meditate enough on each step of each problem.