char BST of and equation

[eNc]

Hi, I'd like to know how to solve a binary search tree. What I mean by this is that I have a BST, and in its Nodes there are matimatical operations and numbers.

For ex. The tree looks like this

+

- *
/ 5 6 7

3 4

This would result in 3/4 - 5 + (6*7)

I think that I need some kind of inorder traversal of the tree, but I'm not sure how to convert only the numbers from char to double, and then return a value based on what the operations are. I'm thinking I need something similar to an in order print, however somehow store the value of the numbers after the operation. Please help.

[eNc]

code:

+           -         *        /   5      6  7     3  4

Sorry I don't know how to get the formatting to stay.

[wtd]

Do you actually have to parse the tree from a textual representation?

[eNc]

No it is created in java. So far this is what I have

code:

class Tree {         private Operation root;                 public void inPrint()         {                 if(root != null)                          root.inPrint();         }         public void setNodes()         {                 // Create All Nodes                 Operation plus = new Operation('+', null, null);                 Operation minus = new Operation('-', null, null);                 Operation div = new Operation('/', null, null);                 Operation mult = new Operation('*', null, null);                 Operation three = new Operation('3', null, null);                 Operation four = new Operation('4', null, null);                 Operation five = new Operation('5', null, null);                 Operation six = new Operation('6', null, null);                 Operation seven = new Operation('7', null, null);                 root = plus;                 plus.left = minus;                 minus.right = five;                 plus.right = mult;                 mult.left = six;                 mult.right = seven;                 minus.left = div;                 div.left = three;                 div.right = four;         }                 class Operation         {                 char operand;                 Operation left;                 Operation right;                                 Operation(char x, Operation l, Operation r)                 {                         operand = x;                         left = l;                         right = r;                 }                                         void inPrint()                 {                                if(left != null)                                 left.inPrint();                                 Output.print(operand);                         if(right != null)                                 right.inPrint();                 }         }        } class MainClass {         public static void main(String [] args)         {                                      Tree t = new Tree();                 t.setNodes();                 t.inPrint();                 //Output.println(('4' - '0' )+ ('5'-'0'));         } }

The inPrint method is incorrectly named, its what im trying to get the equation solver to be.

[wtd]

Have you covered inheritance?

Oh, and since I've been talking up O'Caml... a solution in that language:

http://rafb.net/paste/results/veBmNS35.html

[eNc]

Not really, we just started.

[eNc]

I kinda get the understanding of your solution in O'Caml however its that like 'knowng' where the branches are. I mean like if you didn't ever see the tree, the method is supposed to work (assuming the tree is in the right order).

[wtd]

My code is a pretty straightforward code version of what a tree is.

Think about the simplest possible tree. It's just a value, right? For instance, we could have a tree that's just the number 42.

Now, what else can a tree be? It can be a branch. Each branch has some operation, and two other things. In the next simplest tree, those are just values. "2 + 2" becomes:

code:

Branch (Plus, Value 2, Value 2)

Now, each part of a branch can also be a branch if it so desires. So we say that a branch or a value are both trees. An understanding of recursion helps here.

[eNc]

I see what you are saying (I think). Basically I should look at lets say a part of the tree like

code:

/     3   4

and recurse to the left most part, then i'd have to visit the 'root' or parent of 3 and 4 to get the operation and then i'd recurse into the right child.
I can do this through an inorder print, however when it comes to actually calculating the values I have trouble, to conver the char to an int I can do 3 - '0' or info - '0', however this would not work if I came across to the /, because / - '0' would return -1 in java (or not work) therfore I tried to identify the operation with and if statement, however when I try to make my current value /= to the next number it doesn't work because my variable is being re-initalized every time

ex/

code:

void inPrint()                 {                                  String s = "";                         if(left != null)                                 left.inPrint();                            if(operand == '+') // this statement would have to go before, and I'd have to check if there was a plus in the previous operand.                                 s += (operand);                         if(right != null)                                 right.inPrint();                 }

I don't want to resort to using global variables, however I think I may have to.[/quote]

[wtd]

So, if I understand correctly, if the two branches are null, then you're using the character that would otherwise be holding a representation of the operation to hold a value?

Interfaces (a form of inheritance) would help you tremdnously here, but with your current scheme I would advise you use a String instead of a char, so you can store larger numbers.

As for knowing if it's a number or an operation... check to see if the branches are null or not. If they're null, then it must be a number. If they're not null, then it must be an operation.

[eNc]

Yes I fully agree with you, however the BST has to be of type char.
and we are under the assumption that the BST is filled so that a mathematical operation is possible.