0

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
Reply
6
Views
6 Years
Discussion Span
Last Post by CLina
0

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.