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.

a


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.

Input

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 ().

Output

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.

Example

Input:
((F(TF))(TF))
(TFT)
((TFT)T)
()

Output:
1. false
2. false
3. true

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

hide comments
2020-09-19 06:16:37
very easy problem
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.
2017-01-25 09:51:21
AC in 1 go :-)
2016-11-12 14:59:49
Nice :)
2016-04-17 09:44:17 GAURAV CHANDEL
Lovely Problem..
2014-12-01 17:39:40 Deepak Gupta
Remember
An internal node with both children as leaf, can be OR node as given in the figure.
2012-07-30 18:10:17 (Tjandra Satria Gunawan)(曾毅昆)
@Sachin Railhan: the answer for statement ((T)F) is true.
2012-07-30 10:35:19 Sachin Railhan
What is the answer for statement ((T)F) ?
2011-06-06 00:42:25 Santiago Zubieta
I'm getting RTE in cases like (T), ((T)) and so on...
2011-03-31 17:42:43 kshitij agrawal
print a space after the '.'
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.