从前缀表示法构建二进制表达式树? [英] Build binary expression tree from prefix notation?

问题描述

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的表达式时，我想返回一个表达式树.我得到的输出是这样的:

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

当我尝试获取时:

     *
     /\
    +  -
   /\   /\
  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.

推荐答案

您正在使用字段来存储表达式节点程序集的临时结果.这些将在您正在使用的createExpressionTree(...)的递归调用中被覆盖.

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

这篇关于从前缀表示法构建二进制表达式树?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！