从前缀表示法构建二进制表达式树？

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;
}

}

这是我的代码，当给定*+5 4-3/2 1这样的表达式时，我希望返回一个表达式树。我得到的输出如下所示：

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

当我想要得到：

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

有什么建议吗？为什么我的树中唯一的元素是表达式的最后两个元素？我觉得我漏掉了一些明显的东西。

Answer 1

您正在使用字段存储表达式节点程序集的中间结果。在对您正在使用的createExpressionTree(...)的递归调用中，这些代码会被覆盖。

如果将方法修改为使用局部变量作为临时值，那么一切都应该正常工作(也可以从类定义中删除字段)。

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);
}