java - 在java中使用stacks(LinkedList)实现表达式树如下，但有错误

Question

我尝试使用 stacks(LinkedList) 来实现表达式树，但在编译时出现以下错误。

Note: ExpressionTree.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

import java.util.LinkedList;

public class ExpressionTree implements ExpressionTreeInterface{
    private ExpressionNode root;
    public ExpressionTree(String expression){
        LinkedList l = new LinkedList();
        String[] s = expression.split(" ");
        int i=0;
        for (String a:s){
            if (a == "0" || a == "1" || a == "2" || a == "3" ||a == "4" ||a == "5" ||
                    a == "6" ||a == "7" ||a == "8" ||a == "9"){
                int b = Integer.parseInt(a);
                ExpressionNode e = new ExpressionNode();
                e.operand(b);
                l.add(e);
            }
            else if (a == "*" || a == "/" || a == "+" || a == "-"){
                ExpressionNode e = new ExpressionNode();
                e.operator(a);
                e.right = (ExpressionNode)l.get(l.size()-1);
                e.left = (ExpressionNode)l.get(l.size()-2);
                l.remove(l.size()-1);
                l.remove(l.size()-2);
                l.add(e);
            }
        }
        root = (ExpressionNode)l.get(0);
    }
    public int eval(){
        return eval(root);
    }
    public int eval(ExpressionNode r){
        if (r.left!=null && r.right!=null){
            if (r.getOperator() == "+"){
                return eval(r.left) + eval(r.right);
            } else if (r.operator == "*"){
                return eval(r.left) * eval(r.right);
            } else if (r.operator == "/"){
                return eval(r.left) / eval(r.right);
            } else {
                return eval(r.left) - eval(r.right);
            }
        } else {
            return r.getOperand();
            }

        }
    private static class ExpressionNode{
        int operand;
        String operator;
        ExpressionNode left;
        ExpressionNode right;
        public void operator(String operator){
            this.operator = operator;
        }
        public void operand(int operand){
            this.operand = operand;
        }
        public String getOperator(){
            return operator;
        }
        public int getOperand(){
            return operand;
        }
    }
    public String postfix(){
        return postfix(root).trim();
    }
    private String postfix(ExpressionNode s){
        if (s.left == null && s.right == null){
            return Integer.toString(s.getOperand());
        } else{
            return postfix(s.left) + " " + postfix(s.right) + " " + s.getOperator();
        }
    }
    public String prefix(){
        return prefix(root).trim();
    }
    private String prefix(ExpressionNode s){
        if (s.left == null && s.right == null){
            return Integer.toString(s.getOperand());
        } else{
            return s.getOperator() + " " + prefix(s.left) + " " + prefix(s.right);
        }
    }
    public String infix(){
        return infix(root).trim();
    }
    private String infix(ExpressionNode s){
        if (s.left == null && s.right == null){
            return Integer.toString(s.getOperand());
        } else{
            return infix(s.left) + " " + s.getOperator() + " " + infix(s.right);
        }  
    }
}

此外，我创建了以下测试类，但它再次出现以下错误。

at java.util.LinkedList.checkElementIndex(LinkedList.java:555)
at java.util.LinkedList.get(LinkedList.java:476)
at ExpressionTree.<init>(ExpressionTree.java:27)
at Testfile.main(Testfile.java:4)

public class Testfile {
    public static void main(String[] args){
        String a = "34 2 - 5 *";
        ExpressionTree s = new ExpressionTree(a);
        System.out.println(s.eval());
    }
}

我哪里做错了？我想我使用了很多递归，所以也许那里有错误，但我不知道在哪里。

Answer 1

您的代码中存在一些问题:

第一个问题是您无法使用 == 运算符来比较 java 中的字符串，您需要使用 .equals() 等函数来比较两个字符串值。所以，这段代码片段:

if (a == "0" || a == "1" || a == "2" || a == "3" ||a == "4" ||a == "5" ||
                a == "6" ||a == "7" ||a == "8" ||a == "9")

更改为:

 if (a.equals("0")|| a.equals("1") ||a.equals("2") || a.equals("3") ||a.equals("4") ||a.equals("5") ||
                    a.equals("6") ||a.equals("7") ||a.equals("8") ||a.equals("9"))

这部分代码片段也是如此:

else if (a == "*" || a == "/" || a == "+" || a == "-")

您还需要在此使用 .equals 函数。

这部分的 eval 函数也存在同样的问题:

if (r.left!=null && r.right!=null){
        if (r.getOperator() == "+"){
            return eval(r.left) + eval(r.right);
        } else if (r.operator == "*"){
            return eval(r.left) * eval(r.right);
        } else if (r.operator == "/"){
            return eval(r.left) / eval(r.right);
        } else {
            return eval(r.left) - eval(r.right);
        }
    } else {
        return r.getOperand();
        }

第二个问题是，在输入表达式字符串(“34 2 - 5 *”)中，其中一个字符串是34，但它不满足这种情况:

  if (a == "0" || a == "1" || a == "2" || a == "3" ||a == "4" ||a == "5" ||
                    a == "6" ||a == "7" ||a == "8" ||a == "9")

因此，您可以创建辅助函数来执行相同的操作并调用相同的方法，而不是通过这种方式检查字符串是否为数字:

 private boolean checkStringIsNumber(String s) {
    boolean numeric = true;

    try {
        Integer num = Integer.parseInt(s);
    } catch (NumberFormatException e) {
        numeric = false;
    }
    return numeric;
}

第三期在这两行中:

 l.remove(l.size()-1);
 l.remove(l.size()-2);

假设此时你的链接列表有两个节点。 l1之后，l2。执行第一条语句后

l.remove(l.size()-1);

更新后的链接列表将包含一个节点，即 l1。现在如果你执行这条语句

 l.remove(l.size()-2);

它将抛出异常，因为链接列表大小现在为 1，并且 l.size()-2 将返回 -1，这是无效索引；

所以，我想您想删除最后 2 个节点，这样您就可以这样做，而不是这两个语句:

 l.remove(l.size()-1);
 l.remove(l.size()-1);

因此，解决所有这些问题后，ExpressionTree构造函数的更新代码是:

 public ExpressionTree(String expression){
        LinkedList l = new LinkedList();
        String[] s = expression.split(" ");
        int i=0;
        for (String a:s){
            if (checkStringIsNumber(a)){
                int b = Integer.parseInt(a);
                ExpressionNode e = new ExpressionNode();
                e.operand(b);
                l.add(e);
            }
            else if (a.equals("*") || a.equals("/") || a.equals("+") || a.equals("-")){
                ExpressionNode e = new ExpressionNode();
                e.operator(a);
                e.right = (ExpressionNode)l.get(l.size()-1);
                e.left = (ExpressionNode)l.get(l.size()-2);
                l.remove(l.size()-1);
                l.remove(l.size()-1);
                l.add(e);
            }
        }
        root = (ExpressionNode)l.get(0);
    }

和eval函数的更新代码是:

 public int eval(ExpressionNode r){
    if (r.left!=null && r.right!=null){
        if (r.getOperator().equals("+")){
            return eval(r.left) + eval(r.right);
        } else if (r.operator.equals("*")){
            return eval(r.left) * eval(r.right);
        } else if (r.operator.equals("/")){
            return eval(r.left) / eval(r.right);
        } else {
            return eval(r.left) - eval(r.right);
        }
    } else {
        return r.getOperand();
        }

}

进行这些更改后，上面的表达式字符串工作正常并给出结果为 160。