Given a boolean expression with the following symbols.
Symbols
'T' ---> true
'F' ---> false
And following operators filled between symbols
Operators
& ---> boolean AND
| ---> boolean OR
^ ---> boolean XOR
Count the number of ways we can parenthesize the expression so that the value of expression evaluates to true.
Let the input be in form of two arrays one contains the symbols (T and F) in order and the other contains operators (&, | and ^}
Examples:
Input: symbol[] = {T, F, T}
operator[] = {^, &}
Output: 2
The given expression is "T ^ F & T", it evaluates true
in two ways "((T ^ F) & T)" and "(T ^ (F & T))"
Input: symbol[] = {T, F, F}
operator[] = {^, |}
Output: 2
The given expression is "T ^ F | F", it evaluates true
in two ways "( (T ^ F) | F )" and "( T ^ (F | F) )".
Input: symbol[] = {T, T, F, T}
operator[] = {|, &, ^}
Output: 4
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)).
Solution:
Let T(i, j) represent the number of ways to parenthesize the symbols between i and j (both inclusive) such that the subexpression between i and j evaluates to true.
![T(i,j)=\sum_{k=i}^{j-1}\begin{Bmatrix} T(i,k)*T(k+1,j) & if&operator&[k]is '\&'\\ Total(i,k)*Total(k+1,j)-F(i,k)*F(k+1,j) &if&operator&[k]&is'|' \\ T(i,k)*F(k+1,j)+F(i,k)*T(k+1,j) &if&operator&[k]&is '\oplus' \end{Bmatrix} Total(i,j)= T(i,j)+F(i,j)](https://geeksforgeeks.org/wp-content/uploads/2023/10/neveropen_quicklatex.com-41c0ab3479c8afbba9cef6f6baa89008_l3.png "Rendered by QuickLaTeX.com")
Let F(i, j) represent the number of ways to parenthesize the symbols between i and j (inclusive) such that the subexpression between i and j evaluates to false.![F(i,j)=\sum_{k=i}^{j-1} \begin{Bmatrix} Total(i,k)*Total(k+1,j)-T(i,k)*T(k+1,j) & if&operator[k]&is'\&'\\ F(i,k)*F(k+1,j) &if&operator[k] &is'|' \\ T(i,k)*T(k+1,j)+F(i,k)*F(k+1,j) &if&operator[k]&is'\oplus' \end{Bmatrix} Total(i,j)=T(i,j)+F(i,j)](https://geeksforgeeks.org/wp-content/uploads/2023/10/dominic_rubhabha_quicklatex.com-e7d0c265759028e0a6398ce7d767322d_l3-1.png "Rendered by QuickLaTeX.com")
Base Cases:
T(i, i) = 1 if symbol[i] = 'T' T(i, i) = 0 if symbol[i] = 'F' F(i, i) = 1 if symbol[i] = 'F' F(i, i) = 0 if symbol[i] = 'T'
If we draw the recursion tree of the above recursive solution, we can observe that it has many overlapping subproblems. Like other dynamic programming problems, it can be solved by filling a table in a bottom-up manner. Following is the implementation of a dynamic programming solution.
C++
#include <cstring>#include <iostream>using namespace std;// Returns count of all possible// parenthesizations that lead// to result true for a boolean // expression with symbols like// true and false and operators // like &, | and ^ filled// between symbolsint countParenth(char symb[], char oper[], int n){ int F[n][n], T[n][n]; // Fill diagonal entries first // All diagonal entries in // T[i][i] are 1 if symbol[i] // is T (true). Similarly, // all F[i][i] entries are 1 if // symbol[i] is F (False) for (int i = 0; i < n; i++) { F[i][i] = (symb[i] == 'F') ? 1 : 0; T[i][i] = (symb[i] == 'T') ? 1 : 0; } // Now fill T[i][i+1], // T[i][i+2], T[i][i+3]... in order // And F[i][i+1], F[i][i+2], // F[i][i+3]... in order for (int gap = 1; gap < n; ++gap) { for (int i = 0, j = gap; j < n; ++i, ++j) { T[i][j] = F[i][j] = 0; for (int g = 0; g < gap; g++) { // Find place of parenthesization using // current value of gap int k = i + g; // Store Total[i][k] // and Total[k+1][j] int tik = T[i][k] + F[i][k]; int tkj = T[k + 1][j] + F[k + 1][j]; // Follow the recursive formulas // according // to the current operator if (oper[k] == '&') { T[i][j] += T[i][k] * T[k + 1][j]; F[i][j] += (tik * tkj - T[i][k] * T[k + 1][j]); } if (oper[k] == '|') { F[i][j] += F[i][k] * F[k + 1][j]; T[i][j] += (tik * tkj - F[i][k] * F[k + 1][j]); } if (oper[k] == '^') { T[i][j] += F[i][k] * T[k + 1][j] + T[i][k] * F[k + 1][j]; F[i][j] += T[i][k] * T[k + 1][j] + F[i][k] * F[k + 1][j]; } } } } return T[0][n - 1];}// Driver codeint main(){ char symbols[] = "TTFT"; char operators[] = "|&^"; int n = strlen(symbols); // There are 4 ways // ((T|T)&(F^T)), (T|(T&(F^T))), (((T|T)&F)^T) and // (T|((T&F)^T)) cout << countParenth(symbols, operators, n); return 0;} |
Java
import java.io.*;import java.util.*;class GFG { // Returns count of all possible // parenthesizations that lead to // result true for a boolean // expression with symbols like true // and false and operators like &, | // and ^ filled between symbols static int countParenth(char symb[], char oper[], int n) { int F[][] = new int[n][n]; int T[][] = new int[n][n]; // Fill diagonal entries first // All diagonal entries in T[i][i] // are 1 if symbol[i] is T (true). // Similarly, all F[i][i] entries // are 1 if symbol[i] is F (False) for (int i = 0; i < n; i++) { F[i][i] = (symb[i] == 'F') ? 1 : 0; T[i][i] = (symb[i] == 'T') ? 1 : 0; } // Now fill T[i][i+1], T[i][i+2], // T[i][i+3]... in order And F[i][i+1], // F[i][i+2], F[i][i+3]... in order for (int gap = 1; gap < n; ++gap) { for (int i = 0, j = gap; j < n; ++i, ++j) { T[i][j] = F[i][j] = 0; for (int g = 0; g < gap; g++) { // Find place of parenthesization // using current value of gap int k = i + g; // Store Total[i][k] // and Total[k+1][j] int tik = T[i][k] + F[i][k]; int tkj = T[k + 1][j] + F[k + 1][j]; // Follow the recursive formulas // according to the current operator if (oper[k] == '&') { T[i][j] += T[i][k] * T[k + 1][j]; F[i][j] += (tik * tkj - T[i][k] * T[k + 1][j]); } if (oper[k] == '|') { F[i][j] += F[i][k] * F[k + 1][j]; T[i][j] += (tik * tkj - F[i][k] * F[k + 1][j]); } if (oper[k] == '^') { T[i][j] += F[i][k] * T[k + 1][j] + T[i][k] * F[k + 1][j]; F[i][j] += T[i][k] * T[k + 1][j] + F[i][k] * F[k + 1][j]; } } } } return T[0][n - 1]; } // Driver code public static void main(String[] args) { char symbols[] = "TTFT".toCharArray(); char operators[] = "|&^".toCharArray(); int n = symbols.length; // There are 4 ways // ((T|T)&(F^T)), (T|(T&(F^T))), // (((T|T)&F)^T) and (T|((T&F)^T)) System.out.println( countParenth(symbols, operators, n)); }}// This code has been contributed// by 29AjayKumar |
Python
# Returns count of all possible# parenthesizations that lead to# result true for a boolean# expression with symbols like# true and false and operators# like &, | and ^ filled between symbolsdef countParenth(symb, oper, n): F = [[0 for i in range(n + 1)] for i in range(n + 1)] T = [[0 for i in range(n + 1)] for i in range(n + 1)] # Fill diagonal entries first # All diagonal entries in # T[i][i] are 1 if symbol[i] # is T (true). Similarly, all # F[i][i] entries are 1 if # symbol[i] is F (False) for i in range(n): if symb[i] == 'F': F[i][i] = 1 else: F[i][i] = 0 if symb[i] == 'T': T[i][i] = 1 else: T[i][i] = 0 # Now fill T[i][i+1], T[i][i+2], # T[i][i+3]... in order And # F[i][i+1], F[i][i+2], # F[i][i+3]... in order for gap in range(1, n): i = 0 for j in range(gap, n): T[i][j] = F[i][j] = 0 for g in range(gap): # Find place of parenthesization # using current value of gap k = i + g # Store Total[i][k] and Total[k+1][j] tik = T[i][k] + F[i][k] tkj = T[k + 1][j] + F[k + 1][j] # Follow the recursive formulas # according to the current operator if oper[k] == '&': T[i][j] += T[i][k] * T[k + 1][j] F[i][j] += (tik * tkj - T[i][k] * T[k + 1][j]) if oper[k] == '|': F[i][j] += F[i][k] * F[k + 1][j] T[i][j] += (tik * tkj - F[i][k] * F[k + 1][j]) if oper[k] == '^': T[i][j] += (F[i][k] * T[k + 1][j] + T[i][k] * F[k + 1][j]) F[i][j] += (T[i][k] * T[k + 1][j] + F[i][k] * F[k + 1][j]) i += 1 return T[0][n - 1]# Driver Codesymbols = "TTFT"operators = "|&^"n = len(symbols)# There are 4 ways# ((T|T)&(F^T)), (T|(T&(F^T))),# (((T|T)&F)^T) and (T|((T&F)^T))print(countParenth(symbols, operators, n))# This code is contributed by# sahil shelangia |
C#
// C# program of above approachusing System;class GFG { // Returns count of all possible // parenthesizations that lead to // result true for a boolean // expression with symbols like true // and false and operators like &, | // and ^ filled between symbols static int countParenth(char []symb, char []oper, int n) { int [,]F = new int[n, n]; int [,]T = new int[n, n]; // Fill diagonal entries first // All diagonal entries in T[i,i] // are 1 if symbol[i] is T (true). // Similarly, all F[i,i] entries // are 1 if symbol[i] is F (False) for (int i = 0; i < n; i++) { F[i,i] = (symb[i] == 'F') ? 1 : 0; T[i,i] = (symb[i] == 'T') ? 1 : 0; } // Now fill T[i,i+1], T[i,i+2], // T[i,i+3]... in order And F[i,i+1], // F[i,i+2], F[i,i+3]... in order for (int gap = 1; gap < n; ++gap) { for (int i = 0, j = gap; j < n; ++i, ++j) { T[i, j] = F[i, j] = 0; for (int g = 0; g < gap; g++) { // Find place of parenthesization // using current value of gap int k = i + g; // Store Total[i,k] and Total[k+1,j] int tik = T[i, k] + F[i, k]; int tkj = T[k + 1, j] + F[k + 1, j]; // Follow the recursive formulas // according to the current operator if (oper[k] == '&') { T[i, j] += T[i, k] * T[k + 1, j]; F[i, j] += (tik * tkj - T[i, k] * T[k + 1, j]); } if (oper[k] == '|') { F[i,j] += F[i, k] * F[k + 1, j]; T[i,j] += (tik * tkj - F[i, k] * F[k + 1, j]); } if (oper[k] == '^') { T[i, j] += F[i, k] * T[k + 1, j] + T[i, k] * F[k + 1, j]; F[i, j] += T[i, k] * T[k + 1, j] + F[i, k] * F[k + 1, j]; } } } } return T[0,n - 1]; } // Driver code public static void Main() { char []symbols = "TTFT".ToCharArray(); char []operators = "|&^".ToCharArray(); int n = symbols.Length; // There are 4 ways // ((T|T)&(F^T)), (T|(T&(F^T))), // (((T|T)&F)^T) and (T|((T&F)^T)) Console.WriteLine(countParenth(symbols, operators, n)); }}/* This code contributed by PrinciRaj1992 */ |
Javascript
<script> // Returns count of all possible // parenthesizations that lead to // result true for a boolean // expression with symbols like true // and false and operators like &, | // and ^ filled between symbols function countParenth(symb, oper, n) { let F = new Array(n); let T = new Array(n); for (let i = 0; i < n; i++) { F[i] = new Array(n); T[i] = new Array(n); for(let j = 0; j < n; j++) { F[i][j] = 0; T[i][j] = 0; } } // Fill diagonal entries first // All diagonal entries in T[i][i] // are 1 if symbol[i] is T (true). // Similarly, all F[i][i] entries // are 1 if symbol[i] is F (False) for (let i = 0; i < n; i++) { F[i][i] = (symb[i] == 'F') ? 1 : 0; T[i][i] = (symb[i] == 'T') ? 1 : 0; } // Now fill T[i][i+1], T[i][i+2], // T[i][i+3]... in order And F[i][i+1], // F[i][i+2], F[i][i+3]... in order for (let gap = 1; gap < n; ++gap) { for (let i = 0, j = gap; j < n; ++i, ++j) { T[i][j] = F[i][j] = 0; for (let g = 0; g < gap; g++) { // Find place of parenthesization // using current value of gap let k = i + g; // Store Total[i][k] // and Total[k+1][j] let tik = T[i][k] + F[i][k]; let tkj = T[k + 1][j] + F[k + 1][j]; // Follow the recursive formulas // according to the current operator if (oper[k] == '&') { T[i][j] += T[i][k] * T[k + 1][j]; F[i][j] += (tik * tkj - T[i][k] * T[k + 1][j]); } if (oper[k] == '|') { F[i][j] += F[i][k] * F[k + 1][j]; T[i][j] += (tik * tkj - F[i][k] * F[k + 1][j]); } if (oper[k] == '^') { T[i][j] += F[i][k] * T[k + 1][j] + T[i][k] * F[k + 1][j]; F[i][j] += T[i][k] * T[k + 1][j] + F[i][k] * F[k + 1][j]; } } } } return T[0][n - 1]; } let symbols = "TTFT".split(''); let operators = "|&^".split(''); let n = symbols.length; // There are 4 ways // ((T|T)&(F^T)), (T|(T&(F^T))), // (((T|T)&F)^T) and (T|((T&F)^T)) document.write(countParenth(symbols, operators, n)); // This code is contributed by mukesh07.</script> |
Output
4
Time Complexity: O(n3), as we are using nested loops to traverse n3 times. Where n is the length of the symbols string.
Auxiliary Space: O(n2), as we are using extra space for the DP matrix. Where n is the length of the symbols string.
Approach 2:
We can also use the recursive approach (Top-Down DP), this approach uses memoization.
C++
#include <bits/stdc++.h>using namespace std;int dp[101][101][2];int parenthesis_count(string s, int i, int j, int isTrue){ // Base Condition if (i > j) return false; if (i == j) { if (isTrue == 1) return s[i] == 'T'; else return s[i] == 'F'; } if (dp[i][j][isTrue] != -1) return dp[i][j][isTrue]; int ans = 0; for (int k = i + 1 ; k <= j - 1; k = k + 2) { int leftF, leftT, rightT, rightF; if (dp[i][k - 1][1] == -1) { leftT = parenthesis_count(s, i, k - 1, 1); } // Count no. of T in left partition else { leftT = dp[i][k - 1][1]; } if (dp[k + 1][j][1] == -1) { rightT = parenthesis_count(s, k + 1, j, 1); } // Count no. of T in right partition else { rightT = dp[k + 1][j][1]; } if (dp[i][k - 1][0] == -1) { // Count no. of F in left partition leftF = parenthesis_count(s, i, k - 1, 0); } else { leftF = dp[i][k - 1][0]; } if (dp[k + 1][j][0] == -1) { // Count no. of F in right partition rightF = parenthesis_count(s, k + 1, j, 0); } else { rightF = dp[k + 1][j][0]; } if (s[k] == '&') { if (isTrue == 1) ans += leftT * rightT; else ans += leftF * rightF + leftT * rightF + leftF * rightT; } else if (s[k] == '|') { if (isTrue == 1) ans += leftT * rightT + leftT * rightF + leftF * rightT; else ans = ans + leftF * rightF; } else if (s[k] == '^') { if (isTrue == 1) ans = ans + leftF * rightT + leftT * rightF; else ans = ans + leftT * rightT + leftF * rightF; } dp[i][j][isTrue] = ans; } return ans;}// Driver Codeint main(){ string symbols = "TTFT"; string operators = "|&^"; string s; int j = 0; for (int i = 0; i < symbols.length(); i++) { s.push_back(symbols[i]); if (j < operators.length()) s.push_back(operators[j++]); } // We obtain the string T|T&F^T int n = s.length(); // There are 4 ways // ((T|T)&(F^T)), (T|(T&(F^T))), (((T|T)&F)^T) and // (T|((T&F)^T)) memset(dp, -1, sizeof(dp)); cout << parenthesis_count(s, 0, n - 1, 1); return 0;} |
Java
import java.io.*;import java.util.*;class GFG { public static int countWays(int N, String S) { int dp[][][] = new int[N + 1][N + 1][2]; for (int row[][] : dp) for (int col[] : row) Arrays.fill(col, -1); return parenthesis_count(S, 0, N - 1, 1, dp); } public static int parenthesis_count(String str, int i, int j, int isTrue, int[][][] dp) { if (i > j) return 0; if (i == j) { if (isTrue == 1) { return (str.charAt(i) == 'T') ? 1 : 0; } else { return (str.charAt(i) == 'F') ? 1 : 0; } } if (dp[i][j][isTrue] != -1) return dp[i][j][isTrue]; int temp_ans = 0; int leftTrue, rightTrue, leftFalse, rightFalse; for (int k = i + 1; k <= j - 1; k = k + 2) { if (dp[i][k - 1][1] != -1) leftTrue = dp[i][k - 1][1]; else { // Count number of True in left Partition leftTrue = parenthesis_count(str, i, k - 1, 1, dp); } if (dp[i][k - 1][0] != -1) leftFalse = dp[i][k - 1][0]; else { // Count number of False in left Partition leftFalse = parenthesis_count(str, i, k - 1, 0, dp); } if (dp[k + 1][j][1] != -1) rightTrue = dp[k + 1][j][1]; else { // Count number of True in right Partition rightTrue = parenthesis_count(str, k + 1, j, 1, dp); } if (dp[k + 1][j][0] != -1) rightFalse = dp[k + 1][j][0]; else { // Count number of False in right Partition rightFalse = parenthesis_count(str, k + 1, j, 0, dp); } // Evaluate AND operation if (str.charAt(k) == '&') { if (isTrue == 1) { temp_ans = temp_ans + leftTrue * rightTrue; } else { temp_ans = temp_ans + leftTrue * rightFalse + leftFalse * rightTrue + leftFalse * rightFalse; } } // Evaluate OR operation else if (str.charAt(k) == '|') { if (isTrue == 1) { temp_ans = temp_ans + leftTrue * rightTrue + leftTrue * rightFalse + leftFalse * rightTrue; } else { temp_ans = temp_ans + leftFalse * rightFalse; } } // Evaluate XOR operation else if (str.charAt(k) == '^') { if (isTrue == 1) { temp_ans = temp_ans + leftTrue * rightFalse + leftFalse * rightTrue; } else { temp_ans = temp_ans + leftTrue * rightTrue + leftFalse * rightFalse; } } dp[i][j][isTrue] = temp_ans; } return temp_ans; } // Driver code public static void main(String[] args) { String symbols = "TTFT"; String operators = "|&^"; StringBuilder S = new StringBuilder(); int j = 0; for (int i = 0; i < symbols.length(); i++) { S.append(symbols.charAt(i)); if (j < operators.length()) S.append(operators.charAt(j++)); } // We obtain the string T|T&F^T int N = S.length(); // There are 4 ways // ((T|T)&(F^T)), (T|(T&(F^T))), (((T|T)&F)^T) and // (T|((T&F)^T)) System.out.println(countWays(N, S.toString())); }}// This code is contributed by farheenbano. |
Python3
def parenthesis_count(Str, i, j, isTrue, dp) : if (i > j) : return 0 if (i == j) : if (isTrue == 1) : return 1 if Str[i] == 'T' else 0 else : return 1 if Str[i] == 'F' else 0 if (dp[i][j][isTrue] != -1) : return dp[i][j][isTrue] temp_ans = 0 for k in range(i + 1, j, 2) : if (dp[i][k - 1][1] != -1) : leftTrue = dp[i][k - 1][1] else : # Count number of True in left Partition leftTrue = parenthesis_count(Str, i, k - 1, 1, dp) if (dp[i][k - 1][0] != -1) : leftFalse = dp[i][k - 1][0] else : # Count number of False in left Partition leftFalse = parenthesis_count(Str, i, k - 1, 0, dp) if (dp[k + 1][j][1] != -1) : rightTrue = dp[k + 1][j][1] else : # Count number of True in right Partition rightTrue = parenthesis_count(Str, k + 1, j, 1, dp) if (dp[k + 1][j][0] != -1) : rightFalse = dp[k + 1][j][0] else : # Count number of False in right Partition rightFalse = parenthesis_count(Str, k + 1, j, 0, dp) # Evaluate AND operation if (Str[k] == '&') : if (isTrue == 1) : temp_ans = temp_ans + leftTrue * rightTrue else : temp_ans = temp_ans + leftTrue * rightFalse + leftFalse * rightTrue + leftFalse * rightFalse # Evaluate OR operation elif (Str[k] == '|') : if (isTrue == 1) : temp_ans = temp_ans + leftTrue * rightTrue + leftTrue * rightFalse + leftFalse * rightTrue else : temp_ans = temp_ans + leftFalse * rightFalse # Evaluate XOR operation elif (Str[k] == '^') : if (isTrue == 1) : temp_ans = temp_ans + leftTrue * rightFalse + leftFalse * rightTrue else : temp_ans = temp_ans + leftTrue * rightTrue + leftFalse * rightFalse dp[i][j][isTrue] = temp_ans return temp_ans def countWays(N, S) : dp = [[[-1 for k in range(2)] for i in range(N + 1)] for j in range(N + 1)] return parenthesis_count(S, 0, N - 1, 1, dp) symbols = "TTFT"operators = "|&^"S = ""j = 0for i in range(len(symbols)) : S = S + symbols[i] if (j < len(operators)) : S = S + operators[j] j += 1# We obtain the string T|T&F^TN = len(S)# There are 4 ways# ((T|T)&(F^T)), (T|(T&(F^T))), (((T|T)&F)^T) and# (T|((T&F)^T))print(countWays(N, S))# This code is contributed by divyesh072019 |
C#
using System;class GFG { static int parenthesis_count(string str, int i, int j, int isTrue, int[,,] dp) { if (i > j) return 0; if (i == j) { if (isTrue == 1) { return (str[i] == 'T') ? 1 : 0; } else { return (str[i] == 'F') ? 1 : 0; } } if (dp[i, j, isTrue] != -1) return dp[i, j, isTrue]; int temp_ans = 0; int leftTrue, rightTrue, leftFalse, rightFalse; for (int k = i + 1; k <= j - 1; k = k + 2) { if (dp[i, k - 1, 1] != -1) leftTrue = dp[i, k - 1, 1]; else { // Count number of True in left Partition leftTrue = parenthesis_count(str, i, k - 1, 1, dp); } if (dp[i, k - 1, 0] != -1) leftFalse = dp[i, k - 1, 0]; else { // Count number of False in left Partition leftFalse = parenthesis_count(str, i, k - 1, 0, dp); } if (dp[k + 1, j, 1] != -1) rightTrue = dp[k + 1, j, 1]; else { // Count number of True in right Partition rightTrue = parenthesis_count(str, k + 1, j, 1, dp); } if (dp[k + 1, j, 0] != -1) rightFalse = dp[k + 1, j, 0]; else { // Count number of False in right Partition rightFalse = parenthesis_count(str, k + 1, j, 0, dp); } // Evaluate AND operation if (str[k] == '&') { if (isTrue == 1) { temp_ans = temp_ans + leftTrue * rightTrue; } else { temp_ans = temp_ans + leftTrue * rightFalse + leftFalse * rightTrue + leftFalse * rightFalse; } } // Evaluate OR operation else if (str[k] == '|') { if (isTrue == 1) { temp_ans = temp_ans + leftTrue * rightTrue + leftTrue * rightFalse + leftFalse * rightTrue; } else { temp_ans = temp_ans + leftFalse * rightFalse; } } // Evaluate XOR operation else if (str[k] == '^') { if (isTrue == 1) { temp_ans = temp_ans + leftTrue * rightFalse + leftFalse * rightTrue; } else { temp_ans = temp_ans + leftTrue * rightTrue + leftFalse * rightFalse; } } dp[i, j, isTrue] = temp_ans; } return temp_ans; } static int countWays(int N, string S) { int[,,] dp = new int[N + 1, N + 1, 2]; for(int i = 0; i < (N + 1); i++) { for(int j = 0; j < (N + 1); j++) { for(int k = 0; k < 2; k++) { dp[i, j, k] = -1; } } } return parenthesis_count(S, 0, N - 1, 1, dp); } // Driver code static void Main() { string symbols = "TTFT"; string operators = "|&^"; string S = ""; int j = 0; for (int i = 0; i < symbols.Length; i++) { S = S + symbols[i]; if (j < operators.Length) S = S + operators[j++]; } // We obtain the string T|T&F^T int N = S.Length; // There are 4 ways // ((T|T)&(F^T)), (T|(T&(F^T))), (((T|T)&F)^T) and // (T|((T&F)^T)) Console.WriteLine(countWays(N, S)); }}// This code is contributed by divyeshrabadiya07. |
Javascript
<script>function countWays(N, S){ let dp = new Array(N + 1); for(let i = 0; i < N + 1; i++) { dp[i] = new Array(N+1); for(let j = 0; j < N + 1;j++) { dp[i][j] = new Array(2); for(let k = 0; k < 2; k++) dp[i][j][k] = -1; } } return parenthesis_count(S, 0, N - 1, 1, dp);}function parenthesis_count(str, i, j, isTrue, dp){ if (i > j) return 0; if (i == j) { if (isTrue == 1) { return (str[i] == 'T') ? 1 : 0; } else { return (str[i] == 'F') ? 1 : 0; } } if (dp[i][j][isTrue] != -1) return dp[i][j][isTrue]; let temp_ans = 0; let leftTrue, rightTrue, leftFalse, rightFalse; for (let k = i + 1; k <= j - 1; k = k + 2) { if (dp[i][k - 1][1] != -1) leftTrue = dp[i][k - 1][1]; else { // Count number of True in left Partition leftTrue = parenthesis_count(str, i, k - 1, 1, dp); } if (dp[i][k - 1][0] != -1) leftFalse = dp[i][k - 1][0]; else { // Count number of False in left Partition leftFalse = parenthesis_count(str, i, k - 1, 0, dp); } if (dp[k + 1][j][1] != -1) rightTrue = dp[k + 1][j][1]; else { // Count number of True in right Partition rightTrue = parenthesis_count(str, k + 1, j, 1, dp); } if (dp[k + 1][j][0] != -1) rightFalse = dp[k + 1][j][0]; else { // Count number of False in right Partition rightFalse = parenthesis_count(str, k + 1, j, 0, dp); } // Evaluate AND operation if (str[k] == '&') { if (isTrue == 1) { temp_ans = temp_ans + leftTrue * rightTrue; } else { temp_ans = temp_ans + leftTrue * rightFalse + leftFalse * rightTrue + leftFalse * rightFalse; } } // Evaluate OR operation else if (str[k] == '|') { if (isTrue == 1) { temp_ans = temp_ans + leftTrue * rightTrue + leftTrue * rightFalse + leftFalse * rightTrue; } else { temp_ans = temp_ans + leftFalse * rightFalse; } } // Evaluate XOR operation else if (str[k] == '^') { if (isTrue == 1) { temp_ans = temp_ans + leftTrue * rightFalse + leftFalse * rightTrue; } else { temp_ans = temp_ans + leftTrue * rightTrue + leftFalse * rightFalse; } } dp[i][j][isTrue] = temp_ans; } return temp_ans;} // Driver codelet symbols = "TTFT";let operators = "|&^";let S = [];let j = 0;for (let i = 0; i < symbols.length; i++){ S.push(symbols[i]); if (j < operators.length) S.push(operators[j++]);}// We obtain the string T|T&F^Tlet N = S.length;// There are 4 ways// ((T|T)&(F^T)), (T|(T&(F^T))), (((T|T)&F)^T) and// (T|((T&F)^T))document.write(countWays(N, S.join("")));// This code is contributed by avanitrachhadiya2155</script> |
Output
4
Time Complexity: O(n3), as we are using a loop to traverse, n times and we are making recursive calls which will cost n2 times. Where n is the length of the symbols string.
Auxiliary Space: O(n2), as we are using extra space for the DP matrix. Where n is the length of the symbols string.
References:
http://people.cs.clemson.edu/~bcdean/dp_practice/dp_9.swf
Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
