CS 101 (Fall 2000)
Lab 9: Multiple Representations of Expressions

Author: Sergey Klibanov
Lab Assigned Design Due
(In class)

1 PM
(In Lab)
(In Lab)
Lab Due
(In class)
1 PM
6 Nov None 8-9 Nov 15-16 Nov 17 Nov


The word "computer" was originally spelled "computor" and it refered to humans who spent their time generating generating tables of numbers, such as sin(x) and cos(x). Issac Asimov once said that technology should strive to remove the dull, dangerous, and dirty jobs that humans must do. In this lab, you will create the inner workings of a stack-based calculator. Whereas in the olden days, computational software was all written in assembly and required punch cards for input, our computational software will be written in Java and have buttons for a nicer interface.


By the end of this lab, you should

Before Starting:

[[[ Download PC zip ]]]
Zip contains:

Problem Statement

In this lab, you will create a calculator that can evaluate expressions and display them in four different styles (infix, postfix, prefix, and elisp (pronounced e-lisp)). The expressions you calculator will manipulate and evaluate will be made of integers and the four common mathematical operations -- addition, subtraction, multiplication, and division. The calculator should support the following actions:


Look at the JavaDoc.

The most fundamental component of this lab is the expression tree that represents one mathematical expression. This tree is made up entirely of Nodes. A Node is an interface that has the following public methods:

The expression tree will be used by ExpressionVisualizer to produce a String representation of the tree. There are two classes that implement the Node interface, Constant and BinaryOperator.

Having created the above classes (it should be a breeze), you chould be able to create a mathematical expression tree and evaluate it correctly. You can create a mathematical expression by constructing two Constants of values, for example, 5 and 6. Then create an Addition with those two Constants. The getValue() of the Addition should return 11. Test all your classes in this way before moving on to the next step. Also, try to make a tree several levels deep. Here is a schematic of what a multi-level tree might look like for the expression ((7-5)+3):

The arrows represent references.

The class used to display this expression tree is aptly called ExpressionVisualizer. An ExpressionVisualizer has the following properties:

Test this class thoroughly. Make a *very* large expression tree (10+ nodes) and make sure each of the tree-walking methods works. Expect to spend the majority of your time debugging this class.

To help you in putting together a calculator, we will provide two classes. One of them is VisualizedStackOfNodes, and the other is KeyPad.

The class that pulls everything together is Calculator. The Calculator is responsible for creating the window, and plugging the KeyPad and VisualizedStackOfNodes together to finally make an RPN calculator. The following screenshot of the calculator points out important features:

The Calculator is organized as follows:

This lab may seem quite long to implement, so start early and implement classes in the order they are listed in the Design. Before you move from one stage of the Design to another, please thoroughly test your existing code. In this program, many things rely on each other to work, and finding an error as early as possible is the best way to solve problems.

What to turn in:

  1. Complete a code cover sheet.
  2. Provide a printout of any files you have modified (see approach below).
  3. Provide the transcript from your tests.

Suggested approach:

  1. Type in stubs for all classes not given to you, based on their JavaDoc spec. The stubs must have the right names for the methods and those that should return something must return something (null, a blank String, or some reasonable value).


  2. Your project should compile without error at this point. If it doesn't, do not proceed until it does!
  3. Implement and test Constant
  4. Your project should allow you to enter values now into the calculator.
  5. Implement BinaryOperator. You can't test this because it's an abstract class, so press on.
  6. Implement Addition. Now you can test and see whether addition seems to work. You won't see the expression in formula form, but push the eval button and the answer should show up.
  7. Press on with the other arithmetic nodes.
  8. Implement and test ExpressionVisualizer.

Last modified 20:54:47 CST 05 November 2000 by Ron K. Cytron