/* * Complete the populateFromPostfix(String equation) method * Complete the populateFromPrefix(String equation) method * f(N) and O(N) for populateFromInfix(String equation) method * No other methods/variables should be added/modified */ 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; } } } ///////////////////////////////////////////////////////////////////

public class A4Driver {

public static void main(String[] args) {

String infix = "((a+(b*c))+(((d*e)+f)*g))"; String postfix = "abc*+de*f+g*+"; String prefix = "++a*bc*+*defg"; System.out.println("Original:"+infix); A4EquationTree eq1 = new A4EquationTree(); eq1.populateFromInfix(infix); System.out.println(eq1.printInfix()); System.out.println(eq1.printPostfix()); System.out.println(eq1.printPrefix()); System.out.println("Original:"+postfix); A4EquationTree eq2 = new A4EquationTree(); eq2.populateFromPostfix(postfix); System.out.println(eq2.printInfix()); System.out.println(eq2.printPostfix()); System.out.println(eq2.printPrefix()); System.out.println("Original:"+prefix); A4EquationTree eq3 = new A4EquationTree(); eq3.populateFromPrefix(prefix); System.out.println(eq3.printInfix()); System.out.println(eq3.printPostfix()); System.out.println(eq3.printPrefix());

}

}