CS-211 Fall 2017 Project 2 Due: Oct 22 29, 2017
Logic Simulation
Background
Most of you are electrical engineers, and very familiar with the concept of logical formulas like
“AB”. Wouldn’t it be cool if we could print out a truth table for some arbitrary logical formula?
For this project, you will write a program that takes the description of a logical formula as input,
and writes a truth table that shows all possible input values, and the value of the formula with
those values.
Project Description
For project 2, please write a C program called lsim.c that takes a single command line argument,
which contains the description of a logic formula. To make evaluation of this formula easier, we
will assume that the formula is expressed using “Polish Notation” or “Prefix Notation”. The
Wikipedia article on Polish Notation describes this in more detail. Our simulator will support
three different operators, “^” for logical and (that’s an uppercase 6 on my keyboard), “v” for
logical or (that’s a lowercase vee), and “~” for not or invert. (This is different than the symbols
used for and, or, and invert in C, but I intentionally made them different to avoid confusion.)
Our formula may also contain literals “0” for false, or “1” for true. Any other non-whitespace
character is treated as a variable name. For instance,“^AB” is the notation for “A B”.
Your program should, as always, check for the right number of arguments, and then save the
list of “variables” in the formula. I found it easiest to create global variables “vars”, an array of
variable names (each one character long), and a global “numVars” to keep track of how many
variables are in the list. Note that a variable may appear in your formula more than once, so
check to make sure it’s not already defined before adding it as a new variable. Your program
may assume that there are up to, but not more than 8 different “variables” in your formula. If
you find more, you should issue an error message and quit. (More than 8 is easy to support,
but the resulting truth tables are pages and pages long… and no one is likely to read them.)
Next, print out the header of a truth table. The first line of the header should start with a vertical
bar (|), followed by a blank, the first variable, and another blank, followed by a vertical bar,
followed by a blank, the second variable, and another blank, and so on, until all the variables are
printed. Then, print another blank followed by the user specified formula. The second line of the
header should have dashes (-) everywhere except under the vertical bars.
Under the vertical bars should be plus signs (+). For instance, if I run “./lsim ^AB”, then the
truth table header should print out:
| A | B | ^AB +-
--+---+----
To print out the remainder of the truth table, we need to determine all combinations of zeroes
and ones for the variables. The easiest way to do this is to remember that if there are n
variables, then the numbers 0 to (2n-1), expressed in binary, represent all the required
CS-211 Fall 2017 Project 2 Due: Oct 22 29, 2017
combinations. In C, a simple way of calculating 2n is to use a shift left…. 14 errors -60 points
Compiler warning messages -10 points
Illegible or Poorly formatted code Up to -10 points
Incorrect results -10 points per invocation (up to -40 points)
Late submission -10 points per every 24 hours late
Code matches another student’s code -100 points