PROB3: BUILD GATES

Make do without an OR gate

Your cousin Bill has a patented process that produces AND and NOT circuits very efficiently. Unfortunately, OR logic is very expensive. He offers to wash your laundry for the next year if you can fix the problem.

INPUT: prob3.dat

A sequence of logical expressions, one per line, which conform to the following grammar:

E := '!' E | '(' E '&' E ')' | '(' E '|' E ')' | V

V := 'a' | 'b' | ... | 'z'

Here the bold are nonterminals or parts of the BNF grammar, while the 'teletype' are terminals. Of course '!' is unary NOT, '&' is binary AND, and '|' is binary OR.

Other than end-of-line terminators marking the end of each expression, there will be no white space in the input file. Here's an example:

       column   111111111122222222223
       123456789012345678901234567890
line 1:x[EOL]
     2:(x&!(y|!z))[EOL]
     3:!(x|y)[EOL]
      :[EOF]

OUTPUT: prob3.out

For each expression in the input, you are to produce an equivalent expression in the output, i.e., one that gives the same truth value for all possible combinations of the input, but without using the '|' OR operation.

The generated expression must conform to the same grammar, with the same white space restrictions. A correct output for the example input would be:

       column   111111111122222222223
       123456789012345678901234567890
line 1:Program 3 by team 0[EOL]
     2:x[EOL]
     3:(x&(!y&z))[EOL]
     4:(!x&!y)[EOL]
     5:End of program 3 by team 0[EOL]
      :[EOF]