Mathematical expressions binary tree

Question

I'm supposed to implement a binary tree that holds mathematical expressions, using different classes for each binary or unary expression. for example:

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

The leaves of the tree can be either variable or numbers. Each variable could be converted to another expression with the method:

Expression assign(String var, Expression expression)

I have 2 abstract classes for unary and binary operators.

I've been experiencing difficulties figuring out how to assign the same expression to one of the variables in the expression itself. For example:

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

the output should be:

((x+1)+1)

What's actually happening is that the left part of the expression is pointing on itself which causes an infinite loop. Is there a way to make a duplication of the object but with a different pointer to avoid it? Or maybe a different way to implement the way that the method "assign" works?

Here is my implementation:

BinaryExpression Class:

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() + ")";
    }
}

Variable class:

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

Number class:

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

Any kind of help is appreciated.

I'm adding here the error I'm getting:

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

Here is an example to the clone method in Plus class:

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

I was trying to use it by changing the Var method of assign this way:

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

Furthermore I also tried to fix it by changing the assign method this way after changing the method in var didn't work by using another function:

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

(From comments)

Have expression implement Clonable, and call expression.clone().

clone() should clone the inner elements too (deep copy)

So, clone looks something like

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