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 |
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.
interface
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:
((4-5)+3)
(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.
4 5 - 3 +
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.
+ - 4 5 3
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 5) 3)
. (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).
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()
String toString()
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()
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
.
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.
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:
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.
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: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.
KeyPad
represents a panel with buttons on it. The class has the following properties:
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:
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() |
Hints:
ExpressionVisualizer
, return the toString of the constructor's Node argument for now.
BinaryOperator
for now too.
Constant
BinaryOperator
. You can't test this because it's an abstract class, so press
on.
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.
ExpressionVisualizer
.