WC '02 P5 - Intercepted Cowmmunication

View as PDF

Points: 5
Time limit: 1.0s
Memory limit: 16M

Problem type
Woburn Challenge 2002

Finally, the monkeys have made a breakthrough. During a routine trip to the summit of the Enchanted Tree to gather sustenance (in the form of bananas) for the Head-Monkey, a "Tiny" helper-monkey found a sheet of paper, left behind by some cows, discussing their plan of attack against the monkeys. Now Tiny was a clever little monkey and knew to deliver this information to the Head-Monkey in order to receive a reward. Upon delivery, Tiny did receive his reward: An assignment to code a neural net in minutes flat, or risk having his fur shaved off, in a frenzy of monkey excitement.

Anyways… It turns out that the note was written in some kind of code that, appropriately enough, had to be decoded. The Head-Monkey summoned the legendary Big-White Monkey, to help her with the decryption algorithm. They used the classic decryption strategy of "Put yourself in the encoder's shoes". Working with the knowledge that Bo Vine is a clever cow and a simple encryption would be beneath him, they concluded that to decrypt the message, they have to determine whether the parentheses are correctly nested. As an example, in the sequence { a [ ] ( m, ) ] bb }, the parentheses are NOT properly nested. Knowing this information, the Big-White Monkey can calculate the exact day that the cows will attack, using algorithms known only to the MIT species.

Input Specification

The first line of input contains a single integer, , indicating the number of test cases.
Each test case consists of a single line of text of at most characters.
Note that the only legal parentheses are: (, ), [, ], {, }, <, >.

Output Specification

A single word, TRUE or FALSE indicating whether parentheses are properly nested or not.

Sample Input

5
Blah
Iggity (piggity) jiggity
/*/uu(((laksd[]{}{{()}}))^^\$)
Emoticons are fun =o)
Pr(x < 3) + Pr(x >= 3) = 1.

Sample Output

TRUE
TRUE
TRUE
FALSE
FALSE