0

I created a Binary Tree of an expression and has the operators (+, -, /, *) as roots and operands (values) as the children left/right. I need to evaluate that expression in the Binary Tree taking the parameters (T, v) where 'T' is the binary tree and 'v' is a node where postorder traversal starts.

I have searched on how postorder traversal works and all of that which I understand. But I don't know how to implement the code using a node 'v' for the postorder traversal.

My method looks like this...

public int evaluateExpression (LinkedBinaryTree<T> tree, Position<T> v) {

}

This should return the operator being used on its operators (children of the root). So, I understand what to do, I am stuck on how to actually do it. -.-

David Arce
  • 45
  • 1
  • 6

2 Answers2

3

You don't need to provide the entire tree, and you don't need a separate Position class. Every subtree is a tree. You just need something of this kind:

public class <T extends Number> ExpressionTree<T> {
    private ExpressionTree<T> left, right;
    private T value;
    private int operator;

    // constructors, getters, setters, etc. elided

    public T evaluateExpression() {
        // Here I am assuming a <T> value field that is set if the node
        // is a literal value rather than an expression subtree with left and right children.
        if (this.value != null)
            return this.value;
        // Evaluate the subtree
        switch (this.operator) {
        case '+':
            return left.evaluateExpression()+right.evaluateExpression();
        // etc for the other operators
        }
    }

You should not use the LinkedBinaryTree class mentioned in comments below. It is not designed for this purpose in any way, and appears to me to be needlessly complex even for its own purpose.

user207421
  • 305,947
  • 44
  • 307
  • 483
  • Okay I see what you are doing. I would like to understand this a little more. When you are using tree.value and tree.operator, where are you getting 'value' and 'operator' from? – David Arce Apr 12 '16 at 23:51
  • From the tree node, which will be something like `class LinkedBinaryTree { LinkedBinaryTree left,right; int operator; T value; }`. – user207421 Apr 12 '16 at 23:56
  • @EJP upvoted for helping with this "nice" API: http://net3.datastructures.net/doc5/net/datastructures/LinkedBinaryTree.html :) – Stefan Haustein Apr 13 '16 at 00:00
  • This is what really confuses me about Java (I am still pretty new). Am I creating a tree node, or is that node already defined when I create my Binary Tree? – David Arce Apr 13 '16 at 00:00
  • @StefanHaustein Yes thats the package I am importing net.datastructures for Linked Binary Tree! That link is useful, I just like to understand everything that is going on so I can really grasp what I am creating. – David Arce Apr 13 '16 at 00:02
  • @DavidArce Yes and yes. A tree node is a subtree is a tree. They aren't two different things, or three. The API you're using is inappropriate. I would just use the definition I've given here, plus constructors and methods. – user207421 Apr 13 '16 at 00:06
  • Got it. I am going to try this out. I will post here if I have any questions. If this works out I will definitely choose your answer and I already upvoted (hidden). Thanks so far! – David Arce Apr 13 '16 at 00:07
  • @StefanHaustein I didn't help with that API and in fact I've never heard of it. It is violently unsuitable for this purpose. It is for implementing binary search trees, not expression trees. – user207421 Apr 13 '16 at 00:08
  • Very, very confusing to me as well. It's from this book...http://www.wiley.com/WileyCDA/WileyTitle/productCd-EHEP002900.html – David Arce Apr 13 '16 at 00:11
  • It is not understanding what `value` or `operand` is. I tried putting `.root()` because it returns the root of the LinkedBinaryTree but that's supposed to be the Operator, and I don't know why it doesn't understand the `tree.left` or `tree.right` – David Arce Apr 13 '16 at 00:23
  • @DavidArce I've answered that. I cannot help you if you're going to keep using the wrong API for the job. That one is a data structure for binary searching. You don't need anything anywhere near as complex. You don't need much beyond what I gave you above. – user207421 Apr 13 '16 at 00:26
  • @EJP It is required for my whole class to use it. If I had a choice, I wouldn't be using it. Edit: I understand if you cannot help, and I will still provide you with best answer because it is correct. – David Arce Apr 13 '16 at 00:27
  • 1
    Then I would complain. Show the teacher this thread. I am a compiler writer and I wouldn't use that class for this purpose in a million years. He has set you a pointless task that does not illuminate evaluating expression trees, which is presumably what he's trying to teach you. – user207421 Apr 13 '16 at 00:28
  • Sounds good to me, I will bring it up to him. I appreciate all the help that has been given here. – David Arce Apr 13 '16 at 00:29
0

Normally, in the real world, you would do this as EJP suggests.

That said, a postorder iterator will give you the the values and the operators stored in the tree in the right order to do basically this:

  • If the element is a number, push it on a number stack
  • If the element is an operation, pop two elements from the number stack, process them according to the operation and push the result

After the traversal, return the only element on the stack

Stefan Haustein
  • 18,427
  • 3
  • 36
  • 51
  • I don't understand why you would use a stack when you already have a tree. – user207421 Apr 13 '16 at 00:37
  • Well the original question was about postorder so I just assumed that's the way they have to do it... I am in no way affiliated with the book or API and I share your sentiment towards it -- just got "burned" by it before, trying to help here:  http://stackoverflow.com/questions/36522929/building-a-binary-tree/36523591#36523591 – Stefan Haustein Apr 13 '16 at 00:44
  • I see what you are doing there. I will do that probably as a last ditch effort. – David Arce Apr 13 '16 at 01:20