Expression Tree to Infix: Null in one instance, but not in another?

I have an expression tree class, which has a method buildExpressionTreeFromQueue. As its name suggests, the method takes a queue (just a series of operators and operands) and cycles through it, adding nodes to the tree appropriately.

My problem is this: when I try to write the tree as Infix notation (or Prefix or Postfix for that matter, but we can focus on Infix because I am sure the problem is the same for all of them), it does not come up with the right answer.

Here's the algorithm I'm using:

private void infix(Node t)
{
 if(t.left != null)
 {
  System.out.print("(");
  infix(t.left);
 }
 System.out.print(t.element);
 if(t.right != null)
 {
  infix(t.right);
  System.out.print(")");
 }
}

Some sample data:

Postfix (queue): 300 23 + 43 21 - * 84 7 + /

Here's how my code inserts these items into the tree:

public void buildExpressionTreeFromQueue(QueueAr queue)
{
 StackLi stack = new StackLi();

 Object item = queue.dequeue();
 while (item != null)
 {
  if (this.isOperator(item))
  {
   Object t1 = stack.topAndPop();
   Object t2 = stack.topAndPop();
   Node node = new Node(item, new Node(t2), new Node(t1));
   stack.push(node);
  }
  else
  {
   Node node = new Node(item);
   stack.push(node);
  }
  item = queue.dequeue();
 }
 this.root = (Node)stack.top();
}

Now, I kickstart the infix() method with infix(this.root), which is now an expression tree that represents the Postfix expression from above. In this case, infix() should return (((300+23)*(43-21))/(84+7)). Instead, it simply returns (*/+).

I've done some investigating and it seems that t.left is indeed null when we hit *. What I don't understand is why.

When I print out some debugging info in my Node class, it seems that t.left and t.right are not null where they shouldn't be (i.e., they aren't null for operators). For example, if I implement toString for the Node class like this:

public String toString()
{
 return "" + element + ( left != null ? " left of " + element + " is " + left : "" );
}

the Infix output is: (* left of * is + left of + is 300/+ left of + is 84), which explictly says that the left of * is +, not null.

Herein lies the problem. Why are the child nodes null for everything past the root in infix() but not so in toString()?

ansaurus

tags:

views:

answers:

Expression Tree to Infix: Null in one instance, but not in another?

related questions