A Smart Brain is a Tasty Brain

Interview

Time limit1sMemory limit128 MB

Summary

Parse each of up to 10000 Boolean expressions, evaluate it, and report whether the brain's given answer matches.

Level: Medium4 of 10
Topics: String, Stack, Recursion, Implementation
Solved: No attempts yet

Problem

The zombies have cornered you and your team. There's no hope... but then they stop and, instead of eating you, offer a deal. As it turns out, zombies have trouble finding good-tasting brains — and to a zombie, a good-tasting brain is a smart brain. Your brains would be delicious, but the zombies decide they are better used to help find other smart brains. The deal: help them decide whether a given brain is smart (and therefore tasty), and they will let your team go — at least for now.

A brain is judged smart if it can correctly evaluate a given Boolean expression. You compile a list of Boolean expressions and test each brain on one of them; the brain reports the value it computed.

Every Boolean expression is deterministic and is defined recursively:

expression = '(' + (value or expression) + operation + (value or expression) + ')'
value = 't' or 'f'
operation = '&' or '|'
Any value or expression may be preceded by an optional !.

The expression contains no characters other than those below:

& is AND: (a&b) is true only when both a and b are true; otherwise false.
| is OR: (a|b) is false only when both a and b are false; otherwise true.
! is NOT: it flips the value immediately following it.
( and ) bound an expression; everything inside the parentheses is evaluated first, and every ( has a matching ).
t and f represent true and false, respectively.

Input

The first line contains an integer $x$ with $0 < x \le 10000$ . Each of the next $x$ lines contains one complete Boolean expression (at most 50 characters), followed by a space, an equals sign =, another space, and the tested brain's evaluation of that expression (either t or f).

Output

For each tested brain, on its own line, print the brain's number, then a colon and a space, then Good brain if the expression was evaluated correctly or Bad brain if it was not. Once you are finished, you might want to start running as fast as you can — the zombies will only give you so much of a head start.

Examples3

Example 1

Input

4
(t|f) = f
((t|f)&((f|t)&f)) = f
((f&f)|(f|!(t&f))) = t
(f|(f|t)) = f

Expected output

1: Bad brain
2: Good brain
3: Good brain
4: Bad brain

Example 2

Input

6
(t&t) = t
(t&f) = t
(f|f) = f
(f|t) = f
!(t&t) = f
!(f|f) = t

Expected output

1: Good brain
2: Bad brain
3: Good brain
4: Bad brain
5: Good brain
6: Good brain

Example 3

Input

4
t = t
f = f
t = f
f = t

Expected output

1: Good brain
2: Good brain
3: Bad brain
4: Bad brain