A Smart Brain is a Tasty Brain

The zombies have cornered you and your team. There's no hope...

But wait! Suddenly, they all stop advancing and offer you a deal. As it turns out, the zombies are having trouble finding good-tasting brains—by which they mean smart brains (nothing is more disgusting to a zombie than the brains of a communications major). While your brains would be very delicious, the zombies realize they could put you to better use helping find other smart brains. Here's the deal: help the zombies determine whether a given brain is smart (and therefore tasty) or not, and they will let your team go—at least for now.

Being the big-brained team that you are, you quickly determine that a brain is smart if it can provide the correct answer to a given Boolean expression. You compile a list of Boolean expressions and begin testing each one on a different brain.

Every Boolean expression is deterministic and defined recursively as follows:

1. expression $=$ '(' $+$ (value or expression) $+$ operation $+$ (value or expression) $+$ ')'

2. value $=$ 't' or 'f'

3. operation $=$ '' or '|'

4. Any value or expression can optionally be preceded by a '!'.

Expressions contain no characters other than those listed below. The meaning of each is:

1. '' is AND. $(a\&b)$ is true if $a$ and $b$ are both true; otherwise, false.

2. '|' is OR. $(a|b)$ is false if $a$ and $b$ are both false; otherwise, true.

3. '!' is NOT. $!(a)$ is false if $a$ is true; otherwise, true.

4. '(' and ')' are parentheses enclosing expressions. All expressions inside parentheses are evaluated first. Every '(' has a corresponding ')'.

5. 't' and 'f' mean true and false, respectively.