2021-06-03: Boolean operation. Given a Boolean expression and an expected cloth

2021-06-03： Boolean operation . Given a Boolean expression and a desired boolean result result, Boolean expression by 0 (false)、1 (true)、& (AND)、 | (OR) and ^ (XOR) The symbols make up . Implement a function , Calculate several ways that the expression can get result The parenthesis method of the value .

Fuda answer 2021-06-03：

Method 1 ： recursive .

Method 2 ： Dynamic programming .

The code to use golang To write . The code is as follows ：

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
    }
}

//  Limit :
// L...R On , There must be an odd number of characters 
// L The character of the position and R The character of position , Not 0 namely 1, Cannot be a logical symbol ！
//  return str[L...R] This is a piece of , by true The number of ways , and false The number of ways 
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
        //  Every logical symbol ,split Enumerating things 
        //  Try the final combination 
        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]
}

The results are as follows ：

picture

---

Zuo Shen java Code