建立一棵二叉树 [英] Building a Binary Tree

问题描述

每次表达式遍历循环时，我都会在二进制树中构建一个表达式，在)"的每个结尾处创建一个新树，并将这些运算符/操作数推入堆栈中，然后弹出一个完整的二进制树./p>

我的构建方法:

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，但不知道为什么.我需要尝试"然后让错误逐步解决吗?

解决方案

该错误可能与检查'('(单引号)而不是检查symbol.equals ('(')中的"("(双引号)有关.您将字符串与字符进行比较，这将永远不会相等.

也许stack也没有初始化?它应该在buildExpression()本地.

请注意，您的代码段不会编译:

• stack未定义
• symbol未定义

BTW:buildExpression()可以是静态的，这可以避免main中未使用的空表达式分配.

首先检查"("可以避免两次检查"(".

I build an expression into a binary tree each time it rolls through the loop, creating a new tree at each ending of ")" and pushing those operators/operands into a stack to be popped back into one complete binary tree.

My Build Method:

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

}

My Test:

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

    }

}

I am getting a NullPointerException and I do not know why. Do I need to 'Try' and then let the error roll through?

解决方案

The error probably is related to checking for '(' (single quotes) instead of "(" (double quotes) in symbol.equals ('('). You compare a string to a character, which will never be equal.

Maybe also stack is not initialized? It should be local to buildExpression().

Note that your code snippet won't compile:

• stack is not defined
• symbol is not defined

BTW: buildExpression() could be static, that would avoid the empty unused expression allocation in main.

Checking for "(" first would avoid checking for "(" twice.

这篇关于建立一棵二叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！