First, enter the cs190m directory:
$ cd cs190m
Then, download lab07.zip into the cs190m directory. Run the following commands:
$ unzip lab07.zip $ cd lab07
Traditional arithmetic expressions that you see in math classes involve infix notation—that is, the operator (for example, +) is placed in between the two operands (e.g., 3 + 5). Reverse Polish notation, or RPN, uses postfix notation, where operators are placed at the end (3 + 5 becomes 3 5 +). One side effect of this is that the need for parentheses are eliminated. For example, you can represent (3 + 5) * (1 + 4) as 3 5 + 1 4 + *. More examples can be seen in the Lab07.java file.
There are 6 classes that you'll be working with, all of them ending in Expression. The Expression interface is given to you with only one declared method, which is evaluate. The other classes all implement the Expression interface. The class diagram looks like this:
Each class is explained below.
The Number class is the most simple of all of the classes. It simply represents one number as a double. This means that the evaluation of any Number is simply the number that is stored. Since this class is the simplest possible expression, it is mostly complete; you should modify the code to implement the Expression interface.
The ArithmeticExpression class represents an operation on two sub-expressions. These sub-expressions could be simply numbers, such as 3, or expressions, such as 3 + 5. This class is abstract and is inherited by four classes that represent addition, subtraction, multiplication, and division. All ArithmeticExpression classes hold one characteristic in common: there is a left and right operand. Thus, we can declare left and right variables of type Expression (already done for you). In this class, you should indicate that it implements Expression, but that the evaluate method will be implemented by inheriting classes.
The remaining four classes are very similar, so they will be covered together. In each class, you should:
The Lab07.java file provides a main method which you can test your method with. The string array exprs is the list of testcases; for each testcase, it transforms the string in RPN to an Expression object, evaluates the it, and prints it in infix notation. The transformation from RPN to Expression object is already given to you, as well as the infix notation in the form of toString methods. You are responsible for making sure that the evaluation is correct. The correct infix notations can be found in the testing file. A partial sample output is given below:
Parsing RPN expression: 5 1 2 + 4 * + 3 - Expression evalutes to: 14.0 Infix notation is: 5.0 + (1.0 + 2.0) * 4.0 - 3.0 Parsing RPN expression: 1 1 + 2 * 1 + 2 * Expression evalutes to: 10.0 Infix notation is: ((1.0 + 1.0) * 2.0 + 1.0) * 2.0 Parsing RPN expression: 3 5 + 1 4 + * Expression evalutes to: 40.0 Infix notation is: (3.0 + 5.0) * (1.0 + 4.0)
To turn in your lab:
$ cd ~/cs190m/lab07 $ turnin -v -c cs190m -p lab07 *.java
Many of you will probably run across problems while programming at some point during a lab. If that's the case, here are the resources you should use, in order:
Lab created by: Daniel Tang