Hi profissionals!
Happy new year : )
....

I have a binary tree project and I need to convert a fully parenthesized arithmetic expression to a binary tree.

I was thinking of this algorithm:

1. input a string of expression.
2. breakdown the string and creat new node for each char.
...

The problem is that I don't know how to build the tree and put the correct operation to be the root.

my tree class is:

``````public void insertNode(String value)
{
if (root == null)
root = new TreeNode(value, null);
else
insert(value, root);
}

public void insert(String value, TreeNode n)
{
//		if (value < n.getData())
//	{
if (!n.hasLeft())
n.setLeft(new TreeNode(value, n));
else
insert(value, n.getLeft());
//	}
//	else if (value > n.getData())
//	{
if (!n.hasRight())
n.setRight(new TreeNode(value, n));
else
insert(value, n.getRight());
//	}
}``````

How can I convert it to a binary tree?

Thank you for helping..

1
Contributor
1
6
Views
7 Years
Discussion Span
Last Post by CLina

I got this code and worked on it, but it outputs only the last part of the whole equation, why?

``````class TreeNode
{

public String Tdata;
public TreeNode left;
public TreeNode right;

TreeNode()
{
this.Tdata = null;
this.right = null;
this.left = null;
}

public TreeNode (String inputData)
{
Tdata = inputData;
this.right = null;
this.left = null;
}

public String toString()
{
return "" + Tdata;
}
}

class ExpTree
{

private TreeNode root;

public ExpTree()     //default constructor
{
root = null;
}

public ExpTree(String theString)
{
Stack<TreeNode> operatorStack = new Stack<TreeNode>();
Stack<TreeNode> operandStack = new Stack<TreeNode>();
StringTokenizer tokenizer = new StringTokenizer(theString, " ()+-/*%",true);
while(tokenizer.hasMoreTokens())
{

String str = tokenizer.nextToken().trim();

if(str.length() == 0)
{
int ignoreWhiteSpace = 0;
}
else if(str.equals("+"))
{
operatorStack.push(new TreeNode(str));
}
else if(str.equals("-"))
{
operatorStack.push(new TreeNode(str));
}
else if(str.equals("/"))
{
operatorStack.push(new TreeNode(str));
}
else if(str.equals("*"))
{
operatorStack.push(new TreeNode(str));
}
else if(str.equals("%"))
{
operatorStack.push(new TreeNode(str));
}
else if(str.equals(")"))
{

TreeNode operand1Removed = operandStack.pop();
TreeNode operand2Removed = operandStack.pop();
TreeNode operator1Removed = operatorStack.pop();
operator1Removed.left = operand2Removed;
operator1Removed.right = operand1Removed;
operandStack.push(operator1Removed);
}

else if(str.equals("("))
{
int emptyStatement = 0;
}

else
{
operandStack.push(new TreeNode(str));
}
}

TreeNode fullExpTree =  operandStack.pop();
root = fullExpTree;

}

public String asPostfix()
{
if (root == null)
return "No Exp<b></b>ression";
else
return postOrder(root);
}

private String postOrder(TreeNode subTree)
{
if (subTree == null)
return "";
else
return postOrder(subTree.left) + " " + postOrder(subTree.right) + " " + subTree;
}

public void printTree()
{
if (root == null)
{
System.out.println("Sorry! The tree is empty");
}
else
printTree(root, 0);
}

private void printTree(TreeNode subTree, int indents)
{

if (subTree.right != null)
printTree(subTree.right, indents+1);

System.out.println("\n\n\n");

for (int i=0; i<indents; i++)
System.out.print("\t");

System.out.println(subTree);

if (subTree.left != null)
printTree(subTree.left, indents+1);

}

public String toString()
{
printTree();
return "";
}
}

public class BinaryExpTree {

public static void main(String[] args) {

Scanner key = new Scanner (System.in);

System.out.println();
System.out.println("Enter a fully parenthesized arithmetic expression:");

String eq = key.next();

ExpTree t = new ExpTree(eq);
t.asPostfix();
t.printTree();

}
}``````

Thank you : )

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.