文档章节

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

一贱书生
 一贱书生
发布于 2016/11/23 09:04
字数 718
阅读 99
收藏 0

/**
 * 攻略:给定一个布尔表达式,由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. }

© 著作权归作者所有

一贱书生
粉丝 21
博文 723
码字总数 600123
作品 0
私信 提问
加载中

评论(0)

程序员面试金典 - 面试题 08.14. 布尔运算(区间动态规划)

1. 题目 给定一个布尔表达式和一个期望的布尔结果 result,布尔表达式由 符号组成。 实现一个函数,算出有几种可使该表达式得出 result 值的括号方法。 来源:力扣(LeetCode) 链接:https...

Michael阿明
04/16
0
0
sass笔记-4|像写脚本一样写Sass,把能交给Sass办的都交给它

Sass笔记关于sass的基础部分已经写完,这一篇介绍Sass的高级特性——脚本特性。Sass能做很多事让样式表更智能,我们先会看到Sass眼中的数据类型,在这些数据类型上会有可进行的操作,此外,S...

Stinson_Zhao
2016/12/06
167
0
NOIP 2011 普及组 T4 表达式的值 栈

题目 题目描述 对于1 位二进制变量定义两种运算: 运算的优先级是: 先计算括号内的,再计算括号外的。 “× ”运算优先于“⊕”运算,即计算表达式时,先计算× 运算,再计算⊕运算。例如:...

osc_bu97b05m
2018/06/25
3
0
02-python基本数据类型

02-python基本数据类型 1.python的几个概念 1.1 表达式 1.2 python中的语句 1.3 程序(program) 1.4 函数 2.python的标识符 2.1 关键字 2.2 标识符概念 3.python数据基本类型 3.1 整数和小数...

正在等待对方输入
04/09
0
0
java 基础学习 关键字、标识符、常量、进制、有符号表示法、变量、数据类型小节

1.关键字 概述:被java赋予特殊含义的单词 组成规则:全部是由英文小写字母组成 注意事项: goto和const作为保留字存在,可能在以后的JDK版本升级过程中升级为关键字 类似于notepad++这样的高...

osc_45omoec3
2018/01/25
2
0

没有更多内容

加载失败,请刷新页面

加载更多

zookeeper实现分布式锁总结,看这一篇足矣(设计模式应用实战)

zk实现分布式锁纵观网络各种各样的帖子层出不穷,笔者查阅很多资料发现一个问题,有些文章只写原理并没有具体实现,有些文章虽然写了实现但是并不全面 借这个周末给大家做一个总结,代码拿来...

osc_75pcgicm
53分钟前
20
0
163邮箱配置imap和smtp,隐藏的设置

http://config.mail.163.com/settings/imap/index.jsp?uid=XXXXX@163.com,这是一个隐藏的设置,要到这里配置才能用163的imap或者pop...

bengozhong
54分钟前
22
0
Python可变对象和不可变对象

Python中一切皆对象,每个对象都有其唯一的id,对应的类型和值,其中id指的是对象在内存中的位置。根据对象的值是否可修改分为可变对象和不可变对象。其中, 不可对象包括:数字,字符串,t...

osc_pnyuctmm
55分钟前
20
0
数据库垂直拆分 水平拆分

1 数据库拆分 当我们使用读写分离、缓存后,数据库的压力还是很大的时候,这就需要使用到数据库拆分了。 数据库拆分简单来说,就是指通过某种特定的条件,按照某个维度,将我们存放在同一个数...

努力的学渣
56分钟前
28
0
微信小程序连接低功率蓝牙控制单片机上硬件设备

1.软件部分介绍   微信小程序是一种新的应用,用户不需要下载应用只用通过扫二维码或者打开链接就能使用,使用完后不需要卸载,直接关闭就行了。微信在2017年初推出微信小程序开发环境。任...

osc_uxgfefy0
57分钟前
14
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部