Binary Tree and recursion

[Rastabot]

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-

public String asPostfix()
	{
		return asPostfix(root);

	}

	public String asPostfix(ExpNode subTree)
	{
		if (subTree == null)
			return "";
		else
			return asPostfix(subTree.left) + " " + asPostfix(subTree.right) + subTree;
	}

But its a little bit different traversing the tree when I have to return on int.
Any tips would be appreciated.

[sillyboy]

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)

[Rastabot]

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.

[sillyboy]

why does it need to be int?

[Rastabot]

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

[sillyboy]

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.

[Rastabot]

Thanks for the help. Heres the method:

public int numOps()
	{
		return numOps(root.left, root.right);
	}

	public int numOps(ExpNode subTree, ExpNode subTree2)
	{
		int total= 0;

		if (subTree == null || subTree2 == null)
			return  0;

		else
			return numOps(subTree.left, subTree.right) + numOps(subTree2.right, subTree2.left) + 1;
	}

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?

[sillyboy]

from a quick glance i'd say your contructor isn't trimming the whitespaces correctly

[Rastabot]

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-

public double evaluate(ExpNode subTree)
	{
		//Not done with stopping condition
		if(subTree == null)
		{
			;
		}

		double result = 0;


		String str = subTree.data.toString();
		Double num1 = Double.parseDouble(subTree.left.data.toString());
		Double num2 = Double.parseDouble(subTree.right.data.toString());
		switch(str.charAt(0))
		{

						case '%':{ result = num1 % num2;
								break;}

						case '+': { result = num1 + num2;
								break;}

						case '-': { result = num1 - num2;
								break;}

						case '*': {result = num1 * num2;
								break;}

						case '/': {result = num1 / num2;
								break;}

		}
	
	
	return  evaluate(subTree.left) + evaluate(subTree.right) + result;
	}

But it doesn't really work at all. Any tips would be appreciated.

[sillyboy]

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.