布尔运算。给定一个布尔表达式和一个期望的布尔结果 result，布尔表达式由 0 (false)、1 (true)、& (AND)、 | (OR) 和 ^ (XOR) 符号组成。实现一个函数，算出有几种可使该表达式得出 result 值的括号方法。
方法一：递归。
方法二：动态规划。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
express := "1&1&1"
desired := 1
ret0 := countEval0(express, desired)
ret1 := countEval1(express, desired)
ret2 := countEval2(express, desired)
fmt.Println(ret0, ret1, ret2)
}
func countEval0(express string, desired int) int {
if express == "" {
return 0
}
N := len(express)
dp := make([][]*Info, N)
for i := 0; i < N; i++ {
dp[i] = make([]*Info, N)
}
allInfo := ff(express, 0, len(express)-1, dp)
return twoSelectOne(desired == 1, allInfo.t, allInfo.f)
}
type Info struct {
t int
f int
}
func twoSelectOne(c bool, a int, b int) int {
if c {
return a
} else {
return b
}
}
// 限制:
// L...R上，一定有奇数个字符
// L位置的字符和R位置的字符，非0即1，不能是逻辑符号！
// 返回str[L...R]这一段，为true的方法数，和false的方法数
func ff(str string, L int, R int, dp [][]*Info) *Info {
if dp[L][R] != nil {
return dp[L][R]
}
t := 0
f := 0
if L == R {
t = twoSelectOne(str[L] == '1', 1, 0)
f = twoSelectOne(str[L] == '0', 1, 0)
} else { // L..R >=3
// 每一个种逻辑符号，split枚举的东西
// 都去试试最后结合
for split := L + 1; split < R; split += 2 {
leftInfo := ff(str, L, split-1, dp)
rightInfo := ff(str, split+1, R, dp)
a := leftInfo.t
b := leftInfo.f
c := rightInfo.t
d := rightInfo.f
switch str[split] {
case '&':
t += a * c
f += b*c + b*d + a*d
break
case '|':
t += a*c + a*d + b*c
f += b * d
break
case '^':
t += a*d + b*c
f += a*c + b*d
break
}
}
}
dp[L][R] = &Info{t, f}
return dp[L][R]
}
func countEval1(express string, desired int) int {
if express == "" {
return 0
}
return f(express, desired, 0, len(express)-1)
}
func f(str string, desired int, L int, R int) int {
if L == R {
if str[L] == '1' {
return desired
} else {
return desired ^ 1
}
}
res := 0
if desired == 1 {
for i := L + 1; i < R; i += 2 {
switch str[i] {
case '&':
res += f(str, 1, L, i-1) * f(str, 1, i+1, R)
break
case '|':
res += f(str, 1, L, i-1) * f(str, 0, i+1, R)
res += f(str, 0, L, i-1) * f(str, 1, i+1, R)
res += f(str, 1, L, i-1) * f(str, 1, i+1, R)
break
case '^':
res += f(str, 1, L, i-1) * f(str, 0, i+1, R)
res += f(str, 0, L, i-1) * f(str, 1, i+1, R)
break
}
}
} else {
for i := L + 1; i < R; i += 2 {
switch str[i] {
case '&':
res += f(str, 0, L, i-1) * f(str, 1, i+1, R)
res += f(str, 1, L, i-1) * f(str, 0, i+1, R)
res += f(str, 0, L, i-1) * f(str, 0, i+1, R)
break
case '|':
res += f(str, 0, L, i-1) * f(str, 0, i+1, R)
break
case '^':
res += f(str, 1, L, i-1) * f(str, 1, i+1, R)
res += f(str, 0, L, i-1) * f(str, 0, i+1, R)
break
}
}
}
return res
}
func countEval2(express string, desired int) int {
if express == "" {
return 0
}
N := len(express)
dp := make([][][]int, 2)
for i := 0; i < 2; i++ {
dp[i] = make([][]int, N)
for j := 0; j < N; j++ {
dp[i][j] = make([]int, N)
}
}
dp[0][0][0] = twoSelectOne(express[0] == '0', 1, 0)
dp[1][0][0] = dp[0][0][0] ^ 1
for i := 2; i < len(express); i += 2 {
dp[0][i][i] = twoSelectOne(express[i] == '1', 0, 1)
dp[1][i][i] = twoSelectOne(express[i] == '0', 0, 1)
for j := i - 2; j >= 0; j -= 2 {
for k := j; k < i; k += 2 {
if express[k+1] == '&' {
dp[1][j][i] += dp[1][j][k] * dp[1][k+2][i]
dp[0][j][i] += (dp[0][j][k]+dp[1][j][k])*dp[0][k+2][i] + dp[0][j][k]*dp[1][k+2][i]
} else if express[k+1] == '|' {
dp[1][j][i] += (dp[0][j][k]+dp[1][j][k])*dp[1][k+2][i] + dp[1][j][k]*dp[0][k+2][i]
dp[0][j][i] += dp[0][j][k] * dp[0][k+2][i]
} else {
dp[1][j][i] += dp[0][j][k]*dp[1][k+2][i] + dp[1][j][k]*dp[0][k+2][i]
dp[0][j][i] += dp[0][j][k]*dp[0][k+2][i] + dp[1][j][k]*dp[1][k+2][i]
}
}
}
}
return dp[desired][0][N-1]
}执行结果如下：
