文档章节

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

一贱书生
 一贱书生
发布于 2016/11/23 09:04
字数 718
阅读 17
收藏 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
338
0
javascript:基本数据结构

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

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

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

tiancai啊呆
2017/12/20
0
0
Kotlin:基本类型都是对象,原生类型将成为回忆

在Kotlin中,所有东西都是对象,我们可以在任何变量(如基本类型:数字、字符、布尔、数组与字符串等)上调用成员函数和属性。 一、数字 1. 内置类型种类 Kotlin提供了如下内置类型来表示数据...

p106786860
2017/08/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

c语言之内存分配笔记

先看一个数组: short array[5] = {1,2} // 这儿定义的一个int类型的数组,数组第1和第2个元素值是1和2.其余后面默认会给值为0; 或者 short array[] = {1,2};//这儿数组第1和第2个元素,数组...

DannyCoder
今天
2
0
Shell | linux安装包不用选择Y/N的方法

apt-get install -y packageOR echo "y" | sudo apt-get install package

云迹
今天
2
0
Hadoop的大数据生态圈

基于Hadoop的大数据的产品圈 大数据产品的一句话概括 Apache Hadoop: 是Apache开源组织的一个分布式计算开源框架,提供了一个分布式文件系统子项目(HDFS)和支持MapReduce分布式计算的软件架...

zimingforever
今天
5
0
八大包装类型的equals方法

先看其中一个源码 结论:八大包装类型的equals方法都是先判断类型是否相同,不相同则是false,相同则判断值是否相等 注意:包装类型不能直接用==来等值比较,否则编译报错,但是数值的基本类型...

xuklc
今天
2
0
NoSQL , Memcached介绍

什么是NoSQL 非关系型数据库就是NoSQL,关系型数据库代表MySQL 对于关系型数据库来说,是需要把数据存储到库、表、行、字段里,查询的时候根据条件一行一行地去匹配,当量非常大的时候就很耗...

TaoXu
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部