題目

給定一個只由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;
}