Introduction
This consists of just one problem as a Part B. In addition to the requirements for the Java problems, you must observe the following requirements (for all homework submitted in this course):
- All programs should be literate, i.e., easily understandable by a human (say, your grader) and follow the Java Style Guidelines for CS112 posted on the class web site;
- All files for this homework should be submitted using WebSubmit, following the instructions on the class web site;
- You may not use data structure libraries such as ArrayList, since we are learning to write Java from the ground up and you must learn how these libraries are built; however, you are free to use (unless specifically directed otherwise) the basic libraries String, Character, Scanner, and Math; for this assignment, you may also use
Double.parseDouble(....); - You may freely use code from the class web site, the textbook, or lecture (unless specifically directed otherwise) as long as you cite the source in your comments; but you may NEVER use code from the web or other students’ programs—this will be considered plagiarism and penalized accordingly.
Problem B.1: YAC (Yet Another Calculator)
This problem will be an exercise in hierarchical linked lists and in recursive evaluation of arithmetic expressions. There is not all that much coding to do (my solution added less than 50 lines of code to the template), but you will need to understand how to represent expressions using hierarchical or nested linked lists. As I explained in lecture, this is how Python and many other interpreted languages represent programs, and it is an important way to think about representing data and algorithms.
The primary data structure will be hierarchical linked lists, as described in lecture on Tuesday 10/25. As explained at that time on the board, an expression will consist of three different kinds of nodes, for operators (*, +, -, and /), positive numbers (doubles), and expressions (nested, fully-parenthesized expressions). For example, an infix expression such as
( ( 3.4 + 0.0 ) * ( 1.2 - 2.3 ) )
which can equivalently be represented in prefix form as
*( +( 3.4, 0.0 ), -( 1.2, 2.3 ) )
Representing Arithmetic Expressions by Hierarchical Linked Lists
There are three different kinds of nodes in such a hierarchical list, all represented by different configurations of Node objects:1
2
3
4
5
6
7
8private static class Node {
String op;
double num;
Node exp;
Node next;
..... constructors and toString() ......
}
Operator Nodes represent one of the four arithmetic operators *, +, -, or / and have an op field storing the operator as a String.
Note that the num field, a double, has to have some value, and since it is meaningless in this kind of node, we give it the default value 0.0; similarly, the exp field is not used, and is assigned null. The next field, as we show below, will point to null when the operator is pushed on the Ops stack and point to the two operands of the operator when it is part of an expression.
Expression Nodes are placeholders for expressions, and have default values for op and num, and a pointer to an operator node which starts a subexpression.
Therefore, it is easy to tell which kind of node is being represented:
- Operator nodes have a non-empty String in the op field, a 0.0 in the num field, and a null pointer in the exp field;
- Number nodes have an empty String in the op field, a double value in the num field (could, of course, be 0.0), and a null pointer in the exp field; and
- Expression nodes have a non-null pointer in the exp field.
Each of these nodes may have a next field which is null or non-null, depending on context (see below for examples).
Arithmetic Expressions as Hierarchical (Recursive) Lists
Arithemetic expressions are recursively defined. As Strings they are defined by:
An operator is either
"*" or "+" or "-" or "/"
An expression is either
- a String representing a double or
- “(“ + expression + operator + expression + “)”
As a hierarchical linked list, an expression is either a
- number node, or
- a three-node list consisting of an operator node pointing to two nodes which are either number nodes or expression nodes pointing to an expression.
Some examples will perhaps clarify this idea. A single double
2.3
The more complex example was given at the beginning of the assignment. The most important thing to realize is that the two nodes following an operator node can either be numbers or expression nodes pointing (recursively) to subexpressions.
Building Hierarchical Lists from Strings
The template code Yac.java contains a parse( ... ) method which returns a list of tokens; it is slight variation of the method from HW 06, changed to account for doubles and the full set of four arithmetic operators. You will also need the generic Stack class we used in HW 06; here is the version, with a toString() method, which I used to produce the trace in the Appendix::Stack.java. The template also contains a Node class with various constructors and a toString() method which will print out individual nodes or full expressions. (Do not change the parse method and do not change the definition of the Node class unless you really know what you are doing.)
You must provide the methods build( ... ) and eval( ... ). This section describes the algorithm for the former, to be used for converting a String into a hierarchical linked list, using a variation of the two-stacks method from HW 06.
If you look at the algorithm from HW 06, you will see that it evaluates the expressions by storing the operands on one stack and the operators on another. In this variation of that algorithm, we will store single operator nodes, e.g.,
on the operator stack, and expressions on the operand stack. Note that the next pointer is null because this is a single operator (temporarily). The pseudo-code for this algorithm is as follows:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26public static Node buildExpression(String inputExpression) {
Stack<Node> Ops = new Stack<Node>();
Stack<Node> Exprs = new Stack<Node>();
String[] tokens = parse(inputExpression);
for each token t in the list tokens:
if t is a left parenthesis
do nothing
else if t is an operator
create a single operator node (with next pointing to null)
and push it on the Ops stack
else if t is a right parenthesis
pop the Exprs stack twice to get the expression lists or number nodes; if they are lists (start with an operator),
add an expression node on top to point to it
pop the Ops stack to get the operator node
onstruct the new expression out of the subexpressions
push the new expression list on the Exprs stack
else (it must be a String representing a double)
use Double.parseDouble(....) to turn the token t into a double
create a number node and push it on the Exprs stack
At the end, pop the Exprs stack and return the hierarchical list stored there.
}
Evaluating Hierarchical Lists
You must also write a method eval( ... ) which takes a pointer to a hierarchical linked list, and returns a double which is the result of the expression represented by the hierarchical list. This method must be recursive, does not use a stack, and is actually fairly simple if you understand the recursive structure of the lists:1
2
3
4
5
6
7
8eval(Node e) {
if e is a number
return the number
else if e is an expression (the first node is an operator)
evaluate the subexpressions recursively and return
the result of applying the operator to the values of the subexpressions
}