Given a Boolean expression with the following symbols:
'T' ---> true
'F' ---> false
And the following operators filled between symbols:
& ---> boolean AND
| ---> boolean OR
^ ---> boolean XOR
Count the number of ways we can parenthesize the expression so that the value of the expression evaluates to true.
​Input: char[] symbols = "TFT".toCharArray(); char[] operators = "^&".toCharArray(); Output: 2 Explanation: The given expression "T ^ F & T" evaluates true in two situations: "((T ^ F) & T)" and "(T ^ (F & T))". |
Solution:
1. static int countParenthesization(char[] symbols, char[] operators) { 2. int symbolsLength = symbols.length; 3. int[][] falseValues = new int[symbolsLength][symbolsLength]; 4. int[][] trueValues = new int[symbolsLength][symbolsLength]; 5. 6. for (int i = 0; i < symbolsLength; i++) { 7. falseValues[i][i] = (symbols[i] == 'F') ? 1 : 0; 8. trueValues[i][i] = (symbols[i] == 'T') ? 1 : 0; 9. } 10. 11. for (int gap = 1; gap < symbolsLength; gap++) { 12. for (int i = 0, j = gap; j < symbolsLength; i++, j++) { 13. trueValues[i][j] = falseValues[i][j] = 0; 14. for (int g = 0; g < gap; g++) { 15. int k = i + g; 16. 17. int TotalIK = trueValues[i][k] + falseValues[i][k]; 18. int TotalKJ = trueValues[k + 1][j] + falseValues[k + 1][j]; 19. 20. if (operators[k] == '&') { 21. trueValues[i][j] += trueValues[i][k] * trueValues[k + 1][j]; 22. falseValues[i][j] += (TotalIK * TotalKJ - trueValues[i][k] * trueValues[k + 1][j]); 23. } 24. if (operators[k] == '|') { 25. falseValues[i][j] += falseValues[i][k] * falseValues[k + 1][j]; 26. trueValues[i][j] += (TotalIK * TotalKJ - falseValues[i][k] * falseValues[k + 1][j]); 27. } 28. if (operators[k] == '^') { 29. trueValues[i][j] += falseValues[i][k] * trueValues[k + 1][j] + trueValues[i][k] * falseValues[k + 1][j]; 30. falseValues[i][j] += trueValues[i][k] * trueValues[k + 1][j] + falseValues[i][k] * falseValues[k + 1][j]; 31. } 32. } 33. } 34. } 35. return trueValues[0][symbolsLength - 1]; 36. } 37.