For the past 200 years, the Sphinx has asked the same riddle, and afterhaving devoured the thousands of passersby who failed to answer herquestion, she is incredibly bored. To relieve her monotony, the Sphinxdecides to try asking something a bit easier—a series of Booleanexpressions. Since each expression has only one solution—true orfalse—she figures that passersby will have a fairly good chance ofguessing the solutions, even if they do not actually know them.
The next day, Oedipus passes by the Sphinx on the road to Thebes.Being of peculiar intellect, he manages to answer the Sphinx’s initialBoolean expressions instantly. Suddenly feeling a resurgence of bloodthirstand fearing the loss of her once-impeccable reputation, the Sphinxdecides to stump Oedipus by using all four Boolean operators, alongwith parentheses and order of operations. Help save Oedipus from
The next day, Oedipus passes by the Sphinx on the road to Thebes.Being of peculiar intellect, he manages to answer the Sphinx’s initialBoolean expressions instantly. Suddenly feeling a resurgence of bloodthirstand fearing the loss of her once-impeccable reputation, the Sphinxdecides to stump Oedipus by using all four Boolean operators, alongwith parentheses and order of operations. Help save Oedipus from
Input Format
The first line of the input is an integer n that represents the number of data collections that follow where each data collection lies on a single line. Each line contains a Boolean expression of unspecified length. The uppercase characters T and F will be used in the Boolean expression to represent the terms true and false, respectively. The order of operations is as follows:() Evaluate the expression in parentheses first. Parentheses may be nested; evaluate from the most inner set of parentheses first.
! Evaluate the term immediately following the NOT operator according to the rules !T=F and !F=T
& Evaluate the terms immediately preceding and following the AND operator according to the rules T&T=T, T&F=F, F&T=F, and F&F=F
^ Evaluate the terms immediately preceding and following the XOR operator according to the rules T^T=F, T^F=T, F^T=T, and F^F=F
| Evaluate the terms immediately preceding and following the OR operator according to the rules T|T=T, T|F=T, F|T=T, and F|F=F
No characters beside TF()!&^| will appear in the lines of input.
Sample Input
3
F&T
!F
!T^F
Output Format
Your program should produce n lines of output (one for each data collection). Each line should contain one uppercase character, either T or F, indicating the result of evaluating the corresponding Boolean expression.
The output is to be formatted exactly like that for the sample output given below.
Sample Output
F
T
F
You must be logged in to submit a solution.