Question
I need help with this assignment, I can't seem to figure it out! Complete A4EquationTree.populateFromPostfix() method - 4pts Complete A4EquationTree.populateFromPrefix() method - 4pts f(N) and
I need help with this assignment, I can't seem to figure it out!
Complete A4EquationTree.populateFromPostfix() method - 4pts
Complete A4EquationTree.populateFromPrefix() method - 4pts
f(N) and O(N) for A4EquationTree.populateFromInfix(String equation) method - 2pts (+1 BONUS option)
A4EquationTree.java
*
* 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.insert(5);
tree1.insert(3);
tree1.insert(1);
tree1.insert(2);
tree1.insert(9);
tree1.insert(10);
tree1.insert(25);
A4BST
tree2.insert(8);
tree2.insert(5);
tree2.insert(1);
tree2.insert(3);
tree2.insert(15);
tree2.insert(20);
tree2.insert(25);
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));
}
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started