943,822 Members | Top Members by Rank

Software Development > Java > Binary Tree and recursion
Ad:
  • Java Discussion Thread
  • Unsolved
  • Views: 1544
  • Java RSS
Permalink
Apr 30th, 2009
0

Binary Tree and recursion

Expand Post »
I have to write a program the accepts a fully parenthesized like "((3*4)+(2-(4/2)))", or (3+5). It builds a tree for the expression, without the parentheses. So the tree for the (3+5) would be - "+" is the root, and the 3 is the left node and the 5 is the right node.
So its really an Expression Tree.

In one of my methods I have to count and return the number of operations, and I have to do it recursively. I'm having some trouble with the logic.
I had one method were I had to return the postFix notation of the expression recursively like this-

Java Syntax (Toggle Plain Text)
  1. 	public String asPostfix()
  2. 	{
  3. 		return asPostfix(root);
  4.  
  5. 	}
  6.  
  7. 	public String asPostfix(ExpNode subTree)
  8. 	{
  9. 		if (subTree == null)
  10. 			return "";
  11. 		else
  12. 			return asPostfix(subTree.left) + " " + asPostfix(subTree.right) + subTree;
  13. 	}
But its a little bit different traversing the tree when I have to return on int.
Any tips would be appreciated.
Similar Threads
Reputation Points: 10
Solved Threads: 0
Newbie Poster
Rastabot is offline Offline
11 posts
since Apr 2009
Permalink
Apr 30th, 2009
0

Re: Binary Tree and recursion

i am not entirely sure what your issue is. what i gather is you having issues with "return on int", but you don't have to do you...

why not treat everything as a char? (assuming single digits)
Reputation Points: 85
Solved Threads: 64
Practically a Master Poster
sillyboy is offline Offline
686 posts
since Mar 2007
Permalink
Apr 30th, 2009
0

Re: Binary Tree and recursion

I meant "return an int." Because in the asPostFix, I can add to the String and change the value in the same recursive call. But I'm having trouble with the logic on how to add to the total and change the value in the recursive call.
Reputation Points: 10
Solved Threads: 0
Newbie Poster
Rastabot is offline Offline
11 posts
since Apr 2009
Permalink
Apr 30th, 2009
0

Re: Binary Tree and recursion

why does it need to be int?
Reputation Points: 85
Solved Threads: 64
Practically a Master Poster
sillyboy is offline Offline
686 posts
since Mar 2007
Permalink
Apr 30th, 2009
0

Re: Binary Tree and recursion

Well, its a homework assignment and in the requirements, he wants the method to return an int, which is the number of operations in the expression
Reputation Points: 10
Solved Threads: 0
Newbie Poster
Rastabot is offline Offline
11 posts
since Apr 2009
Permalink
May 1st, 2009
0

Re: Binary Tree and recursion

oh right now i see what you mean. it is similar to your exising recursion, just use different conditions. all you need to do is keep track of some counter.
Reputation Points: 85
Solved Threads: 64
Practically a Master Poster
sillyboy is offline Offline
686 posts
since Mar 2007
Permalink
May 1st, 2009
0

Re: Binary Tree and recursion

Thanks for the help. Heres the method:
Java Syntax (Toggle Plain Text)
  1. 	public int numOps()
  2. 	{
  3. 		return numOps(root.left, root.right);
  4. 	}
  5.  
  6. 	public int numOps(ExpNode subTree, ExpNode subTree2)
  7. 	{
  8. 		int total= 0;
  9.  
  10. 		if (subTree == null || subTree2 == null)
  11. 			return  0;
  12.  
  13. 		else
  14. 			return numOps(subTree.left, subTree.right) + numOps(subTree2.right, subTree2.left) + 1;
  15. 	}

It seems to work fine. However I was do some more testing and it seems my constructor won't construct these expression properly:
((12 - 8) / (2 * 5))

((10*10) - ((4*5)*5))

But it will construct these ones properly:
((3*4)-(2-(4/2)))
(5-3)
(8.14-6.2)

Should I look over my constructor or are the first 2 ones not fully parenthesized expressions?
Reputation Points: 10
Solved Threads: 0
Newbie Poster
Rastabot is offline Offline
11 posts
since Apr 2009
Permalink
May 2nd, 2009
0

Re: Binary Tree and recursion

from a quick glance i'd say your contructor isn't trimming the whitespaces correctly
Reputation Points: 85
Solved Threads: 64
Practically a Master Poster
sillyboy is offline Offline
686 posts
since Mar 2007
Permalink
May 2nd, 2009
0

Re: Binary Tree and recursion

That was it exactly, thanks for the help. However, now I have to code a method that will evaluate the expression tree using recursion. I assume it will be somewhat like my postFix method that was in my first post. I'm having trouble figuring out the algorithm. I couldn't come up with much. I had this-
Java Syntax (Toggle Plain Text)
  1. 	public double evaluate(ExpNode subTree)
  2. 	{
  3. 		//Not done with stopping condition
  4. 		if(subTree == null)
  5. 		{
  6. 			;
  7. 		}
  8.  
  9. 		double result = 0;
  10.  
  11.  
  12. 		String str = subTree.data.toString();
  13. 		Double num1 = Double.parseDouble(subTree.left.data.toString());
  14. 		Double num2 = Double.parseDouble(subTree.right.data.toString());
  15. 		switch(str.charAt(0))
  16. 		{
  17.  
  18. 						case '%':{ result = num1 % num2;
  19. 								break;}
  20.  
  21. 						case '+': { result = num1 + num2;
  22. 								break;}
  23.  
  24. 						case '-': { result = num1 - num2;
  25. 								break;}
  26.  
  27. 						case '*': {result = num1 * num2;
  28. 								break;}
  29.  
  30. 						case '/': {result = num1 / num2;
  31. 								break;}
  32.  
  33. 		}
  34.  
  35.  
  36. 	return  evaluate(subTree.left) + evaluate(subTree.right) + result;
  37. 	}
But it doesn't really work at all. Any tips would be appreciated.
Reputation Points: 10
Solved Threads: 0
Newbie Poster
Rastabot is offline Offline
11 posts
since Apr 2009
Permalink
May 2nd, 2009
0

Re: Binary Tree and recursion

that method is going to involve a bit of thought, and i am not feeling quite up for thinking it out completely. i think at the moment you haven't quite accounted for having child nodes which are expressions ("+", "-", ...). another thing that looks wrong is your return statement. i might have another look later when i have a clearer head.
Reputation Points: 85
Solved Threads: 64
Practically a Master Poster
sillyboy is offline Offline
686 posts
since Mar 2007

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.
Message:
Previous Thread in Java Forum Timeline: Exception in thread "main" java.lang.NoClassDefFoundError: Main/class
Next Thread in Java Forum Timeline: Main displaying values twice





About Us | Contact Us | Advertise | Acceptable Use Policy
Forum Index | Build Custom RSS Feed


Follow us on Twitter


© 2011 DaniWeb® LLC