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.
Write the below in matrix table form for understanding : a,b,c along x and y axis.
(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.
I unserstood the ques but i donot understand how to start with this.
i am required to solve the following in C, C++ . Python etc are not allowed. Iam guessing a boolean approach might work.
Here is a suggestion for how the problem can be solved. Basically, the code is testing all cases from the multiplication table that yields the desired result and checks whether any of them can be achieved:
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;
}
I haven't calculated the complexity of the solution, so I'm not sure if it fullfills the requirement. You would probably have to add memoization to reduce the complexity further.
Further explanation:
There are 3 multiplications that yield a: a*a, b*a and b*b. So the last multiplication must be one of those. The algorithm starts by placing parenthesis for the last multiplication,
It checks all possible placements: (b)(bbba), (bb)(bba), (bbb)(ba), and last (bbbb)(a).
For each placement it checks to see if it is possible to match it to one of the multiplications that yield a.
So let's see how it would match (bbb)(ba) against the multiplication a*a:
It then need to check if it is possbile to get an a from the left expression and an a from the right expression.
So it calls itself:
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"
Let's see what happens in the last of these two, the string "ba":
It will check if it is possible to get an a, so again there are 3 possibles. There is only one way to divide "ba", so the two subexpressions are "b" and "a".
It first checks the multiplication a*a.
isSymbolPossible("b", 'a', 1); // Is it possible to get an 'a' for the string "b" - no it isn't! - skip this multiplication
It then checks the 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
You can see that it solves the problem by breaking it down into smaller parts and checking all routes that can lead to the desired end and skipping other routes as soon as it discovers that they are dead ends.