Boolean Evaluation

Posted: 28 Feb, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given an expression ‘EXP’ in the form of a string where operands will be : (TRUE and FALSE) and operators will be : (AND, OR, XOR). Now you have to find the number of ways we can parenthesize the expression such that it will evaluate to TRUE.

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.

For example :

 Input: 
 'EXP’ = T|T & F
 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.

 Output :
 1

Note :

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

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The second line of each test case contains a string representing the expression ‘EXP’.

Output format:

For each test case, print a single integer representing the number of ways we can parenthesize the expression such that it evaluates to true.   

Print the output of each test case in a separate line. 
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
3 <= |‘EXP’| <= 200    
Where |EXP| denotes the length of 'EXP'.

Time Limit: 1 sec
Approach 1

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 ‘FIND_WAYS’ which will receive the following parameter.

(i) ‘EXP’ the given expression.

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

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

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

 

Base Condition :

  1. If ‘ST’ > ‘END’ then do:
    • Return False.
  2. If ‘ST’ is equal to ‘END’ then do:
    • If ‘IS_TRUE’ is equal to True :
      • If current element is true or ‘EXP[ST]’ == ‘T’
        • Return True
      • Else
        • Return False.
    • If ‘IS_TRUE’ is equal to False :
      • If current element is False or ‘EXP[ST]’ == ‘F’
        • Return True.
      • Else
        • Return False.

Recursive Calls:

  1. Initialize an integer variable ‘ANS’=0.
  2. 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
    • “LEFT_TRUE’  = The number of ways expression left to ‘K’ will be true.
    • “LEFT_FALSE’  = The number of ways expression left to ‘K’ will be false.
    • “RIGHT_TRUE’  = The number of ways expression right to ‘K’ will be true:
    • “RIGHT_FALSE’  = The number of ways expression right to ‘K’ will be true:
    • We will find these values by making calls to ‘FIND_WAYS.
    • 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 ‘IS_TRUE’ = True if we need to find out the number of ways for true else set False.
  3. Now there will be many combinations according to the value of ‘IS_TRUE’ and the value of the current operator(‘EXP[K]’).
  4. Let’s find out what value will current sub-expression add into ‘ANS’ for the given operator ‘|’ and ‘IS_TRUE’ = True.
  5. The truth table for OR :
    • T|T=T
    • F|T=T
    • T|F=T
    • F|F=F
  6. So ‘ANS’+= “LEFT_TRUE’*“RIGHT_FALSE’+ “LEFT_FALSE’*“RIGHT_TRUE’+ “LEFT_TRUE’*“RIGHT_TRUE’
  7. Similarly, we can find’ for other combinations.
  8. Return ‘ANS’.
Try Problem