Program in C !
URL: http://www.cs.ucf.edu/courses/cop3502/fall2015/lab/NormForm.pdf
As you moot 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 disjunct (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 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 (B C)) (D 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. Input Format 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 lest case is followed by a dummy line made of (). Output Format For each test case, print the following line: 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. Sample Input/Output As you moot 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 disjunct (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 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 (B C)) (D 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. Input Format 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 lest case is followed by a dummy line made of (). Output Format For each test case, print the following line: 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. Sample Input/Output
