package hw2;

/* CSC 301 Sections 402, 411, 701, 710 Fall 2017

* 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.

*

* The ArithExpr class has 5 methods. I have already written 2 of the methods.

* You must complete the other 3. Each of the 3 methods is worth 1 point,

* for a total possible score of 3 (meaning that the assignment is worth 3%

* of your cumulative grade for the course).

*

* 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 paren, indicating the start

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

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

}

// other than a left paren, the only other possiblity 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

}

}

package hw2;

/*

* CSC 301 Sections 402, 411, 701, 710 Fall 2017

*

* 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() + " ");

}

}

}

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());

}

}