Parenthesizing a string so that expression takes a given value

Question

The following problem is from the chapter on Dynamic Programming by Vazirani et. al.

---

[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.

---

Here is my approach: Map it to the problem of counting the number of boolean parenthesizations as given here. In that problem, you are given a boolean expression of the form

T or F and T xor T

and you need to find the number of ways of parenthesizing this so that it evaluates to true.

We can think of or , and , xor as operators which follow certain rules (T xor F = T etc.) and act on operands taking values T or F. For our original problem, we can think of a,b,c as operands with multiplication(x) as defined by the given table as providing the rules.

Does the above approach make sense or is there a simpler approach ?

Answer 1

Yes, your approach should be similar to the problem you mentioned. In general, if there are n symbols (instead of 3 as you mentioned in this problem or 2 as in the problem you've given link to), what you should do something like this -

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

Note that, this is not a tested and complete source code.