c++ - 来自 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.

以矩阵表的形式写出以下内容以便理解: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 等。我猜 bool 值方法可能有效。

Answer 1

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

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进一步降低复杂性。

进一步说明:

a 有 3 个乘法: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

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