来自 Vazirani 等人的动态规划的字符串算法括号。阿尔

Question

Consider the problem of examining a string x = x1x2 ...xn from an alphabet of k symbols, and a multiplication table over this alphabet. Decide whether or not it is possible to parenthesize x in such a way that the value of the resulting expression is a, where a belongs to the alphabet. The multiplication table is neither commutative or associative, so the order of multiplication matters.

以矩阵 table 形式写出以下内容以便理解：a、b、c 沿 x 和 y 轴。

(a,a)=a; (a,b)=c (a,c)=c

(b,a)=a (b,b)=a (b,c)=b

(c,a)=c (c,b)=c (c,c)=c

For example, consider the above multiplication table and the string bbbba. Parenthesizing it (b(bb))(ba) gives a, but ((((bb)b)b)a) gives c. Give an algorithm, with time polynomial in n and k, to decide whether such a parenthesization exists for a given string, multiplication table, and goal element.

我没有理解这些问题，但我不知道如何开始。

我需要用 C、C++ 解决以下问题。 Python 等不允许。我猜布尔值方法可能有效。

Answer 1

这是解决问题的建议。基本上，代码正在测试乘法 table 产生所需结果的所有情况，并检查是否可以实现其中任何一个：

char alphabet[] = "abc";
char multiplicationTable[][] = { { 'a', 'c', 'c' },
                                 { 'a', 'a', 'b' },
                                 { 'c', 'c', 'c' } };  // Dimensions are k*k.

int N = strlen(s);
int k = strlen(alphabet);

char *s = "bbbba";  // The string

/* Recursive function that returns 1 if it is 
 * possible to get symbol from 
 * string s of length n. 
 */
int isSymbolPossible(char *s, char symbol, int n) {
    int i, j1, j2;
    if (n == 1) {
        return *s == symbol;
    }
    /* Loop over all possible ways to split the string in two. */
    for (i=0; i < n - 1; i++) {
        /* For each such subdivision, find all the multiplications that yield the desired symbol */
        for (j1 = 0; j1 < k; j1++) {
            for (j2=0; j2 < k; j2++) {
                if (multiplication_table[j1][j2] == symbol) {
                    /* Check if it is possible to get the required left and right symbols for this multiplication */
                    if (isSymbolPossible(s, alphabet[j1], i+1) &&
                            isSymbolPossible(s+i+1, alphabet[j2], n - i - 1) { 
                        return 1;
                    }
                }
            }
        }
    }
    return 0;                
}

int main() {
    if (isSymbolPossible(s,'a',N) {
        printf("Yes\n"); 
    } else {
        printf("No\n");
    }
    return 0;
}

我没有计算过解的复杂度，所以不确定是否满足要求。您可能必须添加 memoization 以进一步降低复杂性。

进一步说明：

有 3 次乘法运算得出 a：a*a、b*a 和 b*b。所以最后一个乘法必须是其中之一。该算法首先为最后一个乘法加上括号，

它会检查所有可能的展示位置：(b)(bbba)、(bb)(bba)、(bbb)(ba) 和最后的 (bbbb)(a)。对于每个位置，它都会检查是否可以将其与产生 a.

的乘法之一相匹配

那么让我们看看它如何将 (bbb)(ba) 与乘法 a*a 相匹配：然后它需要检查是否有可能从左边的表达式中得到一个 a 并从右边的表达式中得到一个 a。所以它称自己为：

isSymbolPossible("bbb", 'a', 3);  // Is it possible to get an 'a' for the string "bbb"
isSymbolPossible("ba", 'a', 2);  // Is it possible to get an 'a' for the string "ba"

让我们看看这两个中的最后一个发生了什么，字符串 "ba":

它将检查是否有可能获得 a，所以同样有 3 种可能。 "ba"的除法只有一种，所以两个子表达式分别是"b"和"a".

它首先检查乘法a*a。

isSymbolPossible("b", 'a', 1);  // Is it possible to get an 'a' for the string "b" - no it isn't! - skip this multiplication

然后检查乘法b*a。

isSymbolPossible("b", 'b', 1);  // Is it possible to get a 'b' for the string "b" - yes, so check the right expression too
isSymbolPossible("a", 'a', 1);  // Is it possible to get an 'a' for the string "a" - yes

你可以看到，它通过将其分解成更小的部分并检查所有可以通向所需终点的路线并在发现它们是死胡同时立即跳过其他路线来解决问题。

来自 Vazirani 等人的动态规划的字符串算法括号。阿尔

Algorithm-parenthesize of string from Dynamic Programming by Vazirani et. al

c

c++

algorithm

parentheses