^CSE2304^
Practicals 1(A) and 1(B), CSE2304, CSSE, Monash, Semester 1, 2005
The practical problems are available online via the unit home page.
The [on-line] practical problems
may include [links], corrections and supplementary material and
are to be taken as the reference documents.
Check the on-line material regularly.
Student:
You must prepare your solution to
this programming exercise in advance
(a 6pt subject => 12-hours work per week, every week).
The designated platform, on which your solution must be demonstrated and on
which it will be marked, is
the `gcc' compiler
running on `Linux'.
If you develop a solution on another platform,
it is your responsibility
to ensure that it works correctly on the designated platform.
Read the information on the practical-work guide,
C and code modularity, missed practicals
and plagiarism on the
[home page].
It is better to have a program that
solves only part of the problem but compiles and runs
rather than to have a more complex program that
crashes or, even worse, does not compile.
So keep copies of old working partial solutions.
Practical work
is marked on the performance of your program
and also on your understanding of the program.
I.e. Perfect program with zero understanding => zero marks!
"Forgetting" is not an acceptable explanation for
lack of understanding.
Unless otherwise noted, you must write all the code yourself, and
may not use any external library routines, the usual I/O (e.g. printf)
and mathematical (e.g. log) routines excepted.
NB.
Remember that each week's practical group is set its own specific problem.
Make sure that you do the correct problem for your week!
You will get zero marks if you solve the wrong problem.
The exam, and the practical work, are both hurdles (half-marks)
for the subject.
If you fail one, or the other, or both, the highest mark that
you can get for the subject is 44%(N).
Demonstrators are not obliged to mark programs
that do not compile or that crash.
Time allowing, they will try to help in tracking down errors,
but they are not required to mark programs in such a state,
particularly those that do not compile.
Therefore keep backup copies of working partial-solutions (also see above).
Objectives:
This practical is about recursion and
manipulating trees (partly revision of 1st year).
It uses a parser. It is not about parsing.
(However it might be useful re cse2303 which does teach parsing later.)
Note the use of procedures (functions) as parameters in the code.
It is also a useful exercise to modify someone else's program,
a very common task in a job.
All Groups: In
[...../tildeProgLang/C/Wff/]
are a few files that together make up a parser
for "well formed formulae" (wff), that is expressions
in propositional logic (Boolean algebra).
Take a copy of all the *.c and *.h files and
put them in a new directory (folder).
Read the source code, compile the program,
e.g. using `gcc *.c', under Unix (Linux), run it and try example inputs.
You will modify wff.c and add one new file.
Do not modify the other files.
Write a new function
Wff leftist(Wff), in a file leftist.c of its own,
to take the tree produced by the parser
and return a modified tree in
which all "and" and "or"
operators in the tree have been made fully left-associative, i.e.
- The tree of t1 and (t2 and t3)
-> the tree of (t1 and t2) and t3.
- The tree of t1 or (t2 or t3)
-> the tree of (t1 or t2) or t3.
- Note that t1, t2 and t3 can contain
ands and ors!
Call your routine from the main program, in wff.c.
Use the given WriteWff
function to output the original and the modified trees.
Marking
Does not compile or crashes
--> 0 to 2/6 marks.
Works on simple examples, performs the task for some but not all operators
in complex examples
--> 3 or 4/6 marks.
Works fully on all complex examples
--> 5/6 marks.
As above plus well tested (with evidence), documented and understood
--> 6/6 marks.
Write a new function
Wff implied(Wff), in a file implied.c of its own,
to take the tree produced by the parser
and return a modified tree in
which all implies (=>) operators are replaced
and in which all negation (not) operators have been moved
as close as possible
to the leaves (variables) of the tree using these rules:
- The tree of t1 => t2
-> the tree of (not t1) or t2.
- The tree of not(t1 and t2)
-> the tree of (not t1) or (not t2).
- The tree of not(t1 or t2)
-> the tree of (not t1) and (not t2).
- The tree of not not t
-> the tree t.
- Note that t1 and t2 can contain =>s,
ands ors and nots!
Call your routine from the main program, in wff.c.
Use the given WriteWff
function to output the original and the modified trees.
Marking
Does not compile or crashes
--> 0 to 2/6 marks.
Works on simple examples, performs the task for some but not all operators
in complex examples
--> 3 or 4/6 marks.
Works fully on all complex examples
--> 5/6 marks.
As above plus well tested (with evidence), documented and understood
--> 6/6 marks.
© 2005 L. Allison,
School of Computer Science and Software Engineering,
Monash University, Australia 3800.
Created with "vi (Linux & IRIX)", charset=iso-8859-1