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.
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:
(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 operand3The 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:
Node. If the
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.
The expression tree will be used by
ExpressionVisualizer to produce a String representation of the tree.
There are two classes that implement the
Constanthas the following properties: Its constructor takes an integer. Its
getValue()returns the value this
Constantwas constructed with. Its
toStringreturns the value of the constant as a
String, for example "5". It has 0 children, and when
BinaryOperatorhas the following properties: it is an abstract class. Its constructor takes two
Nodes, one to be on the Left of the operator, and one to be on the Right. (you may consider using the
protectedkeyword 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
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
Constants of values, for example, 5 and 6. Then create an
Addition with those two
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
The arrows represent references.
The class used to display this expression tree is aptly called
ExpressionVisualizer has the following properties:
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
VisualizedStackOfNodesis 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:
ExpressionVisualizeris 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.
KeyPadrepresents a panel with buttons on it. The class has the following properties:
Calculatorclass (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)|
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:
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()|
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.