Programming Lab #1:


Assigned: Thu 12 Feb 1998

Due: Thu 19 Feb 1998
New Due Date: Thu 26 Feb 1998


General description

For this project you will write a program which:

  • reads in an arithmetic expression in postfix syntax,
  • builds an expression tree using a stack,
  • prints the tree out in an "outline style", and
  • evaluates the expression using a recursive evaluator.
The basic ideas behind all of these tasks, some informative diagrams and much of the code, as well, are given in Section 11.2 of the Weiss text (p. 313 and following). There are basically three differences in this assignemnt from what is discussed in the text:
  1. I have decided not to require infix to postfix conversion (since the code to do this is given in the text, it would just be rote work to type it in);
  2. you will build a tree using a stack, rather than just compute the value of the expression;
  3. finally, you will have to print the resulting tree.
Note that you should handle the same set of operators and numbers as in the example in the book, but that you need not be concerned with issues of precedence or associativity, since expressions in postfix form are unambiguous.

Note also that you will not have to print the tree in a level-order fashion, using a queue, as we discussed in class: this would probably be too difficult for a first assignment. Instead, you are only required to print the tree in an indented outline style, using tabs and returns. Each node should be tabbed in as many times as it is levels deep in the tree, with the children of any given node printed below it. The left child of a node should be printed on the line immediately below that node, but indented one tab further, followed by the descendants of that child, then followed by the right child and its descendants. For example, the following tree would correspond to the output shown below: 

Input read:

  2 3 5 - * 4 +

Printed version of tree:

  +
    *
      2
      -
        3
        5
    4

Value of expression:

  0

For more details, see the various sections below.

Logistics

We will be using Symantec Cafe (Java) under Windows 95 for programming projects this semester. You should already be familiar with the use of this environment, either from a previous course or from self-study during the "lead time" that was granted during the frist few weeks of class. If you are not familiar with Java or Symantec Cafe, you may wish to pair up with a student who is.

Under such circumstances, it would be unwise for either party to allow the Java-knowledgable partner to dominate the coding aspects of the lab

Input, output and error-checking

I will provide sample input and output files in a class directory by this weekend; the sample given above should serve until then. You should write some of your own test inputs for debugging purposes in any case. For convenience, your program should be able to read and process multiple successive input expressions until, say, the end of the input stream is reached. If there is any sort of error in a given expression, you should note it and continue to read in more expressions. Errors you should catch include:

  • bad character in the input (e.g., "z");
  • too few operators (i.e., more than one operand left on the stack);
  • too few operands (i.e., attempt to pop an empty stack).

Note that I will be likely ask you to demonstrate your program on samples other than the ones provided in the directory mentioned above; be prepared.

Assessment

Your project will be assessed on the basis of both a "live" demonstration and a hard copy description and print-out of the project code. The printed version should specify both members of your group and should specifically mention any free late days used, remaining problems or bugs, special enhancements, etc. In addition to "raw code", you should include a brief introduction describing anything that is special in your approach to the problem (bugs, enhancements, etc., should also be mentioned here).

I will be available in lab on Monday mornings from 10:00 - 11:30 for demonstrations. You may also demonstrate at other times (Thursday morning office hours will likely be popular), including by appointment, but you must demonstrate your project and hand in your hard copy by the due date unless you receive a specific provision otherwise (see also the information about free late days on the syllabus).

You may work in groups of two; this is not an absolute requirement, but is strongly recommended. If you cannot find a partner, please see me and I will make arrangements.

Enhancements

Part of the goal of the programming projects in this course is to give you the opportunity to develop some significant programs, and thus to exercise both your design and coding skills. If you find that the assignment is not challenging enough and you wish to do some extra work, there are a number of things you could do to "add value" to the assignment, say for example printing out the infix version of the expression or (more ambitiously) drawing the tree in a graphics window.

In any case, no such enhancements are required: enhanced versions of projects may help your grade a bit, but you will have the opportunity to earn an "A" in the course even if you only meet the minimum assignment requirements.