Program in C !!
As you most probably know, any Boolean expression can be expressed in either a disjunctive normal form or a conjunctive normal form. In a disjunctive normal form, a Boolean expression is written as a disjunction (logical or) of one-or more sub-expressions where each of these sub-expressions is written in a conjunctive normal form. Similarly, an expression written in a conjunctive normal form is a conjunct (logical and) of sub-expressions each written in a disjunctive normal form. An AND/OR tree is a tree-like graphical-representation of Boolean expressions written as either conjunctive- or disjunctive-normal form. Since the sub-expressions of a normalized form alternate in being either disjunctive or conjunctive forms, you'd expect the sub-trees on an AND/OR tree to alternate in being AND- or OR- trees depending on the sub-tree's depth-level. The example on the right illustrates this observation for the Boolean expression (A V (B Lambda C)) Lambda (D V E) where the trees in the 1st (top-most) and 3rd levels are AND-trees. Write a program that evaluates a given and/or tree. Your program will be tested on one or more test cases. Each test case is specified on exactly one line (which is no longer than 32,000 characters) of the form: (E_1 E_2 ... E_n) where n > 0 and E_i is either T for true, F for false, or a sub-expression using the same format. The trees at the deepest level are AND-trees. The last test case is followed by a dummy line made of (). For each test case, print the following line: k. _E Where k is the test case number (starting at one, ) and E is either true or false depending on the value of the expression in that test case. As you most probably know, any Boolean expression can be expressed in either a disjunctive normal form or a conjunctive normal form. In a disjunctive normal form, a Boolean expression is written as a disjunction (logical or) of one-or more sub-expressions where each of these sub-expressions is written in a conjunctive normal form. Similarly, an expression written in a conjunctive normal form is a conjunct (logical and) of sub-expressions each written in a disjunctive normal form. An AND/OR tree is a tree-like graphical-representation of Boolean expressions written as either conjunctive- or disjunctive-normal form. Since the sub-expressions of a normalized form alternate in being either disjunctive or conjunctive forms, you'd expect the sub-trees on an AND/OR tree to alternate in being AND- or OR- trees depending on the sub-tree's depth-level. The example on the right illustrates this observation for the Boolean expression (A V (B Lambda C)) Lambda (D V E) where the trees in the 1st (top-most) and 3rd levels are AND-trees. Write a program that evaluates a given and/or tree. Your program will be tested on one or more test cases. Each test case is specified on exactly one line (which is no longer than 32,000 characters) of the form: (E_1 E_2 ... E_n) where n > 0 and E_i is either T for true, F for false, or a sub-expression using the same format. The trees at the deepest level are AND-trees. The last test case is followed by a dummy line made of (). For each test case, print the following line: k. _E Where k is the test case number (starting at one, ) and E is either true or false depending on the value of the expression in that test case
