Brute Force Intuition
The simple and brute force approach is to try to put brackets in all possible ways, then check how many different ways you can put brackets and how many of them result in true.
Basically, we’ll break down the ‘EXP’ into smaller expressions and see how many ways that smaller expression can return True and how many ways a smaller expression can return False. Then according to the operator, we can club these small answers to find out the number of expressions that result in true. It will become more clear as we proceed.
Algorithm
Let’s create a recursive function called ‘findWays()’ which will take 4 parameters ‘EXP’ as our given expression, ‘ST’ represents the starting point of sub-expression(smaller part), ‘END’ represents the ending point of sub-expression(smaller part), ‘IS_TRUE’ stores whether the sub-expression should be evaluated to true or false.
Base Conditions
- If ‘ST’ is greater than ‘END,’ then return False.
-
If ‘ST’ equals ‘END,’ it means there is only one character left in the ‘EXP’ then we will check for the following:
- If the value of ‘IS_TRUE’ is True, then we will check if the current element is true or not, i.e., ‘EXP[ST]’. If it is true, then we will return true else, we will return false.
- If the value of ‘IS TRUE’ is False, then we will return the opposite of what we have returned above, i.e., if ‘EXP[ST]' is false, we will return True else, we will return False.
Recursive calls
- We will create a new variable, ‘ANS’, which will store our final answer. We’ll initialize it to zero.
-
We will now loop over ‘EXP’ using variable ‘K’ in the range ‘ST' + 1 <= ‘K' <= ‘END' - 1 and do the following:
- We will create four variables: ‘LEFT_TRUE’, which will store the number of ways in which the expression to the left of ‘K' is true, ‘LEFT_FALSE’ will store the number of ways in which the expression to the left of ‘K' is false,‘RIGHT_TRUE’ will store the number of ways the expression to the right to ‘K' is true and finally ‘RIGHT_FALSE' will store the number of ways in which the expression to the right of ‘K' is true.
- We'll find these values by using the calling ‘findWays()’ function recursively in the following ways. ‘ST' will be ‘ST,' and ‘END' will be changed to ‘K' - 1 to make a call to the left part, and to reach the right part, we will change ‘ST' to ‘K' + 1 and ‘END' will remain ‘END’. Similarly, If we need to find the number of ways for true, set the value of ‘IS_TRUE' to True; otherwise, put it to False.
-
Now, depending on the value of ‘IS_TRUE' and the value of the current operator (‘EXP[K]'), there will be numerous combinations possible. For understanding one such case, Let us assume that ‘EXP[K]’ is | (‘OR’) and ‘IS_TRUE' = True, then using the following truth table of ‘OR’ we can calculate our answer.
- T | T = T
- F | T = T
- T | F = T
- F | F = F
- Thus, ‘ANS' = ‘LEFT_TRUE’ * ’RIGHT_FALSE' + ‘LEFT_FALSE' * ’RIGHT_TRUE'+ ‘LEFT_TRUE' * ’RIGHT_TRUE' + ’ANS’.Here we are adding only those cases which will result in true
- We can do the same for other possible combinations as well.
- Return the variable ‘ANS’ as it now contains our final answer.
Now let’s look at the code for the above algorithm.
Code
#include<iostream>
#include<vector>
#include<string>
using namespace std;
#define mod 1000000007
int findWays(string &exp, int i, int j, int isTrue) {
// Corner Cases.
if (i > j) {
return 0;
}
// If the length of expression is 1, we need to evaluate its value.
if (i == j) {
if (isTrue) {
return exp[i] == 'T' ? 1 : 0;
} else {
return exp[i] == 'F' ? 1 : 0;
}
}
long long int ans = 0;
for (int k = i + 1; k <= j - 1; k += 2) {
// The number of ways expression left to 'K' will be true.
long long int leftTrue = (findWays(exp, i, k - 1, 1)) % mod;
// The number of ways expression left to 'K' will be false.
long long int leftFalse = (findWays(exp, i, k - 1, 0)) % mod;
// The number of ways expression right to 'K' will be true.
long long int rightTrue = (findWays(exp, k + 1, j, 1)) % mod;
// The number of ways expression right to 'K' will be false.
long long int rightFalse = (findWays(exp, k + 1, j, 0)) % mod;
if (exp[k] == '|') {
// T | T = T, T | F = T, F | T = T , F | F = F.
if (isTrue) {
ans += leftTrue * rightTrue + leftTrue *
rightFalse + leftFalse * rightTrue;
ans = ans % mod;
} else {
ans += leftFalse * rightFalse;
ans = ans % mod;
}
}
else if (exp[k] == '&') {
// T & T = T, T & F = F, F & T = F , F | F = F.
if (isTrue) {
ans += leftTrue * rightTrue;
ans = ans % mod;
} else {
ans += leftTrue * rightFalse + leftFalse *
rightTrue + leftFalse * rightFalse;
ans = ans % mod;
}
}
else {
// T ^ T = F, T ^ F = T, F ^ T = T , F ^ F = F.
if (isTrue) {
ans += leftTrue * rightFalse + leftFalse *
rightTrue;
ans = ans % mod;
} else {
ans += leftTrue * rightTrue + leftFalse *
rightFalse;
ans = ans % mod;
}
}
}
return ans;
}
int evaluateExp(string & exp) {
int n = exp.length();
// We need to evaluate the whole expression for true.
return findWays(exp, 0, n - 1, 1);
}
int main() {
// Input String.
string s;
cin >> s;
// Calling function and printing the answer.
cout << evaluateExp(s) << endl;
}
Input
T^T^F
Output
0
Time Complexity
O(4 ^ N), Where ‘N’ is the length of the string.
At each step, we are making 4 calls and at that particular call, we are making 4 calls again thus, bringing the time complexity to O(4^N).
Space Complexity
O(4^ N), Where ‘N’ is the length of the string.
As this is the amount of space that the recursion stack will utilize to store 4 ^ N calls.
Memoization Intuition
Our previous approach was pretty simple and straightforward, but the time complexity was unacceptable. But if we closely look at the subproblems, we can clearly see that we are solving the same subproblem again and again. Thus by addressing the overlapping subproblems, we can improve our solution. As a result, keeping the same subproblems in a DP table will reduce the requirement to solve them repeatedly. This is also known as top-down dynamic programming.
Algorithm
We'll start by creating a 3-D DP array ‘MEMO[N][N][2]’ where ‘N’ is the length of the string ‘EXP.’ Initially, all states are unexplored, we will initialize the table to -1.
MEMO[i][j][k] = -1 indicates that the current state is not exploredwhereas, ‘MEMO[i][j][0]’ stores the number of times expression(i, j) is false, while ‘MEMO[i][j][1]’ stores the number of times expression(i, j) is True. Here ‘i’ is the starting position of the ‘EXP’ while ‘j’ is the ending position on ‘EXP’.
Thus, there will be two changes in the recursive approach:
- In the base case, we will first check if the value of ‘MEMO' is -1, and if it is not, which means the answer to this subproblem has already been calculated, we will simply return the value contained in the ‘MEMO’ corresponding to that particular state.
- If the value in ‘MEMO’ is -1, it indicates that the answer to that particular state does not exist. Therefore, we will store the value of ‘ANS’ in ‘MEMO' before returning it.
Now let’s look at the code for the above approach.
Code
#include<iostream>
#include<vector>
#include<string>
using namespace std;
#define mod 1000000007
vector<vector<vector<long long int >>> memo;
int findWays(string &exp, int i, int j, int isTrue) {
// Corner Cases.
if (i > j) {
return 0;
}
// If the length of expression is 1, we need to evaluate its value.
if (i == j) {
if (isTrue) {
return exp[i] == 'T' ? 1 : 0;
} else {
return exp[i] == 'F' ? 1 : 0;
}
}
if (memo[i][j][isTrue] != -1) {
return memo[i][j][isTrue];
}
long long int ans = 0;
for (int k = i + 1; k <= j - 1; k += 2) {
if (memo[i][k - 1][1] == -1) {
memo[i][k - 1][1] = (findWays(exp, i, k - 1, 1)) % mod;
}
if (memo[i][k - 1][0] == -1) {
memo[i][k - 1][0] = (findWays(exp, i, k - 1, 0)) % mod;
}
if (memo[k + 1][j][1] == -1) {
memo[k + 1][j][1] = (findWays(exp, k + 1, j, 1)) % mod;
}
if (memo[k + 1][j][0] == -1) {
memo[k + 1][j][0] = (findWays(exp, k + 1, j, 0)) % mod;
}
// The number of ways expression left to 'K' will be true.
long long int leftTrue = memo[i][k - 1][1];
// The number of ways expression left to 'K' will be false.
long long int leftFalse = memo[i][k - 1][0];
// The number of ways expression right to 'K' will be true.
long long int rightTrue = memo[k + 1][j][1];
// The number of ways expression right to 'K' will be false.
long long int rightFalse = memo[k + 1][j][0];
if (exp[k] == '|') {
// T | T = T, T | F = T, F | T = T, F | F = F.
if (isTrue) {
ans += leftTrue * rightTrue + leftTrue *
rightFalse + leftFalse * rightTrue;
ans = ans % mod;
} else {
ans += leftFalse * rightFalse;
ans = ans % mod;
}
}
else if (exp[k] == '&') {
// T & T = T, T & F = F, F & T = F, F | F = F.
if (isTrue) {
ans += leftTrue * rightTrue;
ans = ans % mod;
} else {
ans += leftTrue * rightFalse + leftFalse *
rightTrue + leftFalse * rightFalse;
ans = ans % mod;
}
}
else {
// T ^ T = F, T ^ F = T, F ^ T = T, F ^ F = F.
if (isTrue) {
ans += leftTrue * rightFalse + leftFalse * rightTrue;
ans = ans % mod;
} else {
ans += leftTrue * rightTrue + leftFalse * rightFalse;
ans = ans % mod;
}
}
}
return memo[i][j][isTrue] = ans;
}
int evaluateExp(string &exp) {
int n = exp.length();
memo = vector<vector<vector<long long int>>> (n, vector<vector<long long int>>(n, vector<long long int>(2, -1)));
// We need to evaluate the whole expression for true.
return findWays(exp, 0, n - 1, 1);
}
int main() {
// Input String.
string s;
cin >> s;
// Calling function and printing the answer.
cout << evaluateExp(s) << endl;
}
Input
T^T^F
Output
Input
Time Complexity
O(N ^ 3), where ‘N’ is the length of the given string.
In the worst-case scenario, after performing N ^ 3 calls, all of the states will be investigated, and we will be able to use the ‘MEMO’ result to find our final answer.
Space Complexity
O(N^2), where ‘N’ is the length of the given string.
As a 3-D array of size N * N * 2 is being used.
Bottom-Up Intuition
In the bottom-up approach, we'll start by creating a 3-D array called 'DP[N][N][2]’ and initialize it to 0, where ‘N’ is the length of the string 'EXP.' The number of ways expression(i, j) will be false will be stored in DP[i][j][0], whereas the number of ways expression(i, j) will be True will be stored in DP[i][j][1]. Here ‘i’ is the starting position of the ‘EXP’ while ‘j’ is the ending position on ‘EXP’.
Algorithm
- Firstly we will fill the diagonals by using a variable ‘i’ we can check if the ‘EXP[i]’ is true then the diagonal entry for the true one will be true otherwise for the false one it will be true.
-
We’ll use the variable ‘GAP’ to iterate over the string ‘EXP' in the range of 2 <= ‘GAP'< N times and will keep increasing ‘GAP' by 2 each time, and do the following:
-
We’ll use the variable ‘j’ to iterate through the string ‘EXP' in the range of 2 < = ‘j' < N, and will keep increasing ‘j' by 2 each time, and do the following:
-
We’ll use the variable ‘k’ to iterate through the string ‘EXP' in the range of 2 < = ‘k’ < N, and will keep increasing ‘k' by 2 each time, and assign the following values to the following variables:
- 'LEFT_TRUE’ = DP[j][k][1]
- 'LEFT_FALSE’ = DP[j][k][0]
- 'RIGHT_TRUE’ = DP[k + 2][j + GAP][1]
- 'RIGHT_FALSE’ = DP[k + 2][j + GAP[0]]
-
Then we will check which operator is there at ‘K’ + 1 place. For example, let’s say if it is OR(‘|’) then we will assign values in the following way:
- DP[j][j + GAP][1] = 'LEFT_TRUE' * ‘RIGHT_FALSE’ + 'LEFT _FALSE' * ‘RIGHT_TRUE’ + 'LEFT TRUE' * 'RIGHT TRUE' + DP[j][j + GAP][1].
- DP[j][j + GAP][0] += 'RIGHT FALSE' * 'LEFT FALSE' + DP[j][j + GAP][0]. We can solve for other operators in the same way.
3. Return DP[0][N - 1][1] as our final answer.
Below is the implementation of the above approach.
Code
#include<iostream>
#include<vector>
#include<string>
using namespace std;
#define mod 1000000007
int evaluateExp(string &exp) {
int n = exp.length();
// We need to evaluate the whole expression for true.
vector<vector<vector<long long int>>> dp(n, vector< vector<long long int>> (n, vector<long long int> (2, 0)));
// Filling the diagonal entries.
for (int i = 0; i < n; i++) {
if (exp[i] == 'T') {
dp[i][i][1] = 1;
} else if (exp[i] == 'F') {
dp[i][i][0] = 1;
}
}
// Filling the dp array.
for (int gap = 2; gap < n; gap += 2) {
for (int j = 0; j + gap < n; j += 2) {
for (int k = j; k < j + gap; k += 2) {
if(exp[k + 1] == '|') {
// T | T = T, T | F = T, F | T = T, F | F = F.
dp[j][j + gap][1] += ((dp[j][k][0] * dp[k + 2][j +
gap][1]) + (dp[j][k][1] * dp[k + 2][j + gap][0]) +
(dp[j][k][1] * dp[k + 2][j + gap][1])) % mod;
dp[j][j + gap][1] %= mod;
dp[j][j + gap][0] += ((dp[j][k][0] * dp[k + 2][j +
gap][0])) % mod;
dp[j][j + gap][0] %= mod;
}
if(exp[k + 1] == '&') {
// T & T = T, T & F = F, F & T = F , F | F = F.
dp[j][j + gap][1] += ((dp[j][k][1] * dp[k + 2][j +
gap][1])) % mod;
dp[j][j + gap][1] %= mod;
dp[j][j + gap][0] += ((dp[j][k][0] * dp[k + 2][j +
gap][1]) + (dp[j][k][1] * dp[k + 2][j + gap][0]) +
(dp[j][k][0] * dp[k + 2][j + gap][0])) % mod;
dp[j][j + gap][0] %= mod;
}
if(exp[k + 1] == '^') {
// T ^ T = F, T ^ F = T, F ^ T = T, F ^ F = F
dp[j][j + gap][1] += ((dp[j][k][1] * dp[k + 2][j +
gap][0]) + (dp[j][k][0] * dp[k + 2][j + gap][1])) %
mod;
dp[j][j + gap][1] %= mod;
dp[j][j + gap][0] += ((dp[j][k][0] * dp[k + 2][j +
gap][0]) + (dp[j][k][1] * dp[k + 2][j + gap][1])) %
mod;
dp[j][j + gap][0] %= mod;
}
}
}
}
return dp[0][n - 1][1];
}
int main() {
// Input String.
string s;
cin >> s;
// Calling function and printing the answer.
cout << evaluateExp(s) << endl;
}
Input
T^T^F
Output
Input
Time Complexity
O(N ^ 3), where ‘N’ is the length of the given string.
As we are iterating over a 3D array and using 3 nested loops.
Space complexity
O(N ^ 2), where ‘N’ is the length of the given string.
As a 3-D array of size N * N * 2 is being used.
Check out this problem - Longest String Chain
Key Takeaways
We saw how we built the solution from recursion to memoization and finally to DP for the problem evaluate expression to true. Now, Understanding a new concept always makes one excited, and this excitement leads to learning more concepts. We’ll make that simple for you, head over to our practice platform Coding Ninjas Studio to practice top problems like evaluate expression to true, attempt mock tests, read interview experiences, and many more. Till then, Happy Coding!
38+ registered 