首页 > 试题广场 >

表达式得到期望结果的组成种数

[编程题]表达式得到期望结果的组成种数
  • 热度指数：342 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
给定一个只由0(假)，1（真），&（逻辑与），|（逻辑或），^（异或）五种字符组成的字符串，记为exp；还有一个布尔型的值，记为desired。
写一个函数，返回exp能有多少种小括号的组合方式，可以达到desired的结果。
例如： expression：1^0|0|1 desired：false
只有两种组合可以得到false： 1^((0|0)|1)和1^(0|(0|1)) 所以应该返回2。
算法知识视频讲解
添加回答
Ghost头像 Ghost
典型的动态规划题，先丢代码，有心情再写答案。 
public class Solution {

 public int[][][] f = new int[100][100][2];
    
 public int getDesiredNum(String exp, boolean desired) {
 char[] expArr = exp.toCharArray(); 
 
 for(int i = 0;i < expArr.length; ++i)
 for(int j = 0;j < expArr.length; ++j)
 f[i][j][0] = f[i][j][1] = 0;
 
 
 for (int i = 0; i < expArr.length; i += 2)
 if (expArr[i] == '1')
 f[i][i][1] = 1;
 else
 f[i][i][0] = 1;

 for (int i = 3; i <= expArr.length; i += 2)
 for (int j = 0; j <= expArr.length - i; j += 2)
 for (int k = j + 1; k < j + i; k += 2) {
 int l = j + i - 1;
 if(expArr[k] == '&'){
 f[j][l][1] += (f[j][k - 1][1] * f[k + 1][l][1]);
 f[j][l][0] += (f[j][k - 1][0] * f[k + 1][l][0] + f[j][k - 1][1] * f[k + 1][l][0] + f[j][k - 1][0] * f[k + 1][l][1]);
 }
 else if(expArr[k] == '|'){
 f[j][l][0] += (f[j][k - 1][0] * f[k + 1][l][0]);
 f[j][l][1] += (f[j][k - 1][1] * f[k + 1][l][1] + f[j][k - 1][1] * f[k + 1][l][0] + f[j][k - 1][0] * f[k + 1][l][1]);
 }
 else{
 f[j][l][1] += (f[j][k - 1][1] * f[k + 1][l][0] + f[j][k - 1][0]	* f[k + 1][l][1]);
 f[j][l][0] += (f[j][k - 1][0] * f[k + 1][l][0] + f[j][k - 1][1]	* f[k + 1][l][1]);
 }
 }
        
 if (desired)
 return f[0][expArr.length - 1][1];
 else
 return f[0][expArr.length - 1][0];
 }

}

发表于 2015-03-09 08:57:09 回复(0)
..Johnson头像 ..Johnson 
class Solution {
public:     int getDesiredNum(string exp, bool desired) {
        const int maxn = 107;
        int dp[maxn][maxn][2];
        int i, j, k, x, l, r, n = exp.length();
        const char *str = exp.c_str();
        char mark;
        memset(dp, 0, sizeof(dp));
        for(i = 0; i < n; i += 2) dp[i][i][str[i] - '0'] = 1;
        for(k = 3; k <= n; k += 2) {
            for(i = 0; i < n - k + 1; i += 2) {
                l = i, r = i + k - 1;
                for(j = l; j < r; j += 2) {
                    mark = str[j + 1];
                    if(mark == '&') {
                        dp[l][r][0] += dp[l][j][0] * dp[j + 2][r][0] + dp[l][j][1] * dp[j + 2][r][0] + dp[l][j][0] * dp[j + 2][r][1];
                        dp[l][r][1] += dp[l][j][1] * dp[j + 2][r][1];
                    } else if(mark == '|') {
                        dp[l][r][0] += dp[l][j][0] * dp[j + 2][r][0];
                        dp[l][r][1] += dp[l][j][1] * dp[j + 2][r][1] + dp[l][j][1] * dp[j + 2][r][0] + dp[l][j][0] * dp[j + 2][r][1];
                    } else if(mark == '^') {
                        dp[l][r][0] += dp[l][j][0] * dp[j + 2][r][0] + dp[l][j][1] * dp[j + 2][r][1];
                        dp[l][r][1] += dp[l][j][1] * dp[j + 2][r][0] + dp[l][j][0] * dp[j + 2][r][1];
                    }
                }
            }
        }
        return dp[0][n - 1][desired];
    }
};
// dp

发表于 2017-10-18 09:09:35 回复(0)
元气の悟空头像 元气の悟空 
class Solution {
    string exp;
    int dp[100][100][2];
public:
    int getDesiredNum(string exp, bool desired) {
        memset(dp,-1,sizeof(dp));
        if(exp.length()==0) return 0;
        this->exp=exp;
        return d(0,exp.length()-1,desired);
    }
    int d(int i,int j,bool val){
        if(dp[i][j][val]!=-1) return dp[i][j][val];
        if(i==j) return (exp[i]-'0')==val?1:0;
        int res=0;
        for(int k=i+1;k<j;k++)
            if(exp[k]=='&'){
                if(val) res+=d(i,k-1,1)*d(k+1,j,1);
                else res+=d(i,k-1,1)*d(k+1,j,0)+d(i,k-1,0)*d(k+1,j,1)+d(i,k-1,0)*d(k+1,j,0);
            }else if(exp[k]=='|'){
                if(val) res+=d(i,k-1,1)*d(k+1,j,0)+d(i,k-1,0)*d(k+1,j,1)+d(i,k-1,1)*d(k+1,j,1);
                else res+=d(i,k-1,0)*d(k+1,j,0);
            }else if(exp[k]=='^'){
                if(val) res+=d(i,k-1,1)*d(k+1,j,0)+d(i,k-1,0)*d(k+1,j,1);
                else res+=d(i,k-1,1)*d(k+1,j,1)+d(i,k-1,0)*d(k+1,j,0);
            }
        dp[i][j][val]=res;
        return res;
    }
};//记忆搜索

发表于 2017-10-18 09:09:09 回复(0)
C/C++
老子是帮主头像 老子是帮主 
既然楼上分享了动态规划解法，我分享一下我的递归解法，递归虽然费时，优点是易于实现
和理解。对于使用逻辑运算符（"&","|","^"）相连的表达式而言，要想得到期望的结果，
只需要计算逻辑运算符两侧的表达式组成所期望结果的方案数的乘积即可。具体来说：
如果期望A & B为true,
那么可行解数目 = 表达式A为true的方案数×表达式B为true的方案数；
如果期望A | B为true,
那么可行解数目 = 表达式A为true的方案数×表达式B为false的方案数 +  表达式A为false的方案数×表达式B为true的方案数 + 
                 表达式A为true的方案数×表达式B为true的方案数；
如果期望A ^ B为true，
那么可行解数目 = 表达式A为true的方案数×表达式B为false的方案数 + 
                 表达式A为false的方案数×表达式B为true的方案数；

同理，如果期望结果是false的话。。。。。。
上述递归思路实现如下：
class Solution {
public:
    int p(string exp, bool desired, int l, int r){
        if(l == r){
            if(exp[l] == '1')
                return desired ? 1 : 0;
            else
                return desired ? 0 : 1;
        }
        int res = 0;
        if(desired){
            for(int i = l + 1;i < r;i += 2){
                if(exp[i] == '&'){
                    res += p(exp, true, l, i-1) * p(exp, true, i+1, r);
                }
                else if(exp[i] == '|'){
                    res += p(exp, true, l, i-1) * p(exp, false, i+1, r);
                    res += p(exp, false, l, i-1) * p(exp, true, i+1, r);
                    res += p(exp, true, l, i-1) * p(exp, true, i+1, r);
                }
                else if(exp[i] == '^'){
                    res += p(exp, true, l, i-1) * p(exp, false, i+1, r);
                    res += p(exp, false, l, i-1) * p(exp, true, i+1, r);
                }
            }
        }
        else{
            for(int i = l + 1;i < r;i += 2){
                if(exp[i] == '&'){
                    res += p(exp, true, l, i-1) * p(exp, false, i+1, r);
                    res += p(exp, false, l, i-1) * p(exp, true, i+1, r);
                    res += p(exp, false, l, i-1) * p(exp, false, i+1, r);
                }
                else if(exp[i] == '|'){
                    res += p(exp, false, l, i-1) * p(exp, false, i+1, r);
                }
                else if(exp[i] == '^'){
                    res += p(exp, true, l, i-1) * p(exp, true, i+1, r);
                    res += p(exp, false, l, i-1) * p(exp, false, i+1, r);
                }
            }
        }
        return res;
    }
    
    int getDesiredNum(string exp, bool desired) {
        if(exp == "")
            return 0;
        int left = 0;
        int right = exp.size() - 1;
        return p(exp, desired, left, right);
    }
};

编辑于 2017-12-26 21:39:23 回复(0)
马客(Mark)头像 马客(Mark)
区间动态规划，dp(l,r,b)表示在[l,r]这段区间外加一层括号结果为b的组合方式，在求dp(l,r,b)时枚举一个中间运算点m，dp(l,r,b)=sigma{ dp(l,m,b1)*dp(m,r, b2)|b1和b2经m运算得b }，初始条件dp(i,i,a[i])=1
（PS:..这题居然没有提到对方案数取模。。想必数据量也不会有多大。。） 
#include <cstring>
#define rep(i, n) for(int i = 0; i < n; ++i)
#define FOR(i, begin, end, step) for(int i = (begin); i < (end); i += (step))
#define r (l + L)
class Solution {
public:
 /**
 *	表达式得到期望结果的组成种数
 *	输入：表达式exp；期待的结果desired
 *	返回：表达式得到期望结果有多少种组合
 */
    bool check(int a, int b, char c){
        switch(c){
            case '&': return a && b;
            case '|': return a || b;
            case '^': return a != b;        }
        return 0x233333;
    }
 int getDesiredNum(string exp, bool desired) {
        int n = exp.size();
 int (*dp)[233][2] = new int[233][233][2];
        rep(i, n) rep(j, n) rep(k, 2) dp[i][j][k] = 0;
        FOR(i, 0, n, 2) dp[i][i][exp[i] - '0'] = 1;
        FOR(L, 2, n, 2) FOR(l, 0, n, 2) rep(b, 2) FOR(m, l + 1, r, 2) rep(b1, 2) rep(b2, 2) if(check(b1, b2, exp[m]) == b) dp[l][r][b] += dp[l][m - 1][b1] * dp[m + 1][r][b2];
        int res = dp[0][n - 1][desired];
        delete dp;
        return res;
    }
};

发表于 2015-03-10 09:30:35 回复(0)
提交观点

问题信息

难度：
5条回答 7432浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号