括号内的字符串，以便表达式采用给定值

Question

以下问题来自Vazirani等人的“动态编程”一章。等

---

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

因此，a×a = b，a×b = b等。

找到一种有效的算法，该算法检查这些符号的字符串（如bbbbac），并确定是否可以以使结果表达式的值为a的方式对字符串加上括号。例如，在输入bbbbac上，您的算法应返回yes，因为（（b（bb））（ba））c = a。

---

这是我的方法：将其映射到此处计算布尔括号数量的问题。在该问题中，将为您提供以下形式的布尔表达式

T 或 F 和 T xor T

并且您需要找到多种方法将此方法加括号，以使其评估为true。

我们可以将或，和，xor视为遵循某些规则的运算符（T xor F = T等），并对采用值T或F的操作数进行操作。对于我们的原始问题，我们可以将a，b，c视为操作数由给定表定义的乘法（x）提供规则。

上面的方法有意义吗？还是有一个更简单的方法？

Answer 1

是的，你的方法应该与你提到的问题类似。一般来说，如果有n 个符号（而不是您在这个问题中提到的 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;
}

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