列表分組由對象字段和計數的發生

Question

我有一個List<TermNode>其中包含操作的所有操作數，如+或*。也就是說，它不是一個二叉樹結構，而是一個樹，其中每個節點可能包含多個子節點。 A TermNode可以是變量，運算符，函數或數字。一個數字和一個變量節點包含一個空的兒童列表（將孩子視爲一個操作的參數）。

public class TermNode { 

    /** 
    * The value this {@link TermNode} holds. 
    */ 
    private String value; 

    /** 
    * The arguments of this {@link TermNode}. 
    * 
    * This {@link List} is empty if the {@link TermTypeEnum} of this {@link TermNode} 
    * is either {@link TermTypeEnum}.NUMBER or {@link TermTypeEnum}.VARIABLE. 
    */ 
    private List<TermNode> children; 

    /** 
    * The {@link TermTypeEnum} of this {@link TermNode}. 
    */ 
    private TermTypeEnum type; 

    public TermNode(ComplexNumber number) { 
     this(number.toString(), new ArrayList<TermNode>(), TermTypeEnum.NUMBER); 
    } 

    public TermNode(String variable) { 
     this(variable, new ArrayList<TermNode>(), TermTypeEnum.VARIABLE); 
    } 

    public TermNode(Operator operator, List<TermNode> children) { 
     this(operator.getOperator(), children, TermTypeEnum.OPERATOR); 
    } 

    public TermNode(Function function, List<TermNode> children) { 
     this(function.getName(), children, TermTypeEnum.FUNCTION); 
    } 

    public TermNode(String value, List<TermNode> children, TermTypeEnum type) { 
     this.value = value; 
     this.children = children; 
     this.type = type; 
    } 

    public TermNode(TermNode node) { 
     this.value = node.getValue(); 
     this.children = node.getChildren(); 
     this.type = node.getType(); 
    } 

    /** 
    * 
    * @return The value of this {@link TermNode}. 
    */ 
    public String getValue() { 
     return value; 
    } 

    /** 
    * 
    * @return The {@link List} of arguments for this {@link TermNode}. 
    */ 
    public List<TermNode> getChildren() { 
     return children; 
    } 

    /** 
    * 
    * @return The {@link TermTypeEnum} of this {@link TermNode}. 
    */ 
    public TermTypeEnum getType() { 
     return type; 
    } 

    /** 
    * 
    * @return True, if this {@link TermNode} represents a {@link ComplexNumber}. 
    */ 
    public boolean isNumber() { 
     return this.type == TermTypeEnum.NUMBER; 
    } 

    /** 
    * 
    * @return True, if this {@link TermNode} represents a variable. 
    */ 
    public boolean isVariable() { 
     return this.type == TermTypeEnum.VARIABLE; 
    } 

    /** 
    * 
    * @return True, if this {@link TermNode} represents an {@link Operator}. 
    */ 
    public boolean isOperator() { 
     return this.type == TermTypeEnum.OPERATOR; 
    } 

    /** 
    * 
    * @return True, if this {@link TermNode} represents a {@link Function}. 
    */ 
    public boolean isFunction() { 
     return this.type == TermTypeEnum.FUNCTION; 
    } 

    /** 
    * 
    * @return A {@link HashSet} object to compare two {@link TermNode} elements in equality. 
    */ 
    public HashSet<TermNode> getHash() { 
     return new HashSet<>(children); 
    } 

} 

爲了簡化像x + x + x + x或sin(x) * sin(x)我已經開始執行，其更新像x + x + x + x一個節點到4 * x節點的方法的表達式。

---

首先表達，我將提供一個例子用表達x + x + x + x：

1. 計算反向polnish符號/後修復順序的表達。

   結果是x x x x + + +。

2. 用TermNodes（參見上面的代碼TermNode）創建表達式樹/術語樹。算法是以下之一：

   public void evaluate() { 
       Stack<TermNode> stack = new Stack<TermNode>(); 
   
       for(String token : rpn) { 
        if(OperatorUtil.containsKey(token)) { 
         Operator operator = OperatorUtil.getOperator(token); 
         List<TermNode> children = new ArrayList<TermNode>() {{ 
          add(stack.pop()); 
          add(stack.pop()); 
         }}; 
   
         TermNode node = simplifyOperator(operator, children); 
         stack.push(node); 
        } else if(FunctionUtil.containsKey(token.toUpperCase())) { 
         Function function = FunctionUtil.getFunction(token.toUpperCase()); 
         List<TermNode> children = new ArrayList<TermNode>(function.getNumParams()); 
   
         for(int i = 0; i < function.getNumParams(); i++) { 
          children.add(stack.pop()); 
         } 
   
         TermNode node = simplifyFunction(function, children); 
         stack.push(node); 
        } else { 
         if(VariableUtil.containsUndefinedVariable(token.toUpperCase())) { 
          stack.push(new TermNode(token)); 
         } else { 
          stack.push(new TermNode(new ComplexNumber(token))); 
         } 
        } 
       } 
   } 
   

3. 某處在simplifyOperator方法我想摺疊具有相同的值的變量。對於上面的表達式中，樹是這個樣子：

     _______ OPERATOR _______ 
        /   "+"   \ 
        /  /  \   \ 
       VARIABLE VARIABLE VARIABLE VARIABLE 
        "x"   "x"  "x"   "x" 
   

4. 的目標是通過在TreeNode評估children領域這棵樹轉換爲簡單的樹：這個表達式由一個OPERATOR TermNode與運營商+與。其中包含了VARIABLE TermNode與價值x 倍（未四次相同TermNode兒童List<TermNode>，僅有4 TermNodes具有完全相同的價值觀，兒童和類型下面是當我的問題進來：

   private TermNode rearrangeTerm(Operator operator, List<TermNode> children) { 
       Map<TermNode, Integer> occurrences = children.stream() 
         .collect(Collectors.groupingBy(term -> term, Collectors.summingInt(term -> 1))); 
   
       List<Pair<TermNode, Integer>> simplification = occurrences.entrySet().stream() 
         .map(entry -> new Pair<TermNode, Integer>(entry.getKey(), entry.getValue())).collect(Collectors.toList()); 
   
       List<TermNode> rearranged = simplification.stream().map(pair -> rearrangeTerm(operator, pair)).collect(Collectors.toList()); 
   
       return new TermNode(operator.getOperator(), rearranged, TermTypeEnum.OPERATOR); 
   } 
   

   此方法正在被傳遞的參數rearrangeTerm(operator, children)到方法，其中，操作者是我們+運營商和children是我們的含有可變x四倍TermNode元素列表調用。

   此時term -> termCollectors.groupingBy不會將TermNode元素按其字段值（值，子級和類型）分組，而是將其作爲TermNode引用自身。所以問題是，我怎麼能TermNode元素由他們的字段（兩個TermNode元素是相等的，如果所有他們的領域匹配（在子列表中的元素的順序可能是不同的，但重要的是，發生的每個TermNode匹配的子項列表中的元素，當然TermNode類型也必須匹配，這裏的問題只是如何更改rearrangeTerm方法，以便Map僅包含一個條目（「x」， 4）用於表達x + x + x + x？

Answer 1

謝謝您的回答，我最終不得不重寫equals(Object obj)和hashCode()我的TermNode類。

我跟着多個計算器網站，用這種方法：

@Override 
public boolean equals(Object other) { 
    if(this == other) { 
     return true; 
    } 

    if((other == null) || (other.getClass() != this.getClass())) { 
     return false; 
    } 

    TermNode node = (TermNode)other; 

    return this.value.equals(node.getValue()) 
      && PlotterUtil.isEqual(this.children, node.getChildren()) 
      && this.type == node.getType(); 
} 

由於TermNode類包含一個List<TermNode>場，一個需要檢查的參數列表等於爲好，但忽視的順序因爲參數或者是單個值，如數字或單個變量，或者它們包含在另一個TermNode中，如Operator。 A Function不應該忽略參數的順序。爲了檢查兩個列表的相等性，我使用了here中的這段代碼。

public static boolean isEqual(List<TermNode> one, List<TermNode> two) { 
    if(one == null && two == null) { 
     return true; 
    } 

    if((one != null && two == null) || (one == null && two != null)) { 
     return false; 
    } 

    if(one.size() != two.size()) { 
     return false; 
    } 

    one = getSortedList(one); 
    two = getSortedList(two); 

    return one.equals(two); 
} 

這也與

Map<TermNode, Integer> occurrences = 
    children.stream().collect(Collectors 
     .groupingBy(term -> term, Collectors.summingInt(term -> 1)) 
    ); 

解決了這個問題，因爲Map<TermNode, Integer>檢查經由equals(Object obj)在term -> term相等的按鍵，一個對象的hashCode()方法。

Answer 2

這將是在這裏評論的時間太長了，所以張貼作爲一個答案......

所以一般的想法是，你需要能夠告訴如果兩個TermNode的S對象是相同或不相同;爲此，您可以添加一個方法到您的對象，將變平您的對象，並以某種方式遞歸計算String並按字母順序排序。由於您的對象僅由兩個字段：value和TermTypeEnum那會不會是太難做到，這樣的事情可能是（顯然不是編譯）：

private List<String> flattened; 

private List<String> flatten(TermNode node){ 
    if(node.getChildren() > 0){ 
     // some recursion here 
    } else { 
     // probably some checks here 
     flattened.add(node.value + node.type) 
    } 
} 

// this will give you a sorted String from all the values 
public String toCompareBy(){ 
    return flatnned.sorted()... 
} 

所以這段代碼你的：

Map<TermNode, Integer> occurrences = children.stream() 
     .collect(Collectors.groupingBy(
      term -> term, 
      Collectors.summingInt(term -> 1))); 

能否改變這樣的事情：

children.stream() 
     .collect(Collector.toMap(
       Function.identity(), 
       Collectors.summingInt(x -> 1), 
       (left, right) -> { 
        return left + right;// or left + 1 
       } 
       () -> new TreeMap<>(Comparator.comparing(TermNode::toCompareBy)) 
     ))