import java.util.* ; import java.io.*; public class Solution { public static long mod = (long)1e9+7; public static int evaluateExp(String str) { int n = str.length(); return (int)solve(str , 0 ,n-1 ,1 , new Long[n+1][n+1][2]); } //memo -> (n*n*2)*n = n^3 |sc ->n*n*2 + n(height of stack) public static long solve(String str , int i , int j , int exp , Long[][][]dp ){ if(i > j) return 0; //base case , for only one expression remains if(i == j){ char ch = str.charAt(i); if(exp == 1) //for true return ch == 'T' ? 1 : 0; else //for false return ch == 'F' ? 1 : 0; } if(dp[i][j][exp] != null) return dp[i][j][exp]; long ways = 0; for(int k = i+1 ; k <= j ;k+=2){ //calls for no. of ways the left/right expression can be false(0) and true(1) (faith) long lt = solve(str , i , k-1 ,1 , dp); long rt = solve(str , k+1 , j , 1 ,dp); long lf = solve(str , i,k-1 , 0 , dp); long rf = solve(str , k+1 , j , 0 , dp); //checks no.of true false ways and return accordingly char ch = str.charAt(k); if(ch == '&'){ //true ways if(exp == 1){ ways = (ways + (lt * rt)%mod)%mod; } //false ways else ways = (ways + (lf*rf)%mod + (lf*rt)%mod + (lt*rf)%mod)%mod; } else if(ch == '|'){ if(exp == 1){ ways = (ways + (lt * rt)%mod + (lf*rt)%mod + (lt*rf)%mod)%mod; } else ways = (ways + (lf*rf)%mod)%mod; } else{ // ^ ways if(exp == 1){ ways = (ways + (lt * rf)%mod + (lf*rt)%mod)%mod; } else ways = (ways + (lf*rf)%mod + + (lt*rt)%mod)%mod; } } return dp[i][j][exp] = ways; } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter