You will write a program truthtable, in C, that reads a circuit description and prints a truth table showing all combinations of input variables.

In all three parts, the program may be given the name of a ?le containing a circuit description as an argument. If a ?le name is not given, the program will read from standard input (stdin). Part 1 (40 points) For this part, the circuit descriptions will be sorted so that each temporary variable appears as an output parameter before any appearances as an input variable. Part 2 (20 points) For this part, the circuit descriptions will not be sorted, meaning that a temporary variable may be used as an input parameter before its use as an output parameter. Part 3 (Extra credit) For extra credit, extend truthtable to take an optional argument -h. If present, truthtable will print truth tables including a header giving the names of the input and output variables. For circuits with multi-character variable names, your program must include padding so that the columns are aligned.

Input - The input to your program will be a single circuit description using the language described in section 1. This circuit description may be provided as a ?le speci?ed as an argument to truthtable, or it may be provided to truthtable through standard input (stdin). You MAY assume that the input is correctly formatted and that no variable depends on its own output.

Output - The output of truthtable is a truth table showing each combination of inputs and the corresponding output for the speci?ed circuit. Each column in the table corresponds to a speci?c input or output variable, which are given in the same order as their declaration in the INPUT and OUTPUT directives. Columns are separated by a single space, and a vertical bar (|) occurs between the input and output variables.

For part 3, the output will include column headers giving the variable names when the -h option is present. Each column must be as wide as its variable name, with the 0 or 1 left-aligned. For example,

A Long | Nand

0 0 | 1

0 1 | 0

1 0 | 0

1 1 | 0

Usage -

$ cat circuit1.txt INPUT 3 : IN1 IN3 IN4 OUTPUT 1 : OUT1 MULTIPLEXER 2 : 1 0 1 0 : IN3 IN4 : temp1 MULTIPLEXER 1 : temp1 1 : IN1 : OUT1 $ ./truthtable circuit1.txt 0 0 0 | 1 0 0 1 | 0 0 1 0 | 1 0 1 1 | 0 1 0 0 | 1 1 0 1 | 1 1 1 0 | 1 1 1 1 | 1 $ cat circuit2.txt INPUT 2 X Y OUTPUT 2 Z W XOR X Y T PASS T Z NOT T W $ cat circuit2.txt | ./truthtable 0 0 | 0 1 0 1 | 1 0 1 0 | 1 0 1 1 | 0 1

For part 2, truthtable must handle unsorted circuit descriptions:

$ cat circuit3.txt INPUT 4 A B C D OUTPUT 1 Z AND A B E MULTIPLEXER 2 0 1 1 0 E F Z OR C D F $ ./truthtable circuit3.txt 0 0 0 0 | 0 0 0 0 1 | 1 0 0 1 0 | 1 0 0 1 1 | 1 0 1 0 0 | 0 0 1 0 1 | 1 0 1 1 0 | 1 0 1 1 1 | 1 1 0 0 0 | 0 1 0 0 1 | 1 1 0 1 0 | 1 1 0 1 1 | 1 1 1 0 0 | 1 1 1 0 1 | 0 1 1 1 0 | 0 1 1 1 1 | 0 For part 3, truthtable may take an option -h which adds column headers to the output: $ ./truthtable -h circuit1.txt IN1 IN3 IN4 | OUT1 0 0 0 | 1 0 0 1 | 0 0 1 0 | 1 0 1 1 | 0 1 0 0 | 1 1 0 1 | 1 1 1 0 | 1 1 1 1 | 1