Question: Data Structure Java Binary Tree Help BinaryTreeFormula Expand on the binary tree example we did in class that reads infix formulas and stores them in
Data Structure Java Binary Tree Help
BinaryTreeFormula Expand on the binary tree example we did in class that reads infix formulas and stores them in a binary tree. Create methods for reading postfix and prefix formulas and storing them in the tree.
DO NOT convert prefix/postfix to infix before storing in the tree.
Make the methods as efficient as possible. Include a tester class and make sure the tree is printed in all 3 formats after being populated from any of the three. Include Big-Oh notation for all 3 populate methods, and all 3 print methods.
==============================================================================================
public class EquationBinaryTree {
private Node root;
public EquationBinaryTree()
{
root = null;
}
public String toInfix()
{
return toInfixHelper(root);
}
private String toInfixHelper(Node node)
{
String output = "";
if(node.leftChild != null)
{
output += "(";
output += toInfixHelper(node.leftChild);
output += node;
output += toInfixHelper(node.rightChild);
output += ")";
}
else
output += node;
return output;
}
public String toPostfix()
{
return toPostfixHelper(root);
}
private String toPostfixHelper(Node node)
{
String output = "";
if(node.leftChild != null)
{
output += toPostfixHelper(node.leftChild);
output += toPostfixHelper(node.rightChild);
output += node;
}
else
output += node;
return output;
}
public String toPrefix()
{
return toPrefixHelper(root);
}
private String toPrefixHelper(Node node)
{
String output = "";
if(node.leftChild != null)
{
output += node;
output += toPrefixHelper(node.leftChild);
output += toPrefixHelper(node.rightChild);
}
else
output += node;
return output;
}
//infix ((a-d)+(b*c))
public void populateFromInfix(String infix)
{
root = populateFromInfixHelper(infix);
}
private Node populateFromInfixHelper(String infix)
{
/*
* 0 = left
* 1 = middle
* 2 = right
*/
String[] parts = infixBreakdownHelper(infix);
Node temp = new Node(parts[1].charAt(0));
if(parts[0].length() == 1)
temp.leftChild = new Node(parts[0].charAt(0));
else
temp.leftChild = populateFromInfixHelper(parts[0]);
if(parts[2].length() == 1)
temp.rightChild = new Node(parts[2].charAt(0));
else
temp.rightChild = populateFromInfixHelper(parts[2]);
return temp;
}
private String[] infixBreakdownHelper(String infix)
{
//((a-d)+(b*c))
//[0] = (a-d)
//[1] = +
//[2] = (b*c)
String[] temp = new String[3];
int pos = 0;
int count = 0;
for(int i = 1; i < infix.length(); i++)
{
if(infix.charAt(i) == '(')
count++;
else if(infix.charAt(i) == ')')
count--;
if(count == 0)
{
pos = i;
break;
}
}
/** /
System.out.println("pos:"+pos);
System.out.println("left:"+infix.substring(1, pos+1));
System.out.println("middle:"+infix.charAt(pos+1));
System.out.println("right:"+infix.substring(pos+2, infix.length()-1));
/**/
temp[0] = infix.substring(1, pos+1);//left
temp[1] = ""+infix.charAt(pos+1);//middle
temp[2] = infix.substring(pos+2, infix.length()-1);//right
return temp;
}
/*
* Populate from prefix
*/
public void populateFromPrefix(String pre)
{
}
/*
* Populate from postfix
*/
public void populateFromPostfix(String post)
{
}
private class Node{
public Node leftChild, rightChild;
public char data;
public Node(char data) {
leftChild = null;
rightChild = null;
this.data = data;
}
public String toString()
{
return "" + data;
}
}
}
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
public class EquationBinaryTreeTester {
public static void main(String[] args) {
EquationBinaryTree mathFormula = new EquationBinaryTree();
mathFormula.populateFromInfix("((a+(b*c))+(((d*e)+f)*g))");
System.out.println(mathFormula.toInfix());
System.out.println(mathFormula.toPostfix());
System.out.println(mathFormula.toPrefix());
} }
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help