Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

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 = 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));

}

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Machine Learning And Knowledge Discovery In Databases European Conference Ecml Pkdd 2015 Porto Portugal September 7 11 2015 Proceedings Part 2 Lnai 9285

Authors: Annalisa Appice ,Pedro Pereira Rodrigues ,Vitor Santos Costa ,Joao Gama ,Alipio Jorge ,Carlos Soares

1st Edition

3319235249, 978-3319235240

More Books

Students also viewed these Databases questions