列表分组由对象字段和计数的发生

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