Assignment 1. CS330 Programming Languages, Summer 2007
A simple spreadsheet with automatic updates (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 is a
simplified version of the back-end of a spreadsheet like Microsoft
Excel. The original computer spreadsheet (Visicalc) as one of the
greatest innovations in computing and transformed the market for
personal computers. You can read more about it in
http://en.wikipedia.org/wiki/Visicalc. There are several
simplification we will make in order to make the assignment manageable
but some of the main challenges will remain.
The first simplification is that our spreadsheet will be 1 dimensional.
It will consist of a row of cells where each cell can be either empty,
a real number, a string or a formula. There will be no graphical user
interface and the input to your program will consist of a text file
with a sequence of instructions for updating the spreadsheet. The
output of your program will be a text file with the updated spreadsheet
after each input instruction.
The input instructions have the form:
cell-specification => cell-number
For example:
5.0 => 0
sets the cell with number 0 to the value 5.0.
hello => 5
sets the cell with number 5 to the value hello.
The spreadsheet is printed by showing the value of each cell separated
by the | character. Any cells that have not been assigned are EMPTY and we only print up to the
last non-empty cell. For example the spreadsheet output after the two
instructions above will be:
5.0|
5.0|EMPTY|EMPTY|EMPTY|EMPTY|hello|
Numbering of cells starts from zero.
- Part 1 (2pts) : Implement a
1-dimensional spreadsheet that takes as input a text file with
instructions and produce a text file with the corresponding output for
each instruction
Example Input
File:
5.0 => 0
3.0 => 1
hello => 4
Corresponding
Output File:
5.0|
5.0|3.0|
5.0|3.0|EMPTY|EMPTY|hello|
The spreadsheet also will have formulas which for now will only be two:
sum and prod. For now each formula is applied to two cells specified by
their corresponding indices. When the spreadsheet is printed the cell
with the formula is printed as the value of the formula when applied to
the two corresponding cells. Cells with strings are ignored when
evaluating formulas. For example the instruction: sum 0 1 => 3 is
interpreted as sum cell number 0 and cell number 1 and store the result
in cell number 3.
- Part 2 (2pts): Extend your
spreadsheet to support formulas without automatic update.
Example Input
File:
5.0 => 0
3.0 => 1
hello => 2
sum 0 1 => 3
sum 1 2 => 4
prod 0 1 => 5
4.0 => 0
Corresponding
Output File:
5.0|
5.0|3.0|
5.0|3.0|hello|
5.0|3.0|hello|8.0|
5.0|3.0|hello|8.0|3.0|
5.0|3.0|hello|8.0|3.0|15.0|
4.0|3.0|hello|8.0|3.0|15.0|
Notice that the last instruction updates cell 0 but the formula values
remain unchanged. The last part of the assignment and the most
difficult one is to provide automatic updates of the formulas i.e when
a cell is updated any formula that contains that cell should also be
updated. This should happen recursively if a cell of a formula contains
another formula.
- Part 3 (1pts): Extend your
spreadsheet to support formulas to support automatic updates.
Example Input File
5.0 => 0
3.0 => 1
sum 0 1 => 2
sum 1 2 => 3
6.0 => 5
hello => 4
3.0 => 0
prod 0 1 => 6
sum 3 4 => 7
prod 3 4 => 8
Example Output File
5.0|
5.0|3.0|
5.0|3.0|8.0|
5.0|3.0|8.0|11.0|
5.0|3.0|8.0|11.0|EMPTY|6.0|
5.0|3.0|8.0|11.0|hello|6.0|
3.0|3.0|6.0|9.0|hello|6.0|
3.0|3.0|6.0|9.0|hello|6.0|9.0|
3.0|3.0|6.0|9.0|hello|6.0|9.0|9.0|
3.0|3.0|6.0|9.0|hello|6.0|9.0|9.0|9.0|
- Part 4 (0pts but good for you) : Think about how you could extend
the spreadsheet in various ways and how you would implement such
extensions. Examples support for more formulas, formulas with arbitrary
number of cell numbers as arguments, 2D spreadsheet, etc.
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:
spreadsheet in.txt out.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.