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

Problem of the day

You are given an expression * 'exp'* in the form of a string where operands will be : (TRUE or FALSE), and operators will be : (AND, OR or XOR).

Now you have to find the number of ways we can parenthesize the expression such that it will evaluate to TRUE.

As the answer can be very large, return the output modulo 1000000007.

Note :

```
‘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.
```

Example :

```
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.
```

Detailed explanation

```
T^T^F
```

```
0
```

```
There are total 2 ways to parenthesize this expression:
(i) (T^T)^(F) = F
(ii) (T)^(T^F) = F
Both ways will result in False, so we will return 0.
```

```
F|T^F
```

```
2
```

```
For the first test case:
There are total 2 ways to parenthesize this expression:
(i) (F|T)^(F) = T
(ii) (F)|(T^F) = T
Both ways will result in True, so we will return 2.
```

```
The expected time complexity is O(n ^ 3), where 'n' denotes the length of 'exp'.
```

```
3 <= |‘exp’| <= 200
Where |'exp'| denotes the length of 'exp'.
Time Limit: 1 sec
```