ACPC10C - Normalized Form

no tags 

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:
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.



1. false
2. false
3. true

hide comments
mahabir10: 2020-09-19 06:16:37

very easy problem

nadstratosfer: 2019-07-13 08:38:59

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.

vengatesh15: 2017-01-25 09:51:21

AC in 1 go :-)

hodobox: 2016-11-12 14:59:49

Nice :)

GAURAV CHANDEL: 2016-04-17 09:44:17

Lovely Problem..

Deepak Gupta: 2014-12-01 17:39:40

An internal node with both children as leaf, can be OR node as given in the figure.

(Tjandra Satria Gunawan)(曾毅昆): 2012-07-30 18:10:17

@Sachin Railhan: the answer for statement ((T)F) is true.

Sachin Railhan: 2012-07-30 10:35:19

What is the answer for statement ((T)F) ?

Hasan0540: 2012-06-20 15:34:20


Last edit: 2012-06-20 18:12:34
manish sharma: 2011-12-09 04:38:43

Last edit: 2012-01-14 15:46:18

Added by:Omar ElAzazy
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:ACPC 2010