Создать двоичное дерево выражений из префиксного обозначения?

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