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

Boolean Evaluation

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
126 upvotes
Asked in companies
SliceIntuitAmazon

Problem statement

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 ( Input/output format, Notes, Images )

Sample Input 1 :

T^T^F    

Sample Output 1 :

0

Explanation For Sample Input 1:

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.
Sample Input 2 :
F|T^F
Sample Output 2 :
2

Explanation For Sample Input 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.

Expected time complexity

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

Constraints:

3 <= |‘exp’| <= 200
Where |'exp'| denotes the length of 'exp'.

Time Limit: 1 sec
Full screen
Console