将字符串括起来以便表达式获得给定值

Question

以下问题来自Vazirani等人的动态规划章节。人。

---

[6.6]让我们定义一个乘法运算（x）在三个符号a上; b; Ç根据下表：

因此，×A = B，A×B = B等

找到一个有效的算法，该算法检查这些符号串，说bbbbac，并决定 是否可以将字符串括起来以使得结果表达式的值为a。例如，在输入bbbbac时，你的算法应该返回yes，因为 （（b（bb））（ba））c = a。

---

这里是我的方法：它映射到计数布尔parenthesizations的数量给出here的问题。在这个问题，你给出的形式

T的布尔表达式或˚F和牛逼XOR牛逼

，你需要找到的圆括号这个路数，使其评估为真。

我们能想到的或，和，XOR作为遵循一定的规则运营商（T XOR F =牛逼等）和行为上采取值T或F.对于我们原来的问题操作数，我们可以将a，b，c看作操作数，其乘法（x）为定义的乘法（x）作为提供规则。

上述方法是否有意义或者是否有更简单的方法？

Answer 1

是的，你的方法应该类似于你提到的问题。一般情况下，如果有ň符号（而不是3，你在这个问题或2提到的问题，你已经给链接），你应该做的是这样的 -

#include <stdio.h> 
#include <string.h> 

#define MAXL 500 
#define MAXN 100 

int  isPossible[MAXL][MAXL][MAXN]; 
int  matrix[MAXN][MAXN]; //multiplication table 
char str[MAXN+1]; 
int  L; 

int go(int start, int end, int need) { 
    if(start > end) return 0; 
    if(isPossible[start][end][need] != -1) return isPossible[start][end][need]; 

    int i,x,y; 
    for(i = start; i < end; i++) { 
     for(x = 0; x < MAXN; x++) {//you can optimize these x & y loops by pre-determining which combinations can give you 'need' 
      for(y = 0; y < MAXN; y++) if(matrix[x][y] == need) { 
       if(go(start, i, x)==1 && go(i+1, end, y)==1) { 
        isPossible[start][end][need] = 1; 
        return 1; 
       } 
      } 
     } 
    } 
    return 0; 
} 

int main() { 
    while(scanf(" %s",str)==1) { 
     L = strlen(str); 
     memset(isPossible, -1, sizeof(isPossible)); 
     go(0, L-1, 'a'); 
    } 
    return 0; 
} 

请注意，这不是经过测试和完整的源代码。

Answer 2

我们可以通过动态编程来解决这个问题pseudo-Algorithm可以在这里找到。

/** 
* Parenthesizing a string so that expression takes a given value 
*/ 
import java.util.*; 
class Solution 
{ 
static boolean func(int[][] matrix, int[] str, int n, int symbol) 
{ 
    Set<Integer>[][] T = new Set[n][n]; 

    // Assign the value 
    for(int i=0; i<n; i++) 
    { 
     T[i][i] = new HashSet<Integer>(); 
     T[i][i].add(str[i]); 
    } 


    for(int gap = 1; gap<n; gap++) 
    { 
     for(int i = 0, j = gap; j<n; i++, j++) 
     {  
      T[i][j] = new HashSet<Integer>(); 

      for(int k=i; k < i+gap; k++) 
      { 
       Iterator<Integer> outer = T[i][k].iterator(); 
       while(outer.hasNext()) 
       { 
        int elementOuter = outer.next(); 
        Iterator<Integer> inner = T[k+1][j].iterator(); 
        while(inner.hasNext()) 
        { 
         int elementInner = inner.next(); 
         int val = matrix[elementOuter][elementInner]; 
         T[i][j].add(val); 
        } 
       } 
      } 
     } 

    } 
    if(T[0][n-1].contains(symbol)) 
     return true; 
    return false; 
} 


public static void main(String args[]) throws Exception 
{ 
    int[] stringNew = {1, 1, 1, 1, 0}; // for String "bbbbac" 
    int element = 3; 
    /** 
    * Here a -> 0  
    *  b -> 1 
    *  c -> 2 
    *  
    *  Table     Equivalent Table 
    *  * a b c   \  * 0 1 2 
    *  a b b a ------\  0 1 1 0 
    *  b c b a ------/  1 2 1 0 
    *  c a c c  / 2 0 2 2 
    */ 
    int  matrix[][] = {{1, 1, 0},{2, 1, 0},{0, 2, 2}}; //multiplication table 

    System.out.println(func(matrix, stringNew, stringNew.length, 0)); 
} 
}