题目

给定一个只由0(假)、1(真)、&(逻辑与)、|(逻辑或)和^(异或)五种组成的字符串express，再给定一个布尔值desired。返回express能有多少种组合方式。可以达到desired的结果。

举例

express“1^0|0|1”,desired=false.

只有1^((0|0)|1)和1^(0|(0|1))的组合可以得到false，返回2.

express=“1”，desired=false

无组合则可以得到false，返回0。

表达式得长度必须是奇数

表达式下标为偶数位置的字符一定是'0'或'1'。

表达式下标为奇数位置的字符一定是'&'或‘|’或‘^’

public boolean isValid(char[] exp){
    if((exp.length & 1) == 0){
        return false;
    }
    for(int i = 0;i<exp.length;i = i + 2){
        int((exp[i] != '1') && (exp[i] != '0')){
            return false;
        }
    }
    for(int i = 1;i<exp.length;i = i + 2){
        int((exp[i] != '&') && (exp[i] != '|') && (exp[i] != '^') ){
            return false;
        }
    }
    return true;
}


public int num1(String express,boolean desired){
    if(express == null || express.equals("")){
        return 0;
    }
    char[] exp = express.toCharArray();
    if(!isValid(exp)){
        return 0;
    }
    return p(exp,desitred,0,exp.length -1);
}

public int p(char[] exp,boolean desired,int l,int r){
    if( l == r){
        if(exp[l] == '1'){
            return desired ? 1 : 0;
        }else{
            return desired ? 0 : 1;
        }
    }
    int res = 0;
    if(desired){
        for(int i = l + 1;i < r; i += 2){
            switch(exp[i]){
                case '&':
                    res += p(exp,true,l,i-1) *  p(exp,true,i+1,r);
                    break;
                case '|':
                    res += p(exp,true,l,i-1) *  p(exp,false,i+1,r);
                    res += p(exp,false,l,i-1) *  p(exp,true,i+1,r);
                    res += p(exp,true,l,i-1) *  p(exp,true,i+1,r);
                    break;
                case '^':
                    res += p(exp,true,l,i-1) *  p(exp,false,i+1,r); 
                    res += p(exp,false,l,i-1) *  p(exp,true,i+1,r);
                    break;
            }
        }
    }else{
        for(int i = l + 1;i < r; i += 2){
            switch(exp[i]){
                case '&':
                    res += p(exp,false,l,i-1) *  p(exp,true,i+1,r);
                    res += p(exp,true,l,i-1) *  p(exp,false,i+1,r);
                    res += p(exp,false,l,i-1) *  p(exp,false,i+1,r);
                    break;
                case '|':
                    res += p(exp,false,l,i-1) *  p(exp,false,i+1,r);
                    break;
                case '^':
                    res += p(exp,true,l,i-1) *  p(exp,true,i+1,r); 
                    res += p(exp,false,l,i-1) *  p(exp,false,i+1,r);
                    break;
            }
        }    
    }
    return res;
}