package hw2; * Homework assignment 2: Expression trees * * The goal of this assi
ID: 3889431 • Letter: P
Question
package hw2;
* 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 constructor. 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<String> q = new ArrayDeque<String>();
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<String> 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<String> 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() + " ");
}
}
}
Explanation / Answer
import java.util.*; public class ExpTree { //-------data private ExpNode root; //-------constructor public ExpTree() { root = null; } //constructor where a string is passed in. It is parsed and stored public ExpTree(String expString) { //declare StringTokenizer, Stacks, and other variables used in parsing StringTokenizer tokenizer = new StringTokenizer (expString, "()+-*/%", true); String token; ExpNode operator, leftOperand, rightOperand; Stack operators = new Stack(); Stack operands = new Stack(); //break up expString into tokens while (tokenizer.hasMoreTokens()) { token = tokenizer.nextToken(); // if the current token is a left paren, ignore it if (token.equals ("(")) ; // if the current token is an operator, put it on the // operator stack else if ((token.equals ("+")) || (token.equals ("-")) || (token.equals ("*")) || (token.equals ("/")) || (token.equals ("%"))) operators.push (new ExpNode(token)); //if the current token is a right paren, pop the operators stack //to get the operator, pop the operands stack twice to get the two //operands (stored as expression trees). Then make the two operands //children of the operator and push back on the operands tree. else if (token.equals (")")) { operator = operators.pop(); rightOperand = operands.pop(); leftOperand = operands.pop(); operator.setLeft(leftOperand); operator.setRight(rightOperand); operands.push(operator); } //otherwise, the token should be a number - put it in the operands stack else operands.push (new ExpNode(token)); } // while (tokenizer.hasMoreTokens()) //when finished parsing, the operands stack should contain the fully-built //expression tree. if (!operands.isEmpty()) root = operands.pop(); } //-------methods //isEmpty() public boolean isEmpty() { return (root == null); } //printTree methods - prints the tree in RNL order, with indents. Called from "outside" public void printTree() { if (root == null) System.out.println("The tree is empty"); else printTree(root, 0); //start with the root with 0 indentations } //recursive, private version of printTree private void printTree(ExpNode subTree, int indents) { //if there is a right side, handle it first (with 1 more indent) if (subTree.getRight() != null) printTree(subTree.getRight(), indents+1); //then print the node itself (first move over the right amount of indents) System.out.println(" "); for (int i=0; iRelated Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.