----------------------------------- eNc Sun Feb 26, 2006 7:45 pm char BST of and equation ----------------------------------- 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 Sun Feb 26, 2006 7:47 pm Re: char BST of and equation ----------------------------------- + - * / 5 6 7 3 4 Sorry I don't know how to get the formatting to stay. ----------------------------------- wtd Sun Feb 26, 2006 8:07 pm ----------------------------------- Do you actually have to parse the tree from a textual representation? ----------------------------------- eNc Sun Feb 26, 2006 8:11 pm ----------------------------------- No it is created in java. So far this is what I have 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 Sun Feb 26, 2006 8:17 pm ----------------------------------- 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 Sun Feb 26, 2006 8:18 pm ----------------------------------- Not really, we just started. ----------------------------------- eNc Sun Feb 26, 2006 8:21 pm ----------------------------------- 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 Sun Feb 26, 2006 8:32 pm ----------------------------------- 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: 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 Sun Feb 26, 2006 8:43 pm ----------------------------------- I see what you are saying (I think). Basically I should look at lets say a part of the tree like / 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/ 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 Sun Feb 26, 2006 8:53 pm ----------------------------------- 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 Sun Feb 26, 2006 9:06 pm ----------------------------------- 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.