Expression Trees

Assignment

 importjava.util.ArrayList;

importjava.util.Iterator;

importjava.util.Scanner;

// import java.util.Stack;   // You will probably want to make use of this

// Homework Y:  Expression trees.

// In the project you need to code one class that extends the abstract class ExpressionTree.

// Your class needs to code one constructor and one output method as well as any helper methods

// that you find useful.

// The goal is to process mathematical expressions that are provided as strings.

// In the main program that tests your class,

// the Utility getInput method reads a mathematical expression that is typed as input.

// The expression can contain any combination of numbers, variable identifiers and mathematical operations.

// These mathematical operations are +, -, *, /, ( and )

// The constructor should turn an input expression into the content of a binary (expression) tree.

// The tree can then be printed in prefix, postfix, or fully parenthesised infix notation.

// The first two of these methods have been coded for you in the abstract class ExpressionTree, you need to code the third.

// For example the expression   5 + (x / y + z * 7) – 2  would be printed as

//                              – + 5 + / x y * z 7 2  in prefix order

//  or                          5 x y / z 7 * + + 2 –  in postfix order

//  or               (( 5 + ((x / y) + (z * 7))) – 2)  in fully parenthesised infix notation.

// To simplify things in this project the – sign can only be used between 2 quantities that are being subtracted.

// This will prevent you from ever working with a negative number such as -2 which would involve a different

// use for the – character.  However the simplification means that your code does not need to work out which meaning

// to attach to any copy of a – character.

// Another simplification for this project is that you may assume that only correct mathematical expressions are entered.

// You do not need to check that an input String from getInput makes sense as an expression.

// If an illegal expression is encountered, your program can behave in any way that is convenient for you.

// You should change the class name Y00000000 so that the last 8 digits are your QC ID number.

// You should only make changes inside this class.

// You do not need any more than 100 lines of code in the class.

// After you have tested your work on venus (as well as in your development environment)

// cut the file above the class Utility and submit it by email.

// See also the general homework guidelines for other instructions before you submit work.

// The hard part of this assignment is the constructor.

// In terms of planning it, I suggest that you think about which operation is the last to be performed in the expression.

// Can you write down a rule to identify this operation? Deal with the easier case when there are no parentheses first.

//

// Once you accomplish this you can finish quickly using a recursion.

//

// ThefullyParenthesised method can also be done using a recursion —

//     this will require an auxiliary recursive method to call on.

// Suggested strategy:

// 1. Make a constructor that deals with expressions without parentheses  (1st step partial credit).

// 2. Make a fullyParenthesised output method  (2nd step partial credit).

// 3. Adapt the constructor to deal with parentheses.  Hint a Stack will help here.  (Last part of credit).

public class Y00000000 extends ExpressionTree {

public static void main(String args[]) {

Y00000000 y = new Y00000000(“5 + 6 * 7”);

Utility.print(y);

y = new Y00000000(Utility.getInput());

Utility.print(y);

}

public String fullyParenthesised() {

// add implementation here

return “”;

}

public Y00000000(String s) {

super();

// add implementation here

}

}

//——-  cut here.  Place your new code above this line and submit only the ——

//——-  code above this line as your homework.  Do not make any code changes —-

//——-  below this line.                                                ———

class Utility {

public static String getInput() {

System.out.println(“Enter an algebraic expression: “);

Scanner s = new Scanner(System.in);

String answer =  s.nextLine();

s.close();

return answer;

}

public static void print(ExpressionTree y) {

System.out.println(“Prefix: ” + y.prefix());

System.out.println(“Postfix: ” + y.postfix());

System.out.println(“Fully parenthesised: ” + y.fullyParenthesised());

System.out.println(“—————–“);

}

}

abstract class ExpressionTree extends BinaryTree<String> {

publicExpressionTree() {

super();

}

public abstract String fullyParenthesised();

public final String postfix() {

String ans = “”;

ArrayList<Node<String>> l = postOrder();

for (Node<String> b:l) ans += b.getData() + ” “;

returnans;

}

public final String prefix() {

String ans = “”;

ArrayList<Node<String>> l = preOrder();

for (Node<String> b:l) ans += b.getData() + ” “;

returnans;

}

}

// classes BinaryTree, BNode, Tree and Node exacctly as implemented in our course

classBinaryTree<T> extends Tree<T> {

publicBinaryTree() {

super();

}

public void addRoot(T x) throws Exception {

if (root != null) throw new Exception(“The tree is not empty”);

root = new BNode<T>(x, null, null, null);

size++;

}

public void addLeft(BNode<T> n, T x) throws Exception {

if (n.getLeft() != null) throw new Exception(“Already used”);

n.setLeft(new BNode<T>(x, n, null, null));

size++;

}

public void addRight(BNode<T> n, T x) throws Exception {

if (n.getRight() != null) throw new Exception(“Already used”);

n.setRight(new BNode<T>(x, n, null, null));

size++;

}

// returns the parent of the removed node

publicBNode<T>removeNode(BNode<T> n) {

if (isLeaf(n)) {  // base case

BNode<T> p = (BNode<T>) parent(n);

if (p == null) root = null;

elsep.removeChild(n);

size–;

return p;

}

if (n.getLeft() != null) {

BNode<T> m = rightmostLeftDescendant(n);

n.setData(m.getData());

returnremoveNode(m);   // recursively remove rightmost left descendant

}

// otherwise n does have a right child

BNode<T> m = leftmostRightDescendant(n);

n.setData(m.getData());

returnremoveNode(m);

}

publicBNode<T>leftmostRightDescendant(BNode<T> n) {

BNode<T> m = n.getRight();

while (m.getLeft() != null) m = m.getLeft();

return m;

}

publicBNode<T>rightmostLeftDescendant(BNode<T> n) {

BNode<T> m = n.getLeft();

while (m.getRight() != null) m = m.getRight();

return m;

}

publicArrayList<BNode<T>>inOrder() {

ArrayList<BNode<T>> answer = new ArrayList<BNode<T>>();

inOrder((BNode<T>) root(), answer);

return answer;

}

public void inOrder(BNode<T> n, ArrayList<BNode<T>> v) {

if (n == null) return;

inOrder(n.getLeft(), v);

v.add(n);

inOrder(n.getRight(), v);

}

publicArrayList<BNode<T>>flatOrder() {

returninOrder();

}

}

classBNode<T> extends Node<T> {

BNode<T> left, right;

publicBNode(T d, BNode<T> p, BNode<T> l, BNode<T> r) {

setData(d);

setParent(p);

left = l;

right = r;

}

public void setLeft(BNode<T> n) {

left = n;

}

public void setRight(BNode<T> n) {

right = n;

}

publicBNode<T>getLeft() {

return left;

}

publicBNode<T>getRight() {

return right;

}

public Iterator<BNode<T>> children() {

ArrayList<BNode<T>> v = new ArrayList<>();

if (left != null) v.add(left);

if (right != null) v.add(right);

returnv.iterator();

}

public void removeChild(BNode<T> n) {

if (getLeft() == n) setLeft(null);

elsesetRight(null);

}

public String toString() {  // for testing and debugging

return “Node ” + data;

}

}

class Tree<T> {

protected Node<T> root;

publicint size;

public Tree() {

root = null;

size = 0;

}

public Node<T> root() {

return root;

}

public Node<T> parent(Node<T> v) {

returnv.getParent();

}

public Iterator<? extends Node<T>> children(Node<T> v) {

returnv.children();

}

publicbooleanisRoot(Node<T> v) {

return v == root;

}

publicbooleanisInternal(Node<T> v) {

return children(v).hasNext();

}

publicbooleanisLeaf(Node<T> v) {

return !isInternal(v);

}

publicint size() {

return size;

}

publicboolean empty() {

return size == 0;

}

public void replace(Node<T> v, T t) {

v.setData(t);

}

publicint depth(Node<T> v) {

if (isRoot(v))

return 0;

return 1 + depth(parent(v));

}

publicint height(Node<T> v) {

if (isLeaf(v))

return 0;

intmaxChild = 0;

Iterator<?extends Node<T>> c = children(v);

while (c.hasNext()) {

inthc = height((Node<T>) c.next());

if (hc>maxChild)

maxChild = hc;

}

returnmaxChild + 1;

}

publicint height() {

if (root == null)

return -1;

return height(root);

}

publicArrayList<Node<T>>preOrder() {

ArrayList<Node<T>> answer = new ArrayList<>();

preOrder(root(), answer);

return answer;

}

public void preOrder(Node<T> n, ArrayList<Node<T>> v) {

if (n == null)

return;

v.add(n);

Iterator<?extends Node<T>> x = children(n);

while (x.hasNext()) {

Node<T> m = x.next();

preOrder(m, v);

}

}

publicArrayList<Node<T>>postOrder() {

ArrayList<Node<T>> answer = new ArrayList<Node<T>>();

postOrder(root(), answer);

return answer;

}

public void postOrder(Node<T> n, ArrayList<Node<T>> v) {

if (n == null)

return;

Iterator<?extends Node<T>> x = children(n);

while (x.hasNext()) {

Node<T> m = x.next();

postOrder(m, v);

}

v.add(n);

}

publicArrayList<Node<T>>levelOrder() {

ArrayList<Node<T>> waiting = new ArrayList<>();

waiting.add(null);

if (root() == null)

return waiting;

waiting.add(root());

int done = 0;

while (done <waiting.size()) {

Node<T>oldNode = waiting.get(done++);

if (oldNode == null) {

if (done <waiting.size())

waiting.add(null);

continue;

}

Iterator<?extends Node<T>> c = children(oldNode);

while (c.hasNext())

waiting.add(c.next());

}

return waiting;

}

publicArrayList<? extends Node<T>>flatOrder() {

returnpreOrder();

}

public String toString() {

returntreePrint(null);

}

public String treePrint(Node<T> cursor) {

String answer = ”  “;

Iterator<Node<T>>lev = levelOrder().iterator();

Iterator<?extends Node<T>> flat = flatOrder().iterator();

lev.next(); // skip first new line

while (lev.hasNext()) {

Node<T> o = lev.next();

if (o == null) {

answer += “\n  “;

flat = flatOrder().iterator();

} else

while (true) {

booleanatCursor = false;

Node<T> n = flat.next();

if (n == cursor)

atCursor = true;

String s = n.getData().toString();

if (atCursor)

s = “* ” + s + ” *”;

if (n == o) {

answer += s + ” “;

break;

} else {

for (int i = 0; i <s.length(); i++)

answer += ‘ ‘;

answer += ‘ ‘;

}

}

}

return answer;

}

}

abstract class Node<T> {

protected Node<T> parent;

protected T data;

public abstract Iterator<? extends Node<T>> children();

public void setParent(Node<T> n) {

parent = n;

}

public void setData(T t) {

data = t;

}

public Node<T>getParent() {

return parent;

}

public T getData() {

return data;

}

} 

Solution 

BinaryTree.java

importjava.util.ArrayList;

classBinaryTree<T> extends Tree<T> {

publicBinaryTree() {

super();

}

public void addRoot(T x) throws Exception {

if (root != null)

throw new Exception(“The tree is not empty”);

root = new BNode<T>(x, null, null, null);

size++;

}

public void addLeft(BNode<T> n, T x) throws Exception {

if (n.getLeft() != null)

throw new Exception(“Already used”);

n.setLeft(new BNode<T>(x, n, null, null));

size++;

}

public void addRight(BNode<T> n, T x) throws Exception {

if (n.getRight() != null)

throw new Exception(“Already used”);

n.setRight(new BNode<T>(x, n, null, null));

size++;

}

// returns the parent of the removed node

publicBNode<T>removeNode(BNode<T> n) {

if (isLeaf(n)) { // base case

BNode<T> p = (BNode<T>) parent(n);

if (p == null)

root = null;

else

p.removeChild(n);

size–;

return p;

}

if (n.getLeft() != null) {

BNode<T> m = rightmostLeftDescendant(n);

n.setData(m.getData());

returnremoveNode(m); // recursively remove rightmost left descendant

}

// otherwise n does have a right child

BNode<T> m = leftmostRightDescendant(n);

n.setData(m.getData());

returnremoveNode(m);

}

publicBNode<T>leftmostRightDescendant(BNode<T> n) {

BNode<T> m = n.getRight();

while (m.getLeft() != null)

m = m.getLeft();

return m;

}

publicBNode<T>rightmostLeftDescendant(BNode<T> n) {

BNode<T> m = n.getLeft();

while (m.getRight() != null)

m = m.getRight();

return m;

}

publicArrayList<BNode<T>>inOrder() {

ArrayList<BNode<T>> answer = new ArrayList<BNode<T>>();

inOrder((BNode<T>) root(), answer);

return answer;

}

public void inOrder(BNode<T> n, ArrayList<BNode<T>> v) {

if (n == null)

return;

inOrder(n.getLeft(), v);

v.add(n);

inOrder(n.getRight(), v);

}

publicArrayList<BNode<T>>flatOrder() {

returninOrder();

}

} 

BNode.java

importjava.util.ArrayList;

importjava.util.Iterator;

classBNode<T> extends Node<T> {

BNode<T> left, right;

publicBNode(T d, BNode<T> p, BNode<T> l, BNode<T> r) {

setData(d);

setParent(p);

left = l;

right = r;

}

public void setLeft(BNode<T> n) {

left = n;

}

public void setRight(BNode<T> n) {

right = n;

}

publicBNode<T>getLeft() {

return left;

}

publicBNode<T>getRight() {

return right;

}

public Iterator<BNode<T>> children() {

ArrayList<BNode<T>> v = new ArrayList<>();

if (left != null)

v.add(left);

if (right != null)

v.add(right);

returnv.iterator();

}

public void removeChild(BNode<T> n) {

if (getLeft() == n)

setLeft(null);

else

setRight(null);

}

public String toString() { // for testing and debugging

return “Node ” + data;

}

} 

ExpressionTree.java

importjava.util.ArrayList;

abstract class ExpressionTree extends BinaryTree<String> {

publicExpressionTree() {

super();

}

public abstract String fullyParenthesised();

public final String postfix() {

String ans = “”;

ArrayList<Node<String>> l = postOrder();

for (Node<String> b : l)

ans += b.getData() + ” “;

returnans;

}

public final String prefix() {

String ans = “”;

ArrayList<Node<String>> l = preOrder();

for (Node<String> b : l)

ans += b.getData() + ” “;

returnans;

}

} 

Node.java

importjava.util.Iterator;

abstract class Node<T> {

protected Node<T> parent;

protected T data;

public abstract Iterator<? extends Node<T>> children();

public void setParent(Node<T> n) {

parent = n;

}

public void setData(T t) {

data = t;

}

public Node<T>getParent() {

return parent;

}

public T getData() {

return data;

}

} 

Tree.java

importjava.util.ArrayList;

importjava.util.Iterator;

class Tree<T> {

protected Node<T> root;

publicint size;

public Tree() {

root = null;

size = 0;

}

public Node<T> root() {

return root;

}

public Node<T> parent(Node<T> v) {

returnv.getParent();

}

public Iterator<? extends Node<T>> children(Node<T> v) {

returnv.children();

}

publicbooleanisRoot(Node<T> v) {

return v == root;

}

publicbooleanisInternal(Node<T> v) {

return children(v).hasNext();

}

publicbooleanisLeaf(Node<T> v) {

return !isInternal(v);

}

publicint size() {

return size;

}

publicboolean empty() {

return size == 0;

}

public void replace(Node<T> v, T t) {

v.setData(t);

}

publicint depth(Node<T> v) {

if (isRoot(v))

return 0;

return 1 + depth(parent(v));

}

publicint height(Node<T> v) {

if (isLeaf(v))

return 0;

intmaxChild = 0;

Iterator<?extends Node<T>> c = children(v);

while (c.hasNext()) {

inthc = height((Node<T>) c.next());

if (hc>maxChild)

maxChild = hc;

}

returnmaxChild + 1;

}

publicint height() {

if (root == null)

return -1;

return height(root);

}

publicArrayList<Node<T>>preOrder() {

ArrayList<Node<T>> answer = new ArrayList<>();

preOrder(root(), answer);

return answer;

}

public void preOrder(Node<T> n, ArrayList<Node<T>> v) {

if (n == null)

return;

v.add(n);

Iterator<?extends Node<T>> x = children(n);

while (x.hasNext()) {

Node<T> m = x.next();

preOrder(m, v);

}

}

publicArrayList<Node<T>>postOrder() {

ArrayList<Node<T>> answer = new ArrayList<Node<T>>();

postOrder(root(), answer);

return answer;

}

public void postOrder(Node<T> n, ArrayList<Node<T>> v) {

if (n == null)

return;

Iterator<?extends Node<T>> x = children(n);

while (x.hasNext()) {

Node<T> m = x.next();

postOrder(m, v);

}

v.add(n);

}

publicArrayList<Node<T>>levelOrder() {

ArrayList<Node<T>> waiting = new ArrayList<>();

waiting.add(null);

if (root() == null)

return waiting;

waiting.add(root());

int done = 0;

while (done <waiting.size()) {

Node<T>oldNode = waiting.get(done++);

if (oldNode == null) {

if (done <waiting.size())

waiting.add(null);

continue;

}

Iterator<?extends Node<T>> c = children(oldNode);

while (c.hasNext())

waiting.add(c.next());

}

return waiting;

}

publicArrayList<? extends Node<T>>flatOrder() {

returnpreOrder();

}

public String toString() {

returntreePrint(null);

}

public String treePrint(Node<T> cursor) {

String answer = ”  “;

Iterator<Node<T>>lev = levelOrder().iterator();

Iterator<?extends Node<T>> flat = flatOrder().iterator();

lev.next(); // skip first new line

while (lev.hasNext()) {

Node<T> o = lev.next();

if (o == null) {

answer += “\n  “;

flat = flatOrder().iterator();

} else

while (true) {

booleanatCursor = false;

Node<T> n = flat.next();

if (n == cursor)

atCursor = true;

String s = n.getData().toString();

if (atCursor)

s = “* ” + s + ” *”;

if (n == o) {

answer += s + ” “;

break;

} else {

for (int i = 0; i <s.length(); i++)

answer += ‘ ‘;

answer += ‘ ‘;

}

}

}

return answer;

}

} 

Utility.java

importjava.util.Scanner;

public class Utility {

public static String getInput() {

System.out.println(“Enter an algebraic expression: “);

Scanner s = new Scanner(System.in);

String answer = s.nextLine();

s.close();

return answer;

}

public static void print(ExpressionTree y) {

System.out.println(“Prefix: ” + y.prefix());

System.out.println(“Postfix: ” + y.postfix());

System.out.println(“Fully parenthesised: ” + y.fullyParenthesised());

System.out.println(“—————–“);

}

} 

Y00000000.java 

importjava.util.Stack;

public class Y00000000 extends ExpressionTree {

public static void main(String args[]) {

Y00000000 y = new Y00000000(“5 + 6 * 7”);

Utility.print(y);

y = new Y00000000(Utility.getInput());

Utility.print(y);

}

public String fullyParenthesised() {

String ans = fullParents((BNode<String>)root());

returnans;

}

public Y00000000(String s) {

super();

s=mod(s); //mod the string by removing spaces and adding * where needed

root = generateTree(s); //generate the tree and set the highest node to the root

}

publicBNode<String>generateTree(String s){ //a recursive call to generate the tree

s=modparents(s); // call the method remove unneeded parents

if(s.matches(“\\d+”) || s.length()==1) //base case for recursion. When its either only digits or just a single character

return new BNode<String>(s, null, null, null); //return this leaf

int root = rootLoc(s); //find the root

BNode<String>newNode = new BNode<>(s.charAt(root)+””, null, null, null); // create a root for this operator

newNode.setLeft(generateTree(s.substring(0, root))); // recursive call to find the left subtree

newNode.setRight(generateTree(s.substring(root+1, s.length()))); //recursive call to fin the right subtree

returnnewNode;

}

publicintrootLoc(String s){   //method checks for the root location

introotLoc = -1; //default root

Stack<String> parents = new Stack<>();  //this stack keeps track of parents

for(int i = s.length()-1; i>=0; i–) {   //moves backward to find the last operation done

if(s.charAt(i)==’)’) parents.push(“)”);  // this adds a parents to the stack indicating we dont need to check this area onward

if(s.charAt(i)=='(‘) parents.pop(); //this removes the parents from the stack

if(parents.isEmpty()) { //if there are no parents on the stack, then it is safe to check for operators

if((s.charAt(i)==’/’ || s.charAt(i)==’*’) &&rootLoc ==-1) rootLoc = i; // if we find any * or /. But only first one

if(s.charAt(i)==’+’ || s.charAt(i)==’-‘) { //finds the first + or –

rootLoc = i;

break; //break b/c no need to find other operator. this is the last one and highest priority

}

}

}

returnrootLoc;

}

public String mod(String s) {   //this methods adds any missing multiplication signs in the string

s=s.replaceAll(” “, “”); //remove all spaces

s=s.replaceAll(“\\[“, “(“);

s=s.replaceAll(“\\]”,”)”);

String s2 =””; //this is the string being return

Stack<String> x = new Stack<>(); //this stack will hold every char from beg on the bottom and end on top

for(int i =0; i<s.length(); i++) { //this loop will add chars on at a time and check for conditions

if(!x.isEmpty()) {

if(s.charAt(i)=='(‘ && (isOperand(x.peek()) || x.peek().equals(“)”)) ) x.push(“*”); //add a multiplication * to the stack for )( , 5(, X(

if(x.peek().equals(“)”) &&isOperand(“”+s.charAt(i)) ) x.push(“*”); //add multiplication * to the stack for )5, )X

if(x.peek().matches(“\\w+”) &&isOperand(“”+s.charAt(i)) && !isDigit(“”+s.charAt(i))) x.push(“*”); // add multiplication * to the stack for 5X, XY

if(x.peek().matches(“[a-zA-Z]”) &&isDigit(s.charAt(i)+””)) x.push(“*”);// adds * to X5

}

x.push(s.charAt(i)+””); // add the character to the stack

}

while(!x.isEmpty()) {//this loop add the characters into the new string. Adding them backwards

s2 =  x.pop() + s2;

}

return s2;

}

publicbooleanisOperator(String s) {

returns.equals(“+”) || s.equals(“-“) || s.equals(“/”) || s.equals(“*”);

}

publicbooleanisOperand(String s) {    //this check is the string is an operand

returns.matches(“\\w+”);

}

publicbooleanisDigit(String s) {   //check if the string consists of just digits

returns.matches(“\\d+”);

}

public String modparents(String s) { // this methods removes any unneeded parents from the string

while(s.startsWith(“(“) &&s.endsWith(“)”) ) { // only check is there are parents at the beginning and end

Stack<String> parents = new Stack<>(); //use a stack to keep track of any open parents

boolean open = false; // indicate whether there is a open parents that is unclosed

for(int i=0; i<s.length(); i++) {

if(s.charAt(i)=='(‘) { //push a open parents when a open parents is found in the string

parents.push(“(“);

open = true; // change the bool to true b/c theres unclosed parents

}

if(s.charAt(i)==’)’) {

parents.pop(); //remove a open parents

if(parents.isEmpty()) open = false; // set it to false iff there are no open parents left

}

if(!open &&isOperator(s.charAt(i)+””)) return s; //return the original string if we find an operator when theres no open parents

}

s= s.substring(1, s.length()-1); //since theres no operators we can safely remove parents

}

return s;

}

public String fullParents(BNode<String> n) { //recursive call to generate full parents

if(isLeaf(n)) return n.getData(); //base case if its a leaf just return the data

String root = n.getData(); // get the root or operator

String left = fullParents(n.getLeft()); //get the left operand

String right = fullParents(n.getRight()); //get the right operand

return “(” + left + root + right + “)”; //concate a string with a parents in the beginning and end

}

}