Построение двоичного дерева

Question

Я строю выражение в двоичном дереве каждый раз, когда он катится по циклу, создавая новое дерево в каждом конце «)» и выталкивая эти операторы/операнды в стек, чтобы выталкиваться обратно в один полный двоичное дерево.

Мой метод сборки:

package lab5; 

import net.datastructures.*; 

public class Expression<T> { 

/** Contain Linked Tree and Linked Stack instance variables **/ 
LinkedBinaryTree<T> tree; 
LinkedStack<LinkedBinaryTree<T>> stack; 


public Expression() { 
    tree = new LinkedBinaryTree<T>(); 
    stack = new LinkedStack<LinkedBinaryTree<T>>(); 

} // end constructor 

public LinkedBinaryTree<T> buildExpression (String expression) {// LinkedBinaryTree<T> is a type of LinkedBinaryTree 
    // major TODO to implement the algorithm] 
    LinkedBinaryTree<T> operand, op1, op2; 
    LinkedStack<LinkedBinaryTree<T>> newStack = new LinkedStack<LinkedBinaryTree<T>>(); 
    String symbol; 

    int i = 0; 
    int len = expression.length(); 

    for (i = 0; i < len; i++) { 
     symbol = expression.substring(i, i+1); 

     if ((!symbol.equals ("(")) && (!symbol.equals (")"))) { 
      operand = new LinkedBinaryTree<T>(); 
      operand.addRoot((T)symbol); 
      newStack.push(operand); 
     } else if (symbol.equals ("(")){ 
      continue; 
     } else { 
      op2 = newStack.pop(); 
      operand = newStack.pop(); 
      op1 = newStack.pop(); 
     tree.attach(operand.root(), op1, op2); 
     newStack.push(tree); 
     } 
    } 
    tree = newStack.pop(); 
    return tree; 

} // end method buildExpression 

}

Мой Тест:

package lab5; 
import net.datastructures.*; 

public class ExpressionTest { 

/** 
* @param args 
* @throws EmptyTreeException 
*/ 

/** Paranthesize is code fragment 8.26 pg. 346 **/ 

/** evaluateExpression method apart of LinkedBinaryTree class in net.datastructures **/ 

public static void main(String[] args) { 
    // declare local variables/objects 
      String s = new String(); 
      String exp = "((((3+1)x3)/((9-5)+2))-((3x(7-4))+6))"; //-13 
      Expression<String> expression = new Expression<String>(); 

      // print the expression string 
      System.out.printf ("The original Expression String generated via printf: %s", exp); 

      // create the tree using the 'stub' method 
      // i.e. it does nothing 
      LinkedBinaryTree<String> tree = expression.buildExpression (exp); 

      // use Object.toString simply to print its reference 
      System.out.printf ("\n\nThe Tree: %s\n", tree); 

    } 

} 

Я получаю NullPointerException, и я не знаю, почему. Нужно ли мне «Попробовать», а затем пропустить ошибку?

Answer 1

Ошибка, вероятно, связана с проверкой на '(' (одинарные кавычки) вместо "(" (двойные кавычки) в symbol.equals ('('). Вы сравниваете строку с символом, который никогда не будет равным.

Возможно, также stack не инициализирован? Он должен быть локальным до buildExpression().

Обратите внимание, что ваш фрагмент кода не будет компилироваться:

• stack не определен
• symbol не определен

КСТАТИ: buildExpression() может быть статическим, что бы избежать пустой неиспользованными распределение выражений в основном.

Проверка на "(" в первую очередь позволит избежать проверки на "(" дважды.