Computer Science Canada

char BST of and equation
Author:  eNc [ Sun Feb 26, 2006 7:45 pm ]
Post subject:  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.
Author:  eNc [ Sun Feb 26, 2006 7:47 pm ]
Post subject:  Re: char BST of and equation
code:
      +

          -         *
       /   5      6  7

    3  4


Sorry I don't know how to get the formatting to stay.
Author:  wtd [ Sun Feb 26, 2006 8:07 pm ]
Post subject: 
Do you actually have to parse the tree from a textual representation?
Author:  eNc [ Sun Feb 26, 2006 8:11 pm ]
Post subject: 
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.
Author:  wtd [ Sun Feb 26, 2006 8:17 pm ]
Post subject: 
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
Author:  eNc [ Sun Feb 26, 2006 8:18 pm ]
Post subject: 
Not really, we just started.
Author:  eNc [ Sun Feb 26, 2006 8:21 pm ]
Post subject: 
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).
Author:  wtd [ Sun Feb 26, 2006 8:32 pm ]
Post subject: 
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. Smile
Author:  eNc [ Sun Feb 26, 2006 8:43 pm ]
Post subject: 
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]
Author:  wtd [ Sun Feb 26, 2006 8:53 pm ]
Post subject: 
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.
Author:  eNc [ Sun Feb 26, 2006 9:06 pm ]
Post subject: 
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.

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy