Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 28 Feb, 2021

Moderate

```
‘T’ will represent the operand TRUE.
‘F’ will represent the operand FALSE.
‘|’ will represent the operator OR.
‘&’ will represent the operator AND.
‘^’ will represent the operator XOR.
```

```
Input: 'exp’ = "T|T & F".
Output: 1
Explanation:
There are total 2 ways to parenthesize this expression:
(i) (T | T) & (F) = F
(ii) (T) | (T & F) = T
Out of 2 ways, one will result in True, so we will return 1.
```

```
The first line of each input contains a string representing the expression ‘exp’.
```

```
print a single integer representing the number of ways we can parenthesize the expression to evaluate to true.
```

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

Approach: Basically, we will divide the expression into smaller parts and will try to find the number of ways a smaller expression can result in True and the number of ways a smaller expression can result in False.

With the help of the result of the smaller expression, we will be able to find the number of ways the whole expression can result in True.

Let’s define a recursive function, ‘findWays’, which will receive the following parameter.

(i) ‘exp’ the given expression.

(ii) ‘st’ is an integer variable representing the starting point for the sub-expression.

(iii) ‘end’ is an integer variable representing the ending point for the sub-expression.

(iii) ‘isTrue’ is a bool variable representing whether the sub-expression should evaluate to True or False.

- If ‘st’ > ‘end’ then do:
- Return False.

- If ‘st’ is equal to ‘end’ then do:
- If ‘isTrue’ is equal to True :
- If current element is true or ‘exp[st]’ == ‘T’
- Return True

- Else
- Return False.

- If current element is true or ‘exp[st]’ == ‘T’
- If ‘isTrue’ is equal to False :
- If current element is False or ‘exp[st]’ == ‘F’
- Return True.

- Else
- Return False.

- If current element is False or ‘exp[st]’ == ‘F’

- If ‘isTrue’ is equal to True :

- Initialize an integer variable ‘ans’=0.
- Run a loop over ‘exp’ for ‘st’+1 <= ‘k’ <= 'end’-1 and do:
- We will need to find out the value of the below variables
- ‘leftTrue’ = The number of ways the expression left to ‘k’ will be true.
- ‘leftFalse’ = The number of ways the expression left to ‘k’ will be false.
- ‘rightTrue’ = The number of ways expression right to ‘k’ will be true:
- ‘rightFalse’ = The number of ways expression right to ‘k’ will be true:
- We will find these values by making calls to ‘findWays'.
- To make a call to the left part, ‘st’ will be ‘st’, and ‘end’ will be ‘k’-1.
- To make a call to the right part, ‘st’ will be ‘k’+1, and ‘end’ will be ‘end’.
- Set the value of ‘isTrue’ = True if we need to find out the number of ways for true else, set False.

- Now there will be many combinations according to the value of ‘isTrue’ and the value of the current operator(‘exp[k]’).
- Let’s find out what value will current sub-expression add to ‘ans’ for the given operator ‘|’ and ‘isTrue’ = True.
- The truth table for OR :
- T|T=T
- F|T=T
- T|F=T
- F|F=F

- So ‘ans’+= ‘leftTrue’*‘rightFalse’ +‘leftFalse’ *‘rightTrue’ +‘leftTrue’*‘rightTrue’
- Similarly, we can find’ for other operators.
- Return ‘ans’.

**Approach:** Our last approach was very simple and easy, but its time complexity was of exponential order. We can improve our solution by taking care of the overlapping subproblems. Thus, we will eliminate the need for solving the same subproblems again and again by storing them in a lookup table. This approach is known as Memoization.

We will initialize a 3-D array, say ‘memo’ [n][n][2] with -1, where ‘n' is the size of string ‘exp’.Where ‘memo’[i][j][k] equal to -1 means the current state is not explored. Otherwise, ‘memo’[i][j][0] will store the number of ways expression(i, j) will be false, and ‘memo’[i][j][1] will store the number of ways expression(i, j) will be True.

So there will be two modifications to the earlier approach :

- In Base Case, first of all, we will check the value of 'memo’ if it is -1, then simply return the value stored in the ‘memo’.
- In Recursive Calls, before returning the ‘ans’, we will store the value in ‘memo’’.

**Algorithm:**

**We will initialize a 3-D array, say ‘dp[n][n][1]’ with 0, where ‘n’ is the size of string ‘exp’. ‘dp’[i][j][0] will store the number of ways expression(i, j) will be false, and ‘dp’[i][j][1] will store the number of ways expression(i, j) will be True.****Iterate over the ‘exp’ for 2 <= ‘gap’ < ‘n’ each time increasing ‘gap’ by 2 and do:**- Iterate over the ‘exp’ for 2 <= ‘j’ < ‘n’ each time increasing 'j' by 2 and do:
- Iterate over the ‘exp’ for 2 <= ‘k’ < ‘n’ each time increasing ‘k’ by 2 and do:
- ‘leftTrue’ = ’dp'[j][k][1] (The number of ways expression left to ‘k’ will be true).
- ‘leftFalse’ = ’dp'[j][k][1] (The number of ways expression left to ‘k’ will be false).
- ‘rightTrue’ = ’dp'[k+2][j+gap][0] ( The number of ways expression right to ‘k’ will be False).
- ‘rightFalse’ = ’dp'[k+2][j+gap][1] ( The number of ways expression right to ‘k’ will be False).
- If 'exp[k+1]’ = ‘|’ then :
- ‘dp’[j][j+gap][1]+= ‘leftTrue’ * ’rightTrue’+ ‘leftFalse' * ‘rightTrue' + ‘leftTrue’ * ’rightTrue’.
- ‘dp'[j][j+gap][0]+= ‘leftFalse' * ‘rightFalse’.
- Similarly, we can solve for other operators too.

- Iterate over the ‘exp’ for 2 <= ‘k’ < ‘n’ each time increasing ‘k’ by 2 and do:

- Iterate over the ‘exp’ for 2 <= ‘j’ < ‘n’ each time increasing 'j' by 2 and do:
**Return ‘dp’[0][n-1][1].**