给定一个布尔表达式,由0、1、&、|和^等符号组成,以及一个想要的布尔结果result,实现一个函数,算出有几种括号的放法可使该表达式
给定一个布尔表达式,由0、1、&、|和^等符号组成,以及一个想要的布尔结果result,实现一个函数,算出有几种括号的放法可使该表达式
一贱书生 发表于1年前
给定一个布尔表达式,由0、1、&、|和^等符号组成,以及一个想要的布尔结果result,实现一个函数,算出有几种括号的放法可使该表达式
  • 发表于 1年前
  • 阅读 10
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 技术升级10大核心产品年终让利>>>   

/**
 * 攻略:给定一个布尔表达式,由0、1、&、|和^等符号组成,以及一个想要的布尔结果result,实现一个函数,算出有几种括号的放法可使该表达式
 * 得出result值。

 */

两种方法:

方法一:

 

  1. /** 
  2.  * 思路:迭代整个表达式,将每个运算符当作第一个要加括号的运算符。 
  3.  * @param exp 
  4.  * @param result 
  5.  * @param s:start 
  6.  * @param e:end 
  7.  * @return 
  8.  */  
  9. public static int f(String exp,boolean result,int s,int e){  
  10.     if(s==e){  
  11.         if(exp.charAt(s)=='1'&&result)  
  12.             return 1;  
  13.         if(exp.charAt(s)=='0'&&!result)  
  14.             return 1;  
  15.         return 0;  
  16.     }  
  17.       
  18.     int c=0;  
  19.     if(result){  
  20.         for(int i=s+1;i<=e;i+=2){  
  21.             if(exp.charAt(i)=='&'){  
  22.                 c+=f(exp,true,s,i-1)*f(exp,true,i+1,e);  
  23.             }else if(exp.charAt(i)=='|'){  
  24.                 c+=f(exp,true,s,i-1)*f(exp,true,i+1,e);  
  25.                 c+=f(exp,false,s,i-1)*f(exp,true,i+1,e);  
  26.                 c+=f(exp,true,s,i-1)*f(exp,false,i+1,e);  
  27.             }else if(exp.charAt(i)=='^'){  
  28.                 c+=f(exp,true,s,i-1)*f(exp,false,i+1,e);  
  29.                 c+=f(exp,false,s,i-1)*f(exp,true,i+1,e);  
  30.             }  
  31.         }  
  32.     }else{  
  33.         for(int i=s+1;i<=e;i+=2){  
  34.             if(exp.charAt(i)=='&'){  
  35.                 c+=f(exp,true,s,i-1)*f(exp,false,i+1,e);  
  36.                 c+=f(exp,false,s,i-1)*f(exp,true,i+1,e);  
  37.                 c+=f(exp,false,s,i-1)*f(exp,false,i+1,e);  
  38.             }else if(exp.charAt(i)=='|'){  
  39.                 c+=f(exp,false,s,i-1)*f(exp,false,i+1,e);  
  40.             }else if(exp.charAt(i)=='^'){  
  41.                 c+=f(exp,true,s,i-1)*f(exp,true,i+1,e);  
  42.                 c+=f(exp,false,s,i-1)*f(exp,false,i+1,e);  
  43.             }  
  44.         }         
  45.     }  
  46.   
  47.     return c;     
  48. }     


 

 

方法二:

 

[java] view plain copy

 

  1. //动态规划  
  2. /** 
  3.  * 思路:缓存不同表达式的结果,避免多次用到同一个exp的值时需要重算。对expression和result进行缓存。 
  4.  * @param exp 
  5.  * @param result 
  6.  * @param s 
  7.  * @param e 
  8.  * @param map 
  9.  * @return 
  10.  */  
  11. public static int ff(String exp,boolean result,int s,int e,HashMap<String,Integer> map){  
  12.     String key=""+result+s+e;//注意加""的位置,应加在前面,表示为字符串的拼接。否则,则表示值先相加,再转字符串  
  13.     if(map.containsKey(key))  
  14.         return map.get(key);  
  15.       
  16.     int c=0;  
  17.     if(result){  
  18.         for(int i=s+1;i<=e;i+=2){  
  19.             if(exp.charAt(i)=='&'){  
  20.                 c+=f(exp,true,s,i-1)*f(exp,true,i+1,e);  
  21.             }else if(exp.charAt(i)=='|'){  
  22.                 c+=f(exp,true,s,i-1)*f(exp,true,i+1,e);  
  23.                 c+=f(exp,false,s,i-1)*f(exp,true,i+1,e);  
  24.                 c+=f(exp,true,s,i-1)*f(exp,false,i+1,e);  
  25.             }else if(exp.charAt(i)=='^'){  
  26.                 c+=f(exp,true,s,i-1)*f(exp,false,i+1,e);  
  27.                 c+=f(exp,false,s,i-1)*f(exp,true,i+1,e);  
  28.             }  
  29.         }  
  30.     }else{  
  31.         for(int i=s+1;i<=e;i+=2){  
  32.             if(exp.charAt(i)=='&'){  
  33.                 c+=f(exp,true,s,i-1)*f(exp,false,i+1,e);  
  34.                 c+=f(exp,false,s,i-1)*f(exp,true,i+1,e);  
  35.                 c+=f(exp,false,s,i-1)*f(exp,false,i+1,e);  
  36.             }else if(exp.charAt(i)=='|'){  
  37.                 c+=f(exp,false,s,i-1)*f(exp,false,i+1,e);  
  38.             }else if(exp.charAt(i)=='^'){  
  39.                 c+=f(exp,true,s,i-1)*f(exp,true,i+1,e);  
  40.                 c+=f(exp,false,s,i-1)*f(exp,false,i+1,e);  
  41.             }  
  42.         }         
  43.     }  
  44.     map.put(key, c);  
  45.     return c;     
  46.       
  47. }
共有 人打赏支持
粉丝 15
博文 722
码字总数 600072
×
一贱书生
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: