java - 数学表达式二叉树

Question

我应该实现一个包含数学表达式的二叉树，为每个二元或一元表达式使用不同的类。例如:

Expression e = new Sin(
                     new Pow(
                        new Mul(
                           new Plus(
                              new Mul(new Num(2), new Var("x")),
                              new Var("y")),
                           new Num(4)),
                     new Var("x")));

树的叶子可以是变量或数字。每个变量都可以使用以下方法转换为另一个表达式:

Expression assign(String var, Expression expression)

我有 2 个用于一元和二元运算符的抽象类。

在弄清楚如何将相同的表达式分配给表达式本身中的变量之一时，我一直遇到困难。例如:

Expression e1 = new Plus(1,"x");
e1.assign("x", e1);
System.out.println(e1.toString());

输出应该是:

((x+1)+1)

实际发生的是表达式的左侧部分指向自身，这导致无限循环。有没有办法复制对象但使用不同的指针来避免它？或者可能是一种不同的方式来实现方法“分配”的工作方式？

这是我的实现:

二进制表达式类:

import java.util.List;
import java.util.Map;


abstract public class BinaryExpression extends BaseExpression implements Expression {

    protected Expression first, second;

    public BinaryExpression(Expression first, Expression second) {
        this.setSecond(second);
        this.setFirst(first);
    }
    public BinaryExpression(double number1, double number2) {
        this(new Num(number1), new Num(number2));
    }
    public BinaryExpression(double number, String variable) {
        this(new Num(number), new Var(variable));
    }
    public BinaryExpression(String variable, double number) {
        this(new Var(variable), new Num(number));
    }
    public BinaryExpression(String variable1, String variable2) {
        this(new Var(variable1), new Var(variable2));
    }
    public BinaryExpression(Expression expression, String variable) {
        this(expression , new Var(variable));
    }
    public BinaryExpression(double number, Expression expression) {
        this(new Num(number), expression);
    }
    public BinaryExpression(Expression expression, double number) {
        this(expression, new Num(number));
    }
    public BinaryExpression(String variable, Expression expression) {
        this(new Var(variable), expression);
    }

    public Expression getSecond() {
        return second;
    }

    public void setSecond(Expression second) {
        this.second = second;
    }

    public Expression getFirst() {
        return first;
    }

    public void setFirst(Expression first) {
        this.first = first;
    }
    public double evaluate(Map<String, Double> assignment) throws Exception {
        try {
            return operate(first.evaluate(assignment), second.evaluate(assignment));
        } catch (Exception e) {
            throw new Exception(e.getMessage());
        }
    }
    abstract public double operate(double first, double second) throws Exception;

    public List<String> getVariables() {
        java.util.List<String> firstList, secondList;
        firstList = this.first.getVariables();
        secondList = this.second.getVariables();
        for (int i = 0; i < secondList.size(); i++) {
            boolean seen = false;
            for (int j = 0; j < firstList.size(); j++) {
                if (((String) firstList.get(j)).equals((String) secondList.get(i))) {
                    seen = true;
                    break;
                }
            }
            if (!seen) {
                firstList.add(secondList.get(i));
            }
        }
        return firstList;
    }

    public Expression assign(String var, Expression expression) {
        this.first = first.assign(var, expression);
        this.second = second.assign(var, expression);
        return this;
    }

    abstract public String operator();

    public String toString() {
        return "(" + this.first.toString() +
               this.operator() +
               this.second.toString() + ")";
    }
}

变量类:

import java.util.ArrayList;
import java.util.List;
import java.util.Map;


public class Var implements Expression {
    private String variable;
    /**
     * setting the desired variable.
     * @param variable the variable to set
     */
    public Var(String variable) {
        this.variable = variable;
    }
    /**
     * getting the variable string.
     * @return the variable string
     */
    public String getVariable() {
        return variable;
    }
    /**
     * setting the variable string.
     * @param newVariable the string we want to set.
     */
    public void setVariable(String newVariable) {
        this.variable = newVariable;
    }
    @Override
    public double evaluate(Map<String, Double> assignment) throws Exception {
        if (assignment.containsKey(this.variable)) {
            return assignment.get(this.variable);
        } else {
            throw new Exception("variable wasn't assigned");
        }
    }
    @Override
    public double evaluate() throws Exception {
        throw new Exception("variable wasn't assigned");
    }
    @Override
    public List<String> getVariables() {
        java.util.List<String> singleVariable = new ArrayList<String>();
        singleVariable.add(this.variable);
        return singleVariable;
    }
    @Override
    public Expression assign(String var, Expression expression) {
        if (var.equals(this.variable)) {
            return expression;
        } else {
            return this;
        }
    }
    public String toString() {
        return this.variable;
    }
}

数字类:

import java.util.ArrayList;
import java.util.List;
import java.util.Map;


public class Num implements Expression {
    private double value;
    /**
     * creating a new number.
     * @param number the value to set.
     */
    public Num(double number) {
        this.setValue(number);
    }
    /**
     * getting the number's value.
     * @return the value to set.
     */
    public double getValue() {
        return value;
    }
    /**
     * setting a new number.
     * @param newValue the number to set.
     */
    public void setValue(double newValue) {
        this.value = newValue;
    }
    @Override
    public double evaluate(Map<String, Double> assignment) {
        return getValue();
    }
    @Override
    public double evaluate() {
        return getValue();
    }
    @Override
    public List<String> getVariables() {
        java.util.List<String> emptyList = new ArrayList<String>();
        return emptyList;
    }
    @Override
    public Expression assign(String var, Expression expression) {
        return this;
    }
    public String toString() {
        return Double.toString(this.value);
    }
}

感谢任何形式的帮助。

我在这里添加我遇到的错误:

Exception in thread "main" java.lang.StackOverflowError
    at sun.misc.FloatingDecimal$BinaryToASCIIBuffer.dtoa(Unknown Source)
    at sun.misc.FloatingDecimal$BinaryToASCIIBuffer.access$100(Unknown Source)
    at sun.misc.FloatingDecimal.getBinaryToASCIIConverter(Unknown Source)
    at sun.misc.FloatingDecimal.getBinaryToASCIIConverter(Unknown Source)
    at sun.misc.FloatingDecimal.toJavaFormatString(Unknown Source)
    at java.lang.Double.toString(Unknown Source)
    at Num.toString(Num.java:50)
    at BinaryExpression.toString(BinaryExpression.java:94)
    at BinaryExpression.toString(BinaryExpression.java:94)
    at BinaryExpression.toString(BinaryExpression.java:96)
    at BinaryExpression.toString(BinaryExpression.java:94)
    at BinaryExpression.toString(BinaryExpression.java:96)
    at BinaryExpression.toString(BinaryExpression.java:94)
    at BinaryExpression.toString(BinaryExpression.java:96)
    at BinaryExpression.toString(BinaryExpression.java:94)
    at BinaryExpression.toString(BinaryExpression.java:96)
    at BinaryExpression.toString(BinaryExpression.java:94)
    at BinaryExpression.toString(BinaryExpression.java:96)
    at BinaryExpression.toString(BinaryExpression.java:94)
    at BinaryExpression.toString(BinaryExpression.java:96)...

这里是Plus类中clone方法的一个例子:

public Expression clone() {
    Expression newFirst = this.first, newSecond = this.second;
    return new Plus(newFirst, newSecond);
}

我试图通过以这种方式更改分配的 Var 方法来使用它:

public Expression assign(String var, Expression expression) {
    if (var.equals(this.variable)) {
        return expression.clone();
    } else {
        return this;
    }
}

此外，在使用另一个函数更改 var 中的方法无效后，我还尝试通过这种方式更改分配方法来修复它:

public Expression assignHelp(String var, Expression expression) {
    this.first = first.assignHelp(var, expression);
    this.second = second.assignHelp(var, expression);
    return this;
}
public Expression assign(String var, Expression expression) {
    return assignHelp(var, expression.clone());
}

Answer 1

(来自评论)

让表达式实现Clonable，并调用expression.clone()。

clone() 也应该克隆内部元素(深拷贝)

所以，克隆看起来像

public Expression clone() {
    return new Plus(this.first.clone(), this.second.clone());
}