# Data Structure Questions and Answers-Counting Boolean Parenthesizations

## Click on any option to know the CORRECT ANSWERS

 Question 1
You are given a boolean expression which consists of operators &, | and ∧ (AND, OR and XOR) and symbols T or F (true or false). You have to find the number of ways in which the symbols can be parenthesized so that the expression evaluates to true. This is the boolean parenthesization problem. Which of the following methods can be used to solve the problem?
 A Dynamic programming B Recursion C Brute force D All of the mentioned

Question 1 Explanation:
All of the mentioned methods can be used to solve the boolean parenthesization problem.

 Question 2
Consider the expression T & F | T. What is the number of ways in which the expression can be parenthesized so that the output is T (true)?
 A 0 B 1 C 2 D 3

Question 2 Explanation:
The expression can only be parenthesized as T & (F | T), so that the output is T.

 Question 3
Consider the expression T & F ∧ T. What is the number of ways in which the expression can be parenthesized so that the output is T (true)?
 A 0 B 1 C 2 D 3

Question 3 Explanation:
The expression can be parenthesized as (T & F) ∧ T or T & (F ∧ T), so that the output is T.

 Question 4
Consider the expression T | F ∧ T. In how many ways can the expression be parenthesized so that the output is F (false)?
 A 0 B 1 C 2 D 3

Question 4 Explanation:
The expression can be parenthesized as (T | F) ∧ T, so that the output is F (false).

 Question 5
Which of the following gives the total number of ways of parenthesizing an expression with n + 1 terms?
 A n factorial B n square C n cube D nth catalan number