国庆节快乐!接分了!好象和学校里的学的集合操作差不多!不知道算法
从最里面的括号展开
1、A | ( B  | C)  则直接括号=A|B|C
2、 A& ( B  ¦ C)    如果括号前的符号为& ,则=A&B|A&C
3、A|(B&C)   =A|b&c,直接地括号
4、A&(B&C)=A&B&C   直接却括号
5、A&B|C     如果有,则相当于(a&B)|C,即&两边加上括号这说明,如果符号相同,直接去括号;如查符号相异,只有A& ( B  ¦ C)时,要分等于 A&B|A&C

解决方案 »

  1.   

    先鄙视一下php版的ID们, 都这么懒, 
    看C版贴个算法题,讨论得热火朝天的再把自己的贴出来, 写得有点乱, 谁有好建议可以简化的奖励写的这个受到楼上fxs_2008的一点启发,先谢谢大致是先给 x&y&z 这样的加上括号 => (x&y)&z , 或 x&y|z => (x&y)|z 
    然后递归调用, 直到最简单的几种情况 (x&y)&z, (x|y)&(a|b), ... 直接去括号function simple($logic){ // convert logic to simple //echo $logic."\n"; $left_count = substr_count($logic,'(');
    $right_count= substr_count($logic,')');
    if($left_count!=$right_count){
     return false;
    }
    if($left_count==0){
    return $logic;
    } $exist_nest=preg_match('/\([^\)]*?\(/',$logic);
    if($left_count==1){ $temp=preg_replace('/\(.*?\)/','',$logic); if(empty($temp)){
    $str=trim(trim($logic,')'),'(');
     return $str;
    } $and_count=substr_count($temp,'&');
    $or_count=substr_count($temp,'|'); if( $and_count==0 || $and_count==1 && $or_count==0 ){ // x&(...) or (...)&x or  y|x|(..)|z // only 1 pair ( and ) , remove them
    if(strpos($logic,'&(')!==false){
    list($left,$right)=explode('&(',$logic);
    $right=trim($right,')');
    $right_elements=explode('|',$right);
    $str='';
    foreach($right_elements as $r){
    $str.=$left.'&'.$r.'|';
    }
    $str=rtrim($str,'|');
    return $str; }elseif(strpos($logic,')&')!==false ){
    list($left,$right)=explode(')&',$logic);
    $left=trim($left,'(');
    $left_elements=explode('|',$left);
    $str='';
    foreach($left_elements as $r){
    $str.=$r.'&'.$right.'|';
    }
    $str=rtrim($str,'|');
    return $str; }else{
    $str=str_replace(array('(',')'),'',$logic);
    return $str;
    }
    }
    }
    if($left_count>=2){ // ()&()  or ()|()|x|y|()....
    if(!$exist_nest){ $temp=preg_replace('/\(.*?\)/','',$logic);
    $and_count=substr_count($temp,'&');
    $or_count=substr_count($temp,'|'); //if( $and_count==0 || $and_count==1 && $or_count==0 ){ if($temp=='&' || $and_count==0 ){
    if($and_count==0){ // ()|()|()|x|()|y...
    $str=str_replace(array('(',')'),'',$logic);
    return $str;
    } if($temp=='&'){
    list($left,$right)=explode(')&(',$logic);
    $left=trim($left,'(');
    $right=trim($right,')');
    $left_elements=explode('|',$left);
    $right_elements=explode('|',$right);
    $str='';
    foreach($left_elements as $l){
    foreach($right_elements as $r){
    $str.=$l.'&'.$r.'|';
    }
    }
    $str=trim($str,'|');
    return $str;
    } }
    }
    } $strs=preg_split('/(\)|\(|&|\|)/',$logic,-1,PREG_SPLIT_DELIM_CAPTURE|PREG_SPLIT_NO_EMPTY); $result=array();
    $stack=array();
    $level=0;
    $=0;
    //find a matched ( and )
    $strs=array_reverse($strs); while($str=array_pop($strs)){
    //echo 'RESULT:'.implode('',$result)."\t\t".implode('',$stack)."\n"; if($str=='('){
    $level++;
    if($level>1 || $==1) array_push($stack,$str);
    continue;
    } if($str==')'){
    $level--;
    if($level>0 || $==1) array_push($stack,$str); if($==1 && $level==0){
    $=0;
    //$level--;
    } if($level==0){ // end of ()
    $temp=implode('',$stack);
    $stack=array();
    $mid=simple($temp);
    array_push($result,'('.$mid.')'); } continue;
    } if($level==0){ if($str=='&' && !$exist_nest ){
    $left=array_pop($result);  //echo '['.$left.']';
    array_push($stack,$left);
    array_push($stack,'&');
    //$level++;
    $=1;
    continue;
    } if($str!='|' && $str!='&'){ // is a number
    if($==1){
    $=0;
    array_push($stack,$str); array_push($result,'('.implode('',$stack).')');
    $stack=array(); continue; //array_push($stack,')');
    //$level--;
    }
    array_push($result,$str);
    }else{
    array_push($result,$str);
    }
    }else{
    array_push($stack,$str);
    } } if($level!=0) {
    return false;
    } return simple(implode('',$result));}
      

  2.   

    补充以下, 我的a,b,c等都是数字, 测试可以用这样的例子:
    simple('1|(2&(3&(4|5&6|7|8&9|11)&12&(13|14)|15))|(16&(17|18&19))&20');
    => 1|2&3&4&12&13|2&3&4&12&14|2&3&5&6&12&13|2&3&5&6&12&14|2&3&7&12&13|2&3&7&12&14|2&3&8&9&12&13|2&3&8&9&12&14|2&3&11&12&13|2&3&11&12&14|2&15|16&17&20|16&18&19&20
      

  3.   

    ........看得头昏了。精神上支持回复的phper!