Assignment 1. CS330 Programming Languages, Summer 2004

Simplifying binary circuits with variables (5% of grade)

Assignment Description

PLEASE READ CAREFULLY - MISSING
LITTLE DETAILS MIGHT COST YOU


In this assignment the task is to write a program that reads a specification
of a binary resistance circuit with variables in prefix notation and outputs
a simplified version of the same circuit in infix notation.

The input to your program will be a text file where each line contains
a specification of a particular circuit in prefix notation. The output
will be a file containing the original circuit and the number of constants
in that circuit followed by the corresponding simplified version of the circuit
in infix notation with the possibly reduced number of constants.

Circuits are built recursively from resistors or circuits by serial
or parallel composition. We use the symbol  |   to denote
parallel composition and the symbol - to denote serial composition.

For example the following circuit can be written as follows:

(infix notation)         (1.0 | 0.25) - 1.5

Assignment 1 diagram
FIGURE 1


We could combine two of the above circuits in series as follows
((1.0 | 0.25) - 1.5) - (1.0 | 0.25) - 1.5))

The input to your program consists of circuit specifications in prefix notation (one specification/line)
In prefix notation the circuit of figure 1 would be written:
- | 1.0 0.25 1.5


Circuits can also contain variables which are strings that start with a non-digit character.
For example:
- | 1.0 0.25 foo

is a valid circuit.

The simplification is done by recursively calculating the total resistance when both
operands are numbers. Suppose c1 and c2 are two circuits with resistances r1 and r2
respecitvely. The resistance of a serial combination of c1 and c2 is r1+r2, and the
resistance of a parallel combination of c1 and c2 is given by the formula: 1 / (1/r1 + 1/r2).
So for example:
| - 1.0 2.0 x
can be simplified to:
| 3.0 x
or (3.0 | x) in infix notation. The simplification must be done recursively so that for example:

- x - - 1.0 2.0 - 3.0 4.0
is simplified to
- x 10.0

Infix notation should be obvious and the number of constants is how many numbers
are there in the circuit. For example the following circuit
- x - - 1.0 2.0 - 3.0 2.0
has 4 numbers
and the circit:
- x 10.0
has 1 number.

Input file conventions: whitespace (one or more spaces) separates each number and
operator (the | and - symbols). For example
- 0.5 0.5
is a valid input line but
-0.5 0.5
is not because there is no whitespace between - and 0.5. Each operator (-,|) takes
only two arguments. The following expression is not correct (three operands).
- 0.5 0.5 0.5
You can assume that the input is in the correct format so there is no
need for error handling on the input. All input numbers can be assumed to be positive and greater than 0

Here is an example input file and the corresponding
output file:

inCircuits.txt
outCircuits.txt

Make sure you try other test cases in addition to these examples.

Practical matters 

You may use any programming language you want. You must submit the full
source code plus a README.txt file describing how to compile and run your
program. I have a preference for commandline compilers but if you are
using some programming environment such as Visual Studio you are welcome to
do so. If you do so then I would like an executable version of your code IN ADDITION
to the source code for any of the following operating systems (Windows, Linux or OS X).

WARNING if the executable doesn't correspond to the source code provided then you will
fail the assignment completely even if it works perfectly. There might
be other consequences so DON'T EVEN THINK about giving the wrong executable.
The executable should take as arguments the names of the input and output file.
For example I should be able to run it as:

circuit inCircuits.txt outCircuits.txt

If you are using a standard widely available tool such as gcc or javac then you
can provide just the source code with instructions of how to compile it.

Check the course web page for submission instructions (should be
similar to the web submission system you have used for
other courses) and if you run into problems email me and we will figure it out.

Late assignment policy:  If the assignment is submitted
within three days from when it was due, you will get half the grade you
would get if you had submitted on time. You will not be able
to submit after three days. (exceptions to this rule only
if you have a VERY important reason).

IMPORTANT: The careful design and documentation (i.e comments) of
your code will be important factors in your grade. If there is a bug
it's better to report it than hide it. Be honest, precise and clear and
you shall be rewarded. NEVER (at least in this class) sacrifice
clarity for efficiency of execution.

IMPORTANT: If you have a hard time writing or understanding
this assignment then you will probably find CS330 is most likely
too advanced for you and will require extra effort and time.