To complete this assignment, you will complete the ExpressionTree class. An ExpressionTree object is meant to represent an arithmetic expression. For our purposes, an arithmetic expression consists of one of the following:

a number; or

an arithmetic expression, followed by an operator (well only use +, , and *), and a second arithmetic expression.

Note that the definition is recursive; that is, an arithmetic expression can be part of a larger expression. You may assume that each item in the expression is separated by other items with a whitespace. Each arithmetic expression, with the exception of a number, must be surrounded with parentheses. Here are some examples of valid expressions:

( 1 + 2 )

10

( ( 2 * 4 ) 3 )

( ( 1 + 2 ) + ( ( 6 4 ) * 5 ) )

These are invalid expressions:

1 + 2

( 1 + 2 + 3 )

The expression should be represented as a binary tree. The operator of the expression is the root, and the left and right children are the expression to the left of the operator (the left child) and the expression to the right of the operator (the right child). For example, the tree which should represent ( ( 1 + 3 ) * ( 2 + ( 4 2 ) ) ) is the following; The ExpressionTree class has 4 public methods: 2 public constructors (overloaded), a toString method, and an evaluate method. There are also 2 helper (private) methods: a third constructor, and a method called getExpr. You must write (1) the toString method; (2) the evaluate method; and (3) the getExpr method. Here is a description of each of the 6 methods in the ExpressionTree. I.

Constructor #1: I am providing you the complete code for this method. This constructor is passed 3 values: a String and two ExpressionTree objects. The String is stored in the item instance variable, and the 2 ExpressionTree objects are stored in the left and right instance variables, respectively. You may not need to call this constructor in the code that you write, but I will use it in my test code. II.

Constructor #2: I am providing you the complete code for this method. This constructor is passed 1 value, which is a String. The String represents an arithmetic expression. This constructor breaks apart a String into tokens (substrings) as delimited by whitespaces, using the split method of the String class. The tokens are then placed in a Queue, in which the first token is at the front of the queue. In Java, the class that we are encouraged to use for Queues is called ArrayDeque. In the ArrayDeque class, the enqueue operation is called offer, and the dequeue operation is called poll.

Constructor #3: I am providing you the complete code for this method. This version of the constructor is passed an ArrayDeque, and forms an expression tree by repeatedly polling tokens from the ArrayDeque until an arithmetic expression can be formed from those tokens.

The toString method: You must write this method. It is passed no parameters, and returns a String, which represents the expression tree rooted by the given ExpressionTree object. For example, referring back to the diagram above, if t is the name of the root, then t.toString() should produce ( ( 1 + 3 ) * ( 2 + ( 4 2 ) ) ). In general, if s is a String, then if we call new ExpressionTree(s).toString(); the result is the original string s.

The getExpr method. You must write this method. It is passed the queue created by the constructor. When completed, it must create a tree representation of the next sequence of tokens on the queue which form an arithmetic expression. It should do this by dequeuing Strings from the queue (the Java method is called poll) until it has reached the end of the next arithmetic expression on the queue. For example: if the Queue contains (from front to back) ["(", "1", "+", "2", ")"] Then the Queue should be polled 5 times, since the 5th poll will return the ) indicating the end of the expression. In general, there may be additional items on the Queue after the first regular expression is found (after the ")").

An evaluate method, which returns an int (the value of the expression). For example, evaluate from the above tree should return 16.

package hw2;

Template

* Homework assignment 2: Expression trees

* The goal of this assignment is to give you practice in

* working with "expression trees". In this implementation,

* expression trees are represented with the ArithExpr class.

* An expression tree is a binary tree (but NOT a binary search tree)

* in which:

* Each ArithExpr object contains an item. The item is either:

* --- a number (but as the form of a String), or

* --- an arithmetic operator (we'll limit ourselves to "+", "-", or "*")

* If the item is an operator, the ArithExpr object also contains left

* and right children, which themselves are ArithExpr objects.

* Here are the methods:

*

* 1. A constructor which is passed a String. Some examples: "1", or "( 1 + 2 )" or

* "( ( 1 + 2 ) + 3 )" etc. Note that each token in the String is separated

* by other tokens with " ", making it easy to use the String's split method.

* This constructor should split the string, create a queue, and enqueue

* each of the items (substrings) from the parameter string.

* It should then call a "helper" method (private) called getExpr, as

* described below. The constructor should build a tree consisting of

* ArithExpr objects, which correspond to the overall arithmetic expression and

* its parts. For example,

* ArithExpr Expr = new ArithExpr("( ( 1 + 2 ) + 3 )") should create a 3 objects

* in total:

* -- 3 ArithExpr objects (leafs of the tree) which represent "1", "2", and "3"

* -- 1 ArithExpr object which represents "( 1 + 2 )"

* -- The root of the tree, which is an ArithExpr object representing the

* entire arithmetic expression. The root's item is "+", its left

* child is the 2nd ArithExpr object, and its right child is the leaf which

* represents "3".

* This tree can be illustrated with the following diagram:

* +

* / \

* + 3

* / \

* 1 2

*

*/

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.Scanner;

import java.util.ArrayDeque;

import java.util.Queue;

public class ArithExpr {

private static final int START=0, LEFT=1, RIGHT=2, END=3;

private String item;

private ArithExpr left = null, right = null;

/*********************************************

* I AM PROVIDING YOU WITH COMPLETED CODE FOR

* THE THREE CONSTRUCTORS BELOW.

*/

/*

* A basic construtor. You may not call this in your

* code, but I call it in my test file.

*/

public ArithExpr(String item, ArithExpr left, ArithExpr right) {

this.item = item;

this.left = left;

this.right = right;

}

/* The next constructor is passed an arithmetic expression

* in the form of a string, and converts it to an expression

* tree. It uses the split(" ") method of the string class,

* which will produce an array of Strings (substrings

* of expr). Then create a Queue (this is called

* an ArrayDeque in Java) and enqueue each string in

* the array produced by split. The enqueue operation

* in Java is called "offer". The process the queue by

* calling the getExp helper method (which I have already

* written).

*/

public ArithExpr(String expr) {

Queue q = new ArrayDeque();

for (String s : expr.split(" "))

q.offer(s); // "offer" is Java's name for "enqueue"

getExpr(q);

}

// another constructor which you may wish to make use of

// in code you write below. If you end up not using it,

// you may delete the method from your code.

public ArithExpr(Queue q) {

getExpr(q);

}

/*

* YOU MUST WRITE THE getExpr METHOD.

*

* It is a "helper" method (note it is private) since

* assists one of the constructors. When completed,

* it should repeated poll the queue until it has

* enough tokens to build an expression tree.

*/

private void getExpr(Queue q) {

String next = q.poll(); // "poll is Java's name for "dequeue"

// next is either a left parenthesis, indicating the start

// of a new arithmetic expression, or it's a number.

if (next.equals("(")) {

//build left subtree

//operator is next on the queue

//build right subtree

//")" is next; dispose it by q.poll()

}

// other than a left parenthesis, the only other possibility is a number

else {

}

}

/*

* YOU MUST WRITE THE toString METHOD. It should return a String

* which represents the expression tree.

*

*/

public String toString() {

return ""; // replace this

}

/*

* YOU MUST WRITE THE evaluate METHOD. It should return the value

* of an expression tree. The value should an integer, since we

* are assuming that the arithmetic expressions consists of integers

* and +, - , *. The results of applying these operators will also

* be integers.

*

*/

public int evaluate() {

return 0; // replace this

}

}

Test code 1

package hw2;

/*

* Some tests cases for HW 2

* This tests your code on just a few examples of arithmetic expression as

* they are specified in the assignment. Once you have properly completed

* the ArithExpr class, the output of this should be something like:

1

1

1

( 1 + 2 )

[ + 1 2 ]

3

( ( 1 * 2 ) + 3 )

[ + [ * 1 2 ] 3 ]

5

( 1 + ( 2 * 3 ) )

[ + 1 [ * 2 3 ] ]

7

( ( 4 - 2 ) * ( 1 + 2 ) )

[ * [ - 4 2 ] [ + 1 2 ] ]

6

*/

public class HW2Test1 {

public static void main(String[ ] args) {

String [] tests = {"1", "( 1 + 2 )", "( ( 1 * 2 ) + 3 )",

"( 1 + ( 2 * 3 ) )", "( ( 4 - 2 ) * ( 1 + 2 ) )"};

for (String t : tests) {

System.out.println(t);

ArithExpr expr = new ArithExpr(t);

System.out.println(expr);

System.out.println(expr.evaluate() + " ");

}

}

}

Test code 2

package hw2;

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

public class HW2Test2 {

public static void main(String[ ] args) {

System.out.println("Type an arithmetic expression:");

BufferedReader r = new BufferedReader(new InputStreamReader(System.in));

String input = "0";

try {

input = r.readLine();

} catch (IOException e) {

// TODO Auto-generated catch block

e.printStackTrace();

}

ArithExpr expr = new ArithExpr(input);

System.out.println(expr);

System.out.println(expr.evaluate());

}

}

UPDATE: Use recursion. call ArithExpr(Queue q) in getExpr method.