algorithm - 将字符串括起来，以便表达式采用给定值

Question

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

[6.6]Let us define a multiplication operation(×) on three symbols a; b; c according to the following table:

Therefore, a × a = b , a × b = b etc.

Find an efficient algorithm that examines a string of these symbols, say bbbbac, and decides whether or not it is possible to parenthesize the string in such a way that the value of the resulting expression is a. For example, on input bbbbac your algorithm should return yes because ((b(bb))(ba))c = a.

这是我的方法:

将其映射到计算给定的 bool 括号数的问题 here 。在那个问题中，你得到了一个形式的 bool 表达式

T or F and T xor T

并且您需要找到将其括起来的方式的数量，以便它的计算结果为真。

我们可以将 or 、and 、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;
}

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