Binary Tree and recursion

Please support our Java advertiser: Programming Forums - DaniWeb Sister Site
Reply

•
•
Join Date: Apr 2009
Posts: 10
Reputation: Rastabot is an unknown quantity at this point 
Solved Threads: 0
Rastabot Rastabot is offline Offline
Newbie Poster

Binary Tree and recursion

 
0
  #1
Apr 30th, 2009
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.
Reply With Quote Quick reply to this message  
•
•
Join Date: Mar 2007
Posts: 686
Reputation: sillyboy is on a distinguished road 
Solved Threads: 61
sillyboy's Avatar
sillyboy sillyboy is offline Offline
Practically a Master Poster

Re: Binary Tree and recursion

 
0
  #2
Apr 30th, 2009
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)
http://www.happypolla.com
Reply With Quote Quick reply to this message  
•
•
Join Date: Apr 2009
Posts: 10
Reputation: Rastabot is an unknown quantity at this point 
Solved Threads: 0
Rastabot Rastabot is offline Offline
Newbie Poster

Re: Binary Tree and recursion

 
0
  #3
Apr 30th, 2009
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.
Reply With Quote Quick reply to this message  
•
•
Join Date: Mar 2007
Posts: 686
Reputation: sillyboy is on a distinguished road 
Solved Threads: 61
sillyboy's Avatar
sillyboy sillyboy is offline Offline
Practically a Master Poster

Re: Binary Tree and recursion

 
0
  #4
Apr 30th, 2009
why does it need to be int?
http://www.happypolla.com
Reply With Quote Quick reply to this message  
•
•
Join Date: Apr 2009
Posts: 10
Reputation: Rastabot is an unknown quantity at this point 
Solved Threads: 0
Rastabot Rastabot is offline Offline
Newbie Poster

Re: Binary Tree and recursion

 
0
  #5
Apr 30th, 2009
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
Reply With Quote Quick reply to this message  
•
•
Join Date: Mar 2007
Posts: 686
Reputation: sillyboy is on a distinguished road 
Solved Threads: 61
sillyboy's Avatar
sillyboy sillyboy is offline Offline
Practically a Master Poster

Re: Binary Tree and recursion

 
0
  #6
May 1st, 2009
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.
http://www.happypolla.com
Reply With Quote Quick reply to this message  
•
•
Join Date: Apr 2009
Posts: 10
Reputation: Rastabot is an unknown quantity at this point 
Solved Threads: 0
Rastabot Rastabot is offline Offline
Newbie Poster

Re: Binary Tree and recursion

 
0
  #7
May 1st, 2009
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?
Reply With Quote Quick reply to this message  
•
•
Join Date: Mar 2007
Posts: 686
Reputation: sillyboy is on a distinguished road 
Solved Threads: 61
sillyboy's Avatar
sillyboy sillyboy is offline Offline
Practically a Master Poster

Re: Binary Tree and recursion

 
1
  #8
May 2nd, 2009
from a quick glance i'd say your contructor isn't trimming the whitespaces correctly
http://www.happypolla.com
Reply With Quote Quick reply to this message  
•
•
Join Date: Apr 2009
Posts: 10
Reputation: Rastabot is an unknown quantity at this point 
Solved Threads: 0
Rastabot Rastabot is offline Offline
Newbie Poster

Re: Binary Tree and recursion

 
0
  #9
May 2nd, 2009
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.
Reply With Quote Quick reply to this message  
•
•
Join Date: Mar 2007
Posts: 686
Reputation: sillyboy is on a distinguished road 
Solved Threads: 61
sillyboy's Avatar
sillyboy sillyboy is offline Offline
Practically a Master Poster

Re: Binary Tree and recursion

 
0
  #10
May 2nd, 2009
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.
http://www.happypolla.com
Reply With Quote Quick reply to this message  
Reply

Quick Reply to Thread
This thread is more than three months old.
Perhaps start a new thread instead?
•
•
•
•
•
•
•
•
Message:
•
•
•
•



Similar Threads
Other Threads in the Java Forum
Thread Tools Search this Thread



Tag cloud for Java
actionlistener android api apple applet application apps arguments array arrays automation balls binary bluetooth card chat class classes client code component consumer database draw eclipse ee error event exception file fractal free game gameprogramming gis givemetehcodez graphics gui helpwithhomework html ide image input integer j2me j2seprojects java javaprojects jmf jni jpanel julia jvm linux list loop machine map method methods migrate mobile myaggfun netbeans newbie nextline nls notdisplaying number oracle output print problem program programming project recursion recursive scanner screen security server set size sms socket sort spamblocker sql sqlite string sun swing terminal test threads time tree trolltech windows
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC