Question

In how many ways can the string \({\bf{A}} \cap {\bf{B - A}} \cap {\bf{B - A}}\) be fully parenthesized to yield an infix expression?

Short answer

Therefore, 14 ways of the given string can be fully parenthesized to yield an infix expression.

Step-by-step solution

General form

Preorder traversal:

Let T be an ordered rooted tree with root r. If T consists only of r, then r is the preorder traversal of T. Otherwise, suppose that\({T_1},{T_2},...,{T_n}\)are the subtrees at r from left to right in T. The preorder traversal begins by visiting r. It continues by traversing\({T_1},\)in preorder, then\({T_2}\)in preorder, and so on, until\({T_n}\)is traversed in preorder.

Postorder traversal:

Let T be an ordered rooted tree with root r. If T consists only of r, then r is the postorder traversal of T. Otherwise, suppose that\({T_1},{T_2},...,{T_n}\)are the subtrees at r from left to right. The postorder traversal begins by traversing\({T_1},\)in postorder, then\({T_2}\)in postorder, …, then\({T_n}\)in postorder, and ends by visiting r.

Inorder traversal:

Let T be an ordered rooted tree with root r. If Tconsists only of r, then r is the inorder traversal of T. Otherwise, suppose that\({T_1},{T_2},...,{T_n}\)are the subtrees at r from left to right. The inorder traversal begins by traversing\({T_1},\)in inorder, then visiting r. It continues by traversing\({T_2}\)in inorder, and so on, until\({T_n}\)is traversed in inorder.

Note: Since the prefix, postfix and infix form of this expression are founded by traversing this rooted tree in preorder, post order and inorder (including parentheses), respectively.

Represent the given expression using binary tree

Given that, the string is \(A \cap B - A \cap B - A\).

Let us parenthesized the given string. Using at most possible ways.

Case (1):

All possible ways with first occurrence of \( \cap \) as the outermost operation.

\(\begin{array}{l}\left( {A \cap \left( {B - \left( {A \cap \left( {B - A} \right)} \right)} \right)} \right)\\\left( {A \cap \left( {B - \left( {\left( {A \cap B} \right) - A} \right)} \right)} \right)\\\left( {A \cap \left( {\left( {B - A} \right) \cap \left( {B - A} \right)} \right)} \right)\\\left( {A \cap \left( {\left( {\left( {B - A} \right) \cap B} \right) - A} \right)} \right)\\\left( {A \cap \left( {\left( {B - \left( {A \cap B} \right)} \right) - A} \right)} \right)\\\left( {\left( {\left( {A \cap B} \right) - A} \right) \cap \left( {B - A} \right)} \right)\\\left( {\left( {A \cap \left( {B - A} \right)} \right) \cap \left( {B - A} \right)} \right)\end{array}\)

So, there are 7 possible expressions we founded.

Case (2):

All possible ways with \( - \) as the outermost operation.

\(\begin{array}{l}\left( {\left( {A \cap B} \right) - \left( {\left( {A \cap B} \right) - A} \right)} \right)\\\left( {\left( {A \cap B} \right) - \left( {A \cap \left( {B - A} \right)} \right)} \right)\\\left( {\left( {A \cap \left( {\left( {B - A} \right) \cap B} \right)} \right) - A} \right)\\\left( {\left( {A \cap \left( {B - \left( {A \cap B} \right)} \right)} \right) - A} \right)\\\left( {\left( {\left( {A \cap B} \right) - \left( {A \cap B} \right)} \right) - A} \right)\\\left( {\left( {\left( {\left( {A \cap B} \right) - A} \right) \cap B} \right) - A} \right)\\\left( {\left( {\left( {A \cap \left( {B - A} \right)} \right) \cap B} \right) - A} \right)\end{array}\)

So, there are 7 possible expressions we founded.

Now, find the total number of possible ways.

\(7 + 7 = 14\).

So, there are 14 ways.