运算符交换以补充表达式树求值的最小数目

Question

我有一个表达式树，其中每个叶节点都包含0或1作为值，所有内部节点都包含"&"或"||"作为运算符。现在我需要评估这棵树；结果将是0或1。

问题是补充原始表达式树的结果所需的内部节点的最小交换次数。任何内部节点都可以翻转；例如，如果它是一个"&"，我们可以使它成为"||"，反之亦然。

为了解决这个问题，我尝试了以下技巧，但没有成功：我的方法是，我会检查根是否是"&"或"||"运算符，以及评估树的结果是0还是1，这取决于我是否继续进行评估。

Answer 1

我不确定我是否理解你的问题。如果是如何评估整棵树，我的答案是：

尝试递归
像这样的东西：

evalute() {
    if_the_root_is_an_operator() {
       l= evaluate(left operant) 
       r= evaluate(right operant)
       return calculate(l,r)  // depending on what operator it was
    } 
    // not an operator, so it'S a leaf
    return value;
}

优化可以是，检查l或r是否为值，如果它们的值已经定义了最终结果，则跳过评估
"0 AND（子树）"肯定是0，
"1 OR（子树）"是1，所以子树不需要评估

evalute() {
    if (the_root_is_an_operator()) {
       if (  operator_is_and() &&
            (left_is_leaf() && value(left)==0) || 
            (right_is_leaf() && value(right)==0)) 
          return 0;
       if (  operator_is_or() &&
            (left_is_leaf() && value(left)==1) || 
            (right_is_leaf() && value(right)==1)) 
          return 1;
       l= evaluate(left operant) 
       r= evaluate(right operant)
       return calculate(l,r)  // depending on what operator it was
    } 
    // not an operator, so it'S a leaf
    return value;
}

Answer 2

这是所问问题的一个例子。

 OR 

/\或与
/\/\
1 0 1 1

输出为1。需要找到要更改的最小操作数才能将输出更改为0。需要更改的操作员的最小数量为2。

class A {   
int min=Integer.max;  

int minNumber(Tree node)  {  
if(node==null) return Math.max;  
if(node.left==null && node.right==null) return Math.max; 
 String c = node.data;   
 int l = evaluate(node.left); 
 int r = evaluate(node.right);  
if(l || r==0) {     min_number = 1; }  
else {      
    if(l && r == 1 )     
    {         
    min_number = 0;     
    }     
    else if(l && r == 0)     
    {         
     min_number = 0;     
    }           
int left = min_number + minNumber(node.left)     
int right = min_number + minNumber(node.right);      
min_number = Math.min(left,right); 
}  
if(min_number<min) min = min_number;  return min;  
}