文档章节

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

一贱书生
 一贱书生
发布于 2016/11/23 09:04
字数 718
阅读 21
收藏 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. }

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 724
码字总数 600123
作品 0
私信 提问
sass笔记-4|像写脚本一样写Sass,把能交给Sass办的都交给它

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

Stinson_Zhao
2016/12/06
147
0
C#循环控制语句

本节课将介绍如何使用C#控制语句中的循环语句,本课目的如下: 1.学会"while"循环的用法。 2.学会"do" 循环的用法。 3.学会"for" 循环的用法。 4.学会foreach循环的用法。 5.进一步了解"brea...

晨曦之光
2012/03/09
360
0
javascript:基本数据结构

JavaScript提供脚本语言的编程与C++非常相似,它只是去掉了C语言中有关指针等容易产生的错误,并提供了功能强大的类库.对于已经具备C++或C语言的人来说,学习JavaScript脚本语言是一件非常轻松愉...

街边
2014/01/09
0
0
js正则学习笔记

工作中不可避免的会用到正则表达式,现就正则做以下总结。 正则简介 正则表达式是一种表达文本模式(即字符串结构)的方法,常常用作按照“给定模式”匹配文本的工具。 有两种创建方式,一种...

tiancai啊呆
2017/12/20
0
0
Python全栈工程师(运算符、if)

ParisGabriel Python 入门基础 比较运算符: < 小于 <= 小于等于 > 大于 >= 大于等于 == 等于 != 不等于 语法: 表达式1>表达式2 返回布尔类型 数值对象的构造函数: float(obj) 用字符串或...

巴黎香榭
07/04
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring源码学习笔记-1-Resource

打算补下基础,学习下Spring源码,参考书籍是《Spring源码深度解析》,使用版本是Spring 3.2.x,本来想试图用脑图记录的,发现代码部分不好贴,还是作罢,这里只大略记录下想法,不写太细了 ...

zypy333
今天
10
0
RestClientUtil和ConfigRestClientUtil区别说明

RestClientUtil directly executes the DSL defined in the code. ConfigRestClientUtil gets the DSL defined in the configuration file by the DSL name and executes it. RestClientUtil......

bboss
今天
16
0

中国龙-扬科
昨天
2
0
Linux系统设置全局的默认网络代理

更改全局配置文件/etc/profile all_proxy="all_proxy=socks://rahowviahva.ml:80/"ftp_proxy="ftp_proxy=http://rahowviahva.ml:80/"http_proxy="http_proxy=http://rahowviahva.ml:80/"......

临江仙卜算子
昨天
10
0
java框架学习日志-6(bean作用域和自动装配)

本章补充bean的作用域和自动装配 bean作用域 之前提到可以用scope来设置单例模式 <bean id="type" class="cn.dota2.tpye.Type" scope="singleton"></bean> 除此之外还有几种用法 singleton:......

白话
昨天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部