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

问题描述：

我有一个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：

计算反向polnish符号/后修复顺序的表达。

结果是x x x x + + +。

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

某处在simplifyOperator方法我想折叠具有相同的值的变量。对于上面的表达式中，树是这个样子：

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

的目标是通过在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？

您能否提供一个代数表达式以及您希望它产生的对象列表？根据您对node1的定义，“对（node1,4），Pair（node2,2）}”对应的代数表达式是什么，即四次“x”和两次“sin（x） node2'？ –

@AlexandreDupriez修改了我的OP并添加了一个完整的示例。 – CRoemheld

我正在投票关闭这个简单的事实，即您提供的代码无法编译 - 缺少大量的类。但是，如果你添加那些你的问题还是模糊的，你可以添加更多的“范围”，使其更好 – Eugene

答

谢谢您的回答，我最终不得不重写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()方法。

答

这将是在这里评论的时间太长了，所以张贴作为一个答案......

所以一般的想法是，你需要能够告诉如果两个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)) 
     ))

不幸的是，这些对象由*三个字段组成：'value'，'children'和'type' 'children'是应用于操作符或函数的参数列表。 – CRoemheld

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

相关推荐