Ensuring Truth

In this problem we will consider Boolean formulas written according to the following BNF grammar: ::= | "|" ::= "(" ")" ::= | "&" ::= | "~" ::= "a" | "b" | "c" | ... | "z" Each formula can contain up to 26 different Boolean variables, which are denoted by lowercase En- glish letters. We use the ampersand sign (“&”) to denote conjunction, vertical bar (“|”) for disjunction, and tilde (“~”) for inversion. The truth tables of these operators are shown below for your reference. xyx&y xyx|y false false false false true false true false false true true true false false false false true true true false true true true true x ∼x false true true false A formula is called satisfiable if it is possible make the formula evaluate to true. Input to assign values to its variables in such a way as to The first line of the input file contains an integer T (1 ≤ T ≤ 5000). Each of the next T lines contains a Boolean formula. You can assume that the formulas will strictly follow the grammar specified above, and will not be longer than 250 characters. Output For each formula, you should determine whether it is satisfiable, and output a line ‘YES’ if yes, it is, and ‘NO’ otherwise. Sample Input 2 (a&b&c)|(a&b)|(a) (x&~x) Sample Output YES NO