將字符串括起來以便表達式獲得給定值

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