CS112-Yet-Another-Calculator

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 request 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 request 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 request, 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

1	( ( 3.4 + 0.0 ) * ( 1.2 - 2.3 ) )

which can equivalently be represented in prefix form as

1	*( +( 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:

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

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:

eval(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
}