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

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

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

### Overview:

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.

### Goals:

By the end of this lab, you should
• Be able to use an `interface`
• Understand inheritance even better than you do already
• Know how to walk the branches of a tree
• Understand Reverse Polish Notation (this is not a joke)

### Before Starting:

• Read over this entire document before you start.
• Look at the JavaDoc, as it contains detailed information about the classes and methods for this lab.
• Study examples given in class.
• Run the sample solution.
Zip contains:
``` Lab9.java Startup.java VisualizedStackOfNodes.java KeyPad.java Calculator.java Node.java ```

### 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:

• Entering an integer into the immediate field by clicking digit buttons. By default, this value is 0.
• Pushing the immediate value onto the Stack
• Popping and discarding (dropping) a value from the Stack
• Swapping the order of the top two most recently pushed values on the stack.
• Performing addition, subtraction, multiplication, division on the top two variables on the Stack. The operand to be popped first should be on the right of the operator, and the operand popped second should be on the left.
• Displaying the expressions resulting from using operators (+ - * /) in the following forms:
1. Infix: `((4-5)+3)`
Infix is the common algebraic representation for a mathematical expression.
An expression in Infix is formatted as follows: `(operand1 operator1 operand2)`. Expressions in parentheses can be nested, for example `((operand1 operator1 operand2) operator2 operand3)`. Parentheses are required to determine the order of operations.
2. Postfix: `4 5 - 3 +`
Postfix is used as the order of entry into a stack-based calculator.
An expression in Postfix is formatted as follows: `operand1 operand2 operator1`. Expressions can be nested, for example `operand1 operand2 operator1 operand3 operator2`. Parentheses are not required because the number of operands an operator takes is known.
3. Prefix: `+ - 4 5 3`
Prefix is simply another way to represent a mathematical expression.
An expression in Prefix is formatted as follows: `operator1 operand1 operand2`. Expressions can be nested, for example `operator1 operator2 operand1 operand2 operand3` The number of operands that an operator takes is known, so parentheses are not required.
4. Elisp: `(+ (- 4 5) 3)`.
An expression in Elisp is formatted as follows: `(operator1 operand1 operand2)`. Expressions can be nested, for example `(operator1 (operator2 operand1 operand2) operand3)`. You will notice that the elisp format is very similar to prefix, except for with parentheses. Parentheses are required to determine an operator from an operand (the first thing after an opening parenthesis is always an operator, every other thing before a closing parenthesis is an operand).
Elisp is a programming language that originated from Lisp. Many of the extensions written for the Emacs text editor, including the JDE, are written using Emacs Lisp, or Elisp for short. Emacs can even evaluate Elisp code on the fly. To test this capability, switch to the *scratch* buffer, enter (+ (- 4 5) 3), put the cursor after the closing ) and hit ctrl-x ctrl-e. The number 2 should pop up in the minibuffer below. You can learn more about programming in Elisp at the GNU Emacs Lisp Reference Manual page.
• Evaluating the displayed expression into an integer and displaying the result.

### Design

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:

• `int getValue()`
Returns the integer value of the node.
• `String toString()`
Returns the String representation of the `Node`. If the `Node` is a `Constant`, a string containing the integer value of the constant is returned. If the node is an operator, for example `Addition`, a "+" should be returned.
• `int getNumChildren()`
Returns the number of children this Node has. Children are a Node's branches. To visualize this concept, think of a tree drawn upside-down. A junction of branches is a node. The branches going down are children.
• Node getChild(int n)
Returns the Nth child. 0 is the first child.

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`.

• A `Constant` has the following properties: Its constructor takes an integer. Its `getValue()` returns the value this `Constant` was constructed with. Its `toString` returns the value of the constant as a `String`, for example "5". It has 0 children, and when `getChild(int)` is called, `null` is returned.
• A `BinaryOperator` has the following properties: it is an abstract class. Its constructor takes two `Node`s, one to be on the Left of the operator, and one to be on the Right. (you may consider using the `protected` keyword to store these values) Each instance has eactly 2 children (hence the name `BinaryOperator`). Child 0 is on the Left, and Child 1 is on the Right. The BinaryOperator's `int getValue()` method is `abstract`. There are four subclasses of `BinaryOperator`: `Addition`, `Subtraction`, `Multiplication`, and `Division`, and each implments `abstract int getValue()` in its own appropriate way. Also, each implements `String toString()` to return a "+", "-", "*", "/", whichever is appropriate.

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 `Constant`s of values, for example, 5 and 6. Then create an `Addition` with those two `Constant`s. 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:

• A constructor that takes a Node. The argument node is the root of the tree you wish to display. For example, in the above schematic, the argument tree would be the Addition node.
• Methods called `inFix`, `postFix`, `preFix`, `elispFix`, with each one returning a String containing the propler representation of the tree. It is entirely up to you to figure out how these methods work. The specific formatting styles are given in the Problem Statement. This will probably be the hardest part of the lab.

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`.
• `VisualizedStackOfNodes` is a Stack class with the usual LIFO behavior. The special aspect of this class is that the stack it is holding is displayed on a DrawingPane. The stack is displayed upside-down, so that the most recently pushed items are at the bottom. For this reason, whenever the "bottom item on the stack" is mentioned in this lab, "most recently pushed item" is what is meant. The class works like this:
• The VisualizedStackOfNodes defaults to InFix notation when constructed.
• For each Node pushed, a new `ExpressionVisualizer` is created, and the String returned by that ExpressionVisualizer is put into a new StringComponent. The StringComponent is then added at the bottom of the DrawingPane, and all existing StringComponents are moved upwards to accomodate the new arrival.
• When the display notation is changed by calling one of the methods setInFix(), setPostFix(), setPreFix(), setElispFix(), each of the StringComponents on the DrawingPane is changed to contain the proper string.
• When a Node is popped, its StringComponent is removed from the DrawingPane and all of the DrawingPane's contents are moved down by a number of pixels.
• `KeyPad` represents a panel with buttons on it. The class has the following properties:
• A constructor that takes a Calculator (see below).
• a 310x210 DrawingPane containing all the clickable buttons.
• Whenever a button is pressed, a method in your `Calculator` class (see below) is called. The buttons on the panel and the methods they call in Calculator are as follows:  Button Name Method it calls in Calculator Digits 0-9 digit(int i) Clear clear() Reset reset() + plus() - minus() * multiply() / divide() Enter enter() Eval eval() Drop drop() Swap swap() Infix setInFix() Postfix setPostFix() Prefix setPreFix() Elispfix setElispFix()

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:

• The VisualizedStackOfNodes's DrawingPane is at the top of the window, the KeyPad's DrawingPane is at the bottom.
• Between them lies the Immediate field, into which the user enters digits to form an integer. By default (also after Clear and Reset), the value in the Immediate field is 0.
• The KeyPad calls methods in the Calculator indicating that the user wants some action to be performed. Each method does the following:  Method Name Action performed digit(int i) Add the given digit to the end of the Immediate integer clear() Clear the Immediate field to its default value reset() Empty the stack and clear the Immediate field plus() From the two bottom nodes on the Stack, create an Addition and push it onto the stack. In order of popping off the stack, the right operand comes first, then the left. If there are not enough nodes on the Stack, print an error and do nothing. minus() Similar to plus() multiply() Similar to plus() divide() Similar to plus() enter() Create a new Node containing the integer in the Immediate field and push it onto the Stack. Also, clear the Immediate field. eval() Remove the bottom Node from the stack, get its integer value, and push it onto the Stack drop() Discard the bottom value on the stack swap() Change the order of the bottom two Nodes on the stack setInFix() call setInFix() on the VisualizedStackOfNodes setPostFix() similar to setInFix() setPreFix() similar to setInFix() setElispFix() similar to setInFix()

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).

Hints:

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`.