ACPC10C - Normalized Form
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 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 ex- pressions 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 upwards 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.
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:
( E1 E2 . . . En )
where n > 0 and Ei 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:
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.
very easy problem
Nice one. Ignore confusing comments; (T) is not a valid expression because both AND and OR need at least 2 operands. ((TFT)T) = ((1 or 0 or 1) and 1) = 1 and 1 = 1.
AC in 1 go :-)
(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
@Sachin Railhan: the answer for statement ((T)F) is true.
What is the answer for statement ((T)F) ?
....Last edit: 2012-06-20 18:12:34
Last edit: 2012-01-14 15:46:18