Java - data structures

P3

Design an algorithm that produces a binary expression tree from a given infix expression. You can assume that the infix expression is a string that has only the binary operators +, -, *, / and one-letter operands. Implement the solution as a construction in ExpressionTree that takes a string argument:

public ExpressionTree(String infix)

that calls the private method

private ExpressionTreeInterface formTree(String expr, int first, int last)

to construct the tree. formTree() builds the tree recursively.

ExpressionTree.java

public class ExpressionTree extends BinaryTree { public ExpressionTree() { } // end default constructor public ExpressionTree(String data) { super(data); } // end default constructor public double evaluate() { return evaluate(root); } // end evaluate private double evaluate(BinaryNode rootNode) { double result; if (rootNode == null) result = 0; else if (rootNode.isLeaf()) { String variable = rootNode.getData(); result = getValueOf(variable); } else { double firstOperand = evaluate(rootNode.getLeftChild()); double secondOperand = evaluate(rootNode.getRightChild()); String operator = rootNode.getData(); result = compute(operator, firstOperand, secondOperand); } // end if

return result; } // end evaluate private double getValueOf(String variable) { // strings allow multicharacter variables double result = 0; if (variable.equals("a")) result = 1; else if (variable.equals("b")) result = 2; else if (variable.equals("c")) result = 3; else if (variable.equals("d")) result = 4; else if (variable.equals("e")) result = 5; return result; } // end getValueOf

private double compute(String operator, double firstOperand, double secondOperand) { double result = 0; if (operator.equals("+")) result = firstOperand + secondOperand; else if (operator.equals("-")) result = firstOperand - secondOperand; else if (operator.equals("*")) result = firstOperand * secondOperand; else if (operator.equals("/")) result = firstOperand / secondOperand; return result; } // end compute } // end ExpressionTree

Incase if you need Binarytree and Binarynode

BinaryTree.java

//package TreePackage; import java.util.Iterator; import java.util.NoSuchElementException; import java.util.Stack ; // for Stack

public class BinaryTree { protected BinaryNode root; public BinaryTree() { root = null; } // end default constructor public BinaryTree(T rootData) { root = new BinaryNode(rootData); } // end constructor

public BinaryTree(T rootData, BinaryTree leftTree, BinaryTree rightTree) { privateSetTree(rootData, leftTree, rightTree); } // end constructor

public void setTree(T rootData) { root = new BinaryNode(rootData); } // end setTree public void setTree(T rootData, BinaryTree leftTree, BinaryTree rightTree) { privateSetTree(rootData, leftTree, rightTree); } // end setTree

private void privateSetTree(T rootData, BinaryTree leftTree, BinaryTree rightTree) { root = new BinaryNode(rootData);

if (leftTree != null) root.setLeftChild(leftTree.root); if (rightTree != null) root.setRightChild(rightTree.root); }

public T getRootData () { T rootData = null; if (root != null) rootData = root.getData(); return rootData; } public boolean isEmpty () { return root == null; } public void clear (){ root = null; } // getHeight and getNumberOfNodes call same functions in BinaryNode public int getHeight () { return root.getHeight (); } public int getNumberOfNodes () { return root.getNumberOfNodes (); } public void inorderTraversal() { Stack> nodeStack = new Stack>(); BinaryNode currentNode = root; while (!nodeStack.empty() || currentNode != null) { while(currentNode != null) { nodeStack.push(currentNode); currentNode = currentNode.getLeftChild(); } if(!nodeStack.empty()) { BinaryNode nextNode = nodeStack.pop(); System.out.println(nextNode.getData()); currentNode = nextNode.getRightChild(); } } } public Iterator getPreorderIterator() { return new PreorderIterator(); } public Iterator getInorderIterator() { return new InorderIterator(); } private class PreorderIterator implements Iterator { private Stack> nodeStack; public PreorderIterator() { nodeStack = new Stack>(); if (root != null) nodeStack.push(root); } // end default constructor public boolean hasNext() { return !nodeStack.isEmpty(); } // end hasNext public T next() { BinaryNode nextNode; if (hasNext()) { nextNode = nodeStack.pop(); BinaryNode leftChild = nextNode.getLeftChild(); BinaryNode rightChild = nextNode.getRightChild(); // push into stack in reverse order of recursive calls if (rightChild != null) nodeStack.push(rightChild); if (leftChild != null) nodeStack.push(leftChild); } else { throw new NoSuchElementException(); } return nextNode.getData(); } // end next public void remove() { throw new UnsupportedOperationException(); } // end remove } // end PreorderIterator private class InorderIterator implements Iterator < T > { private Stack< BinaryNode< T >> nodeStack; private BinaryNode< T > currentNode; public InorderIterator () { nodeStack = new Stack < BinaryNode< T>> (); currentNode = root; } // end default constructor

public boolean hasNext () { return !nodeStack.isEmpty () || (currentNode != null); } // end hasNext

public T next () { BinaryNode< T > nextNode = null; // find leftmost node with no left child while (currentNode != null) { nodeStack.push (currentNode); currentNode = currentNode.getLeftChild (); } // end while // get leftmost node, then move to its right subtree if (!nodeStack.isEmpty ()) { nextNode = nodeStack.pop (); currentNode = nextNode.getRightChild (); } else throw new NoSuchElementException (); return nextNode.getData (); } // end next public void remove () { throw new UnsupportedOperationException (); } // end remove

} // end InorderIterator } // end BinaryTree

BinaryNode.java

//package TreePackage; class BinaryNode { private T data; private BinaryNode left; private BinaryNode right;

public BinaryNode() { this(null); // call next constructor } // end default constructor

public BinaryNode(T dataPortion) { this(dataPortion, null, null); // call next constructor } // end constructor

public BinaryNode(T dataPortion, BinaryNode leftChild, BinaryNode rightChild) { data = dataPortion; left = leftChild; right = rightChild; } // end constructor

public T getData() { return data; } // end getData

public void setData(T newData) { data = newData; } // end setData

public BinaryNode getLeftChild() { return left; } // end getLeftChild

public void setLeftChild(BinaryNode leftChild) { left = leftChild; } // end setLeftChild

public boolean hasLeftChild() { return left != null; } // end hasLeftChild

public boolean isLeaf() { return (left == null) && (right == null); } // end isLeaf public BinaryNode getRightChild() { return right; } // end getLeftChild

public void setRightChild(BinaryNode rightChild) { right = rightChild; } // end setLeftChild

public boolean hasRightChild() { return right != null; } // end

public int getHeight() { return getHeight(this); // call private getHeight } // end getHeight private int getHeight(BinaryNode node) { int height = 0; if (node != null) height = 1 + Math.max(getHeight(node.left), getHeight(node.right)); return height; } // end getHeight public int getNumberOfNodes() { int leftNumber = 0; int rightNumber = 0; if (left != null) leftNumber = left.getNumberOfNodes(); if (right != null) rightNumber = right.getNumberOfNodes(); return 1 + leftNumber + rightNumber; } // end getNumberOfNodes public BinaryNode copy() { BinaryNode newRoot = new BinaryNode(data);

if (left != null) newRoot.left = left.copy(); if (right != null) newRoot.right = right.copy(); return newRoot; } // end copy } // end BinaryNode