Data Structure Questions and Answers – Counting Boolean Parenthesizations

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Counting Boolean Parenthesizations”.

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) Dynamic programming, Recursion and Brute force

Explanation: Dynamic programming, Recursion and Brute force can be used to solve the Boolean parenthesization problem.

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

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

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

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

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

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

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

Explanation: The nth Catalan number gives the total number of ways of parenthesizing an expression with n + 1 terms.
Note: Join free Sanfoundry classes at Telegram or Youtube

6. What is the maximum number of ways in which a boolean expression with n + 1 terms can be parenthesized, such that the output is true?
a) nth catalan number
b) n factorial
c) n cube
d) n square

Explanation: The number of ways will be maximum when all the possible parenthesizations result in a true value. The number of possible parenthesizations is given by the nth catalan number.

7. Consider the following dynamic programming implementation of the boolean parenthesization problem:

```int count_bool_parenthesization(char *sym, char *op)
{
int str_len = strlen(sym);
int True[str_len][str_len],False[str_len][str_len];
int row,col,length,l;
for(row = 0, col = 0; row < str_len; row++,col++)
{
if(sym[row] == 'T')
{
True[row][col] = 1;
False[row][col] = 0;
}
else
{
True[row][col] = 0;
False[row][col] = 1;
}
}
for(length = 1; length < str_len; length++)
{
for(row = 0, col = length; col < str_len; col++, row++)
{
True[row][col] = 0;
False[row][col] = 0;
for(l = 0; l < length; l++)
{
int pos = row + l;
int t_row_pos = True[row][pos] + False[row][pos];
int t_pos_col = True[pos+1][col] + False[pos+1][col];
if(op[pos] == '|')
{
_______________;
}
if(op[pos] == '&')
{
_______________;
}
if(op[pos] == '^')
{
_______________;
}
}
}
}
return True[0][str_len-1];
}```

Which of the following lines should be added to complete the “if(op[pos] == ‘|’)” part of the code?
a) False[row][col] += True[row][pos] * False[pos+1][col];
True[row][col] += t_row_pos * t_pos_col + False[row][pos] * False[pos+1][col];
b) False[row][col] += False[row][pos] * True[pos+1][col];
True[row][col] += t_row_pos * t_pos_col – True[row][pos] * True[pos+1][col];
c) False[row][col] += True[row][pos] * True[pos+1][col];
True[row][col] += t_row_pos * t_pos_col + True[row][pos] * True[pos+1][col];
d) False[row][col] += False[row][pos] * False[pos+1][col];
True[row][col] += t_row_pos * t_pos_col – False[row][pos] * False[pos+1][col];

Explanation: The following lines should be added:
False[row][col] += False[row][pos] * False[pos+1][col];
True[row][col] += t_row_pos * t_pos_col + False[row][pos] * False[pos+1][col];

8. Which of the following lines should be added to complete the “if(op[k] == ‘&’)” part of the following code?

```int count_bool_parenthesization(char *sym, char *op)
{
int str_len = strlen(sym);
int True[str_len][str_len],False[str_len][str_len];
int row,col,length,l;
for(row = 0, col = 0; row < str_len; row++,col++)
{
if(sym[row] == 'T')
{
True[row][col] = 1;
False[row][col] = 0;
}
else
{
True[row][col] = 0;
False[row][col] = 1;
}
}
for(length = 1; length < str_len; length++)
{
for(row = 0, col = length; col < str_len; col++, row++)
{
True[row][col] = 0;
False[row][col] = 0;
for(l = 0; l < length; l++)
{
int pos = row + l;
int t_row_pos = True[row][pos] + False[row][pos];
int t_pos_col = True[pos+1][col] + False[pos+1][col];
if(op[pos] == '|')
{
_______________;
}
if(op[pos] == '&')
{
_______________;
}
if(op[pos] == '^')
{
_______________;
}
}
}
}
return True[0][str_len-1];
}```

a) True[row][col] += False[row][pos] * False[pos+1][col];
False[row][col] += t_row_pos * t_pos_col – True[row][pos] * True[pos+1][col];
b) True[row][col] += True[row][pos] * True[pos+1][col];
False[row][col] += t_row_pos * t_pos_col – True[row][pos] * True[pos+1][col];
c) True[row][col] += True[row][pos] * False[pos+1][col];
False[row][col] += t_row_pos * t_pos_col – False[row][pos] * True[pos+1][col];
d) True[row][col] += False[row][pos] * True[pos+1][col];
False[row][col] += t_row_pos * t_pos_col – False[row][pos] * True[pos+1][col];

Explanation: The following lines should be added:
True[row][col] += True[row][pos] * True[pos+1][col];
False[row][col] += t_row_pos * t_pos_col – True[row][pos] * True[pos+1][col];

9. What is the time complexity of the following dynamic programming implementation of the boolean parenthesization problem?

```int count_bool_parenthesization(char *sym, char *op)
{
int str_len = strlen(sym);
int True[str_len][str_len],False[str_len][str_len];
int row,col,length,l;
for(row = 0, col = 0; row < str_len; row++,col++)
{
if(sym[row] == 'T')
{
True[row][col] = 1;
False[row][col] = 0;
}
else
{
True[row][col] = 0;
False[row][col] = 1;
}
}
for(length = 1; length < str_len; length++)
{
for(row = 0, col = length; col < str_len; col++, row++)
{
True[row][col] = 0;
False[row][col] = 0;
for(l = 0; l < length; l++)
{
int pos = row + l;
int t_row_pos = True[row][pos] + False[row][pos];
int t_pos_col = True[pos+1][col] + False[pos+1][col];
if(op[pos] == '|')
{
False[row][col] += False[row][pos] * False[pos+1][col];
True[row][col] += t_row_pos * t_pos_col - False[row][pos] * False[pos+1][col];;
}
if(op[pos] == '&')
{
True[row][col] += True[row][pos] * True[pos+1][col];
False[row][col] += t_row_pos * t_pos_col - True[row][pos] * True[pos+1][col];
}
if(op[pos] == '^')
{
True[row][col] += True[row][pos] * False[pos+1][col]
+ False[row][pos] * True[pos + 1][col];
False[row][col] += True[row][pos] * True[pos+1][col]
+ False[row][pos] * False[pos+1][col];
}
}
}
}
return True[0][str_len-1];
}```

a) O(1)
b) O(n)
c) O(n2)
d) O(n3)

Explanation: The time complexity of the above dynamic programming implementation is O(n3).

10. What is the space complexity of the following dynamic programming implementation of the boolean parenthesization problem?

```int count_bool_parenthesization(char *sym, char *op)
{
int str_len = strlen(sym);
int True[str_len][str_len],False[str_len][str_len];
int row,col,length,l;
for(row = 0, col = 0; row < str_len; row++,col++)
{
if(sym[row] == 'T')
{
True[row][col] = 1;
False[row][col] = 0;
}
else
{
True[row][col] = 0;
False[row][col] = 1;
}
}
for(length = 1; length < str_len; length++)
{
for(row = 0, col = length; col < str_len; col++, row++)
{
True[row][col] = 0;
False[row][col] = 0;
for(l = 0; l < length; l++)
{
int pos = row + l;
int t_row_pos = True[row][pos] + False[row][pos];
int t_pos_col = True[pos+1][col] + False[pos+1][col];
if(op[pos] == '|')
{
False[row][col] += False[row][pos] * False[pos+1][col];
True[row][col] += t_row_pos * t_pos_col - False[row][pos] * False[pos+1][col];;
}
if(op[pos] == '&')
{
True[row][col] += True[row][pos] * True[pos+1][col];
False[row][col] += t_row_pos * t_pos_col - True[row][pos] * True[pos+1][col];
}
if(op[pos] == '^')
{
True[row][col] += True[row][pos] * False[pos+1][col]
+ False[row][pos] * True[pos + 1][col];
False[row][col] += True[row][pos] * True[pos+1][col]
+ False[row][pos] * False[pos+1][col];
}
}
}
}
return True[0][str_len-1];
}```

a) O(1)
b) O(n)
c) O(n2)
d) O(n3)

Explanation: The space complexity of the above dynamic programming implementation is O(n2).

11. What is the output of the following code?

```#include<stdio.h>
#include<string.h>
int count_bool_parenthesization(char *sym, char *op)
{
int str_len = strlen(sym);
int True[str_len][str_len],False[str_len][str_len];
int row,col,length,l;
for(row = 0, col = 0; row < str_len; row++,col++)
{
if(sym[row] == 'T')
{
True[row][col] = 1;
False[row][col] = 0;
}
else
{
True[row][col] = 0;
False[row][col] = 1;
}
}
for(length = 1; length < str_len; length++)
{
for(row = 0, col = length; col < str_len; col++, row++)
{
True[row][col] = 0;
False[row][col] = 0;
for(l = 0; l < length; l++)
{
int pos = row + l;
int t_row_pos = True[row][pos] + False[row][pos];
int t_pos_col = True[pos+1][col] + False[pos+1][col];
if(op[pos] == '|')
{
False[row][col] += False[row][pos] * False[pos+1][col];
True[row][col] += t_row_pos * t_pos_col - False[row][pos] * False[pos+1][col];
}
if(op[pos] == '&')
{
True[row][col] += True[row][pos] * True[pos+1][col];
False[row][col] += t_row_pos * t_pos_col - True[row][pos] * True[pos+1][col];
}
if(op[pos] == '^')
{
True[row][col] += True[row][pos] * False[pos+1][col]
+ False[row][pos] * True[pos + 1][col];
False[row][col] += True[row][pos] * True[pos+1][col]
+ False[row][pos] * False[pos+1][col];
}
}
}
}
return True[0][str_len-1];
}
int main()
{
char sym[] = "TTTT";
char op[] = "|^^";
int ans = count_bool_parenthesization(sym,op);
printf("%d",ans);
return 0;
}```

a) 1
b) 2
c) 3
d) 4

Explanation: The output of the above program is 4.

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]