Build binary expression tree from prefix notation?

Question

import java.util.ArrayList;
import java.util.List;

public class ExpressionTree {

List<String> expArray = new ArrayList<String>();
ExpressionTreeNode root;
ExpressionTreeNode curNode;
ExpressionTreeNode left;
ExpressionTreeNode right;
String element;

public ExpressionTree(String prefixExpression) {
    String[] temp = prefixExpression.split(" ");
    for (int i = 0; i < temp.length; i++) {
        expArray.add(temp[i]);
    }
    root = createExpressionTree(expArray);
    System.out.println(root);
}

private ExpressionTreeNode createExpressionTree(List<String> prefixExpression) {
    element = prefixExpression.get(0);
    prefixExpression.remove(0);
    if (isNumeric(element)) {
        return new Leaf(Double.parseDouble(element));
    } else {
        left = createExpressionTree(prefixExpression);
        right = createExpressionTree(prefixExpression);
    }
    return new ExpressionTreeNode(left, right, element);
}

private static boolean isNumeric(String str) {
    try {
        double d = Double.parseDouble(str);
    } catch(NumberFormatException nfe) {
        return false;
    }
    return true;
}

}

That is my code that I want to return an expression tree when given an expression like * + 5 4 – 3 / 2 1. The output i'm getting though is something like this:

1
|\
2 1
  /\
  2 1
    /\
    2 1

When I'm trying to get:

     *
     /\
    +  -
   /\   /\
  5  4  3  /
           /\
           2 1

Any tips? Why are the only elements of my tree the last two elements of the expression? I feel like I'm missing something obvious.

Answer 1

You are using fields to store the interim results of expression node assembly. These get overwritten in the recursive calls to createExpressionTree(...) you are using.

If you modify the method to use local variables for the interim values, then everything should work fine (you can also remove the fields from the class definition as well).

private ExpressionTreeNode createExpressionTree(List<String> prefixExpression) {
    String element = prefixExpression.get(0);
    prefixExpression.remove(0);
    if (isNumeric(element)) {
        return new Leaf(Double.parseDouble(element));
    }
    ExpressionTreeNode left = createExpressionTree(prefixExpression);
    ExpressionTreeNode right = createExpressionTree(prefixExpression);
    return new ExpressionTreeNode(left, right, element);
}