從前綴符號構建二進制表達式樹？

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