/* * Complete the populateFromPostfix(String equation) method * Complete the populateFromPrefix(String equation) method * f(N) and O(N) for populateFromInfix(String equation) method */ public class A4EquationTree { /* * Grading: * Correctly fills in tree values from equation string - 3pts * f(N) formula (show your work) - 0.5pt * O(N) reduction - 0.5pt */ public void populateFromPostfix(String equation) { /* * Given a postfix string, create a series of nodes that represent the formula */ root = null; } /* * Grading: * Correctly fills in tree values from equation string - 3pts * f(N) formula (show your work) - 0.5pt * O(N) reduction - 0.5pt */ public void populateFromPrefix(String equation) { /* * Given a prefix string, create a series of nodes that represent the formula */ root = null; } /* * Grading: * f(N) formula (show your work) - 1pt * O(N) reduction - 1pt * Give best and average case reduction for BONUS - 1pt */ public void populateFromInfix(String equation) { root = populateFromInfixHelper(equation); } public Node populateFromInfixHelper(String equation) { if(equation.length() == 1) { return new Node(equation);//math operand }

String temp = equation.substring(1, equation.length()-1);//remove wrapper paren

//begin search for middle of equation int parenCount = 0; int mid = 0; for(int i = 0; i < temp.length(); i++) { if(temp.charAt(i) == '(') parenCount++; if(temp.charAt(i) == ')') parenCount--; if(parenCount == 0) { mid = i+1; break; } } //middle Node n = new Node(""+temp.charAt(mid)); //first half n.left = populateFromInfixHelper(temp.substring(0, mid));//recursive //second half n.right = populateFromInfixHelper(temp.substring(mid+1));//recursive

return n; } private Node root; public A4EquationTree() { root = null; }

//(left parent right) //(->left->parent->right->) public String printInfix() { return printInfixHelper(root); } private String printInfixHelper(Node n)//O(N) - visit each node only once { String content = ""; if(n != null && n.left != null) { content += "("; content += printInfixHelper(n.left);//left side content += n.value;//middle item//parent content += printInfixHelper(n.right);//right side content += ")"; } else if(n != null) { content += n.value;//middle item//parent } return content; } //left -> right -> parent public String printPostfix() { return printPostfixHelper(root); } private String printPostfixHelper(Node n) { String content = ""; if(n != null && n.left != null) { content += printPostfixHelper(n.left);//left side content += printPostfixHelper(n.right);//right side content += n.value;//middle item//parent } else if(n != null) { content += n.value;//middle item//parent } return content; } //parent -> left -> right public String printPrefix() { return printPrefixHelper(root); } private String printPrefixHelper(Node n) { String content = ""; if(n != null && n.left != null) { content += n.value;//middle item//parent content += printPrefixHelper(n.left);//left side content += printPrefixHelper(n.right);//right side } else if(n != null) { content += n.value;//middle item//parent } return content; }

private class Node { String value; Node left, right; public Node(String v) { value = v; left = null; right = null; } } }

A4Driver.java

public class A4Driver {

public static void main(String[] args) { A4BST tree1 = new A4BST<>(); tree1.insert(5); tree1.insert(3); tree1.insert(1); tree1.insert(2); tree1.insert(9); tree1.insert(10); tree1.insert(25); A4BST tree2 = new A4BST<>(); tree2.insert(8); tree2.insert(5); tree2.insert(1); tree2.insert(3); tree2.insert(15); tree2.insert(20); tree2.insert(25); A4BST tree3 = new A4BST<>(); tree3.insert(1); tree3.insert(2); tree3.insert(3); tree3.insert(5); tree3.insert(9); tree3.insert(10); tree3.insert(25); System.out.println("Level Order"); System.out.println(tree1.printInLevelOrder().equals("5,3,9,1,10,2,25,"));//5, 3, 9, 1, 10, 2, 25 System.out.println(tree2.printInLevelOrder().equals("8,5,15,1,20,3,25,"));//8, 5, 15, 1, 20, 3, 25 System.out.println(tree3.printInLevelOrder().equals("1,2,3,5,9,10,25,"));//1, 2, 3, 5, 9, 10, 25 System.out.println(" Visually Identical"); System.out.println(tree1.visuallyIdentical(tree2) == true);//true System.out.println(tree1.visuallyIdentical(tree3) == false);//false

System.out.println(" Populate Methods"); String infix = "(a+b)"; String postfix = "ab+"; String prefix = "+ab";

System.out.println("Original:"+infix); A4EquationTree eq1 = new A4EquationTree(); eq1.populateFromInfix(infix); System.out.println(eq1.printInfix().equals(infix)); System.out.println(eq1.printPostfix().equals(postfix)); System.out.println(eq1.printPrefix().equals(prefix));

System.out.println("Original:"+postfix); A4EquationTree eq2 = new A4EquationTree(); eq2.populateFromPostfix(postfix); System.out.println(eq2.printInfix().equals(infix)); System.out.println(eq2.printPostfix().equals(postfix)); System.out.println(eq2.printPrefix().equals(prefix));

System.out.println("Original:"+prefix); A4EquationTree eq3 = new A4EquationTree(); eq3.populateFromPrefix(prefix); System.out.println(eq3.printInfix().equals(infix)); System.out.println(eq3.printPostfix().equals(postfix)); System.out.println(eq3.printPrefix().equals(prefix));

infix = "((a+(b*c))+(((d*e)+f)*g))"; postfix = "abc*+de*f+g*+"; prefix = "++a*bc*+*defg";

System.out.println("Original:"+infix); eq1 = new A4EquationTree(); eq1.populateFromInfix(infix); System.out.println(eq1.printInfix().equals(infix)); System.out.println(eq1.printPostfix().equals(postfix)); System.out.println(eq1.printPrefix().equals(prefix));

System.out.println("Original:"+postfix); eq2 = new A4EquationTree(); eq2.populateFromPostfix(postfix); System.out.println(eq2.printInfix().equals(infix)); System.out.println(eq2.printPostfix().equals(postfix)); System.out.println(eq2.printPrefix().equals(prefix));

System.out.println("Original:"+prefix); eq3 = new A4EquationTree(); eq3.populateFromPrefix(prefix); System.out.println(eq3.printInfix().equals(infix)); System.out.println(eq3.printPostfix().equals(postfix)); System.out.println(eq3.printPrefix().equals(prefix));

}

}