文档章节

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

一贱书生
 一贱书生
发布于 2016/11/23 09:04
字数 718
阅读 18
收藏 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
计算器 abacus 技术文档之二----初步设计

======================================= 计算器 abacus 的下载地址:http://www.oschina.net/code/snippet73693213725 如果你有关于 abacus 的问题或者建议,请发邮件至 zhoucosin@163.co......

zhcosin
2012/10/30
0
0

没有更多内容

加载失败,请刷新页面

加载更多

HashTable

Hashtable 是一个散列表,它存储的内容是键值对(key-value)映射 Hashtable 继承于Dictionary,实现了Map、Cloneable、java.io.Serializable接口 Hashtable 的函数都是同步的,这意味着它是线...

职业搬砖20年
4分钟前
0
0
Linux系统状态查看命令1

10月23日任务 10.1 使用w查看系统负载 10.2 vmstat命令 10.3 top命令 10.4 sar命令 10.5 nload命令 查看系统负载 w命令 # 第一行:当前系统时间,系统启动时间,登录的用户,系统负载:1分钟...

robertt15
20分钟前
0
0
缓存那些事

前言 一般而言,现在互联网应用(网站或App)的整体流程,可以概括如图1所示,用户请求从界面(浏览器或App界面)到网络转发、应用服务再到存储(数据库或文件系统),然后返回到界面呈现内容...

Skqing
29分钟前
0
0
nginx开启stub_status模块配置方法

nginx开启stub_status模块配置方法 2017年12月13日 15:57:29 ly_dengle 阅读数:3765 标签: stub_statusnginxnginx开启stub_status模块 更多 个人分类: 软件工具php 版权声明:本文为博主原...

linjin200
35分钟前
3
0
挑逗 Java 程序员的那些 Scala 绝技

有个问题一直困扰着 Scala 社区,为什么一些 Java 开发者将 Scala 捧到了天上,认为它是来自上帝之吻的完美语言;而另外一些 Java 开发者却对它望而却步,认为它过于复杂而难以理解。同样是 ...

joymufeng
38分钟前
94
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部