Biểu thức toán học cây nhị phân

Question

Tôi phải triển khai cây nhị phân chứa biểu thức toán học, sử dụng các lớp khác nhau cho mỗi biểu thức nhị phân hoặc đơn nhất. ví dụ:

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

Lá của cây có thể là biến hoặc số. Mỗi biến có thể được chuyển đổi thành một biểu thức khác với phương thức:

Expression assign(String var, Expression expression) 

Tôi có 2 lớp trừu tượng cho toán tử đơn và nhị phân.

Tôi đã gặp khó khăn trong việc tìm cách chỉ định cùng một biểu thức cho một trong các biến trong chính biểu thức đó. Ví dụ:

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

đầu ra nên là:

((x+1)+1) 

gì thực sự xảy ra là phần bên trái của biểu thức được chỉ trên chính nó gây ra một vòng lặp vô hạn. Có cách nào để tạo một bản sao của đối tượng nhưng với một con trỏ khác để tránh nó? Hoặc có thể một cách khác để thực hiện cách thức mà phương thức "gán" hoạt động?

Đây là triển khai thực hiện của tôi:

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

Biến lớp:

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

Số lớp:

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

Bất kỳ loại giúp đỡ là apprec iated.

tôi thêm ở đây lỗi tôi nhận được:

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

Dưới đây là một ví dụ để các phương pháp nhân bản trong lớp Plus:

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

Tôi đã cố gắng sử dụng nó bằng cách thay đổi phương pháp Var chỉ định theo cách này:

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

Hơn nữa, tôi cũng cố khắc phục bằng cách thay đổi lệnh gán od cách này sau khi thay đổi phương pháp trong var không làm việc bằng cách sử dụng chức năng khác:

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

(Từ comments)

đã biểu thực hiện Clonable, và gọi expression.clone().

clone() nên sao chép các yếu tố bên trong quá (bản sao sâu)

Vì vậy, bản sao trông giống như

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