Parenthesizing string so that the expression takes the given value

Question

The next issue from the chapter on dynamic programming from Vazirani et. and etc.

---

[6.6] Define the operation of multiplication (×) by three characters a; b; c in accordance with the following table:

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

Find an efficient algorithm that examines the string of these characters, say bbbbac, and decides whether it is possible to bracket the string so that the value of the resulting expression is: a. For example, at the input of bbbbac, your algorithm should return yes, because ((b (bb)) (ba)) c = a.

---

Here is my approach: compare it with the task of counting the number of logical brackets in the form here . In this task, 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 to insert in brackets so that it evaluates to true.

We can think either, and, xor as operators that follow certain rules (T xor F = T, etc.) and act on operands that take values ​​of T or F. For our original problem, we can think of a, b, c as operands with multiplication (x), as defined in this table, as providing rules.

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

Answer 1

Yes, your approach should look like the problem you were talking about. In general, if there are n characters (instead of 3, as you mentioned in this problem, or 2, as in the problem you referred to), then 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; } 

Please note that this is not verified and complete source code.

Answer 2

We can solve this problem by using dynamic programming pseudo-algorithm can be found here.

 /** * Parenthesizing a string so that expression takes a given value */ import java.util.*; class Solution { static boolean func(int[][] matrix, int[] str, int n, int symbol) { Set<Integer>[][] T = new Set[n][n]; // Assign the value for(int i=0; i<n; i++) { T[i][i] = new HashSet<Integer>(); T[i][i].add(str[i]); } for(int gap = 1; gap<n; gap++) { for( int i = 0, j = gap; j<n; i++, j++) { T[i][j] = new HashSet<Integer>(); for(int k=i; k < i+gap; k++) { Iterator<Integer> outer = T[i][k].iterator(); while(outer.hasNext()) { int elementOuter = outer.next(); Iterator<Integer> inner = T[k+1][j].iterator(); while(inner.hasNext()) { int elementInner = inner.next(); int val = matrix[elementOuter][elementInner]; T[i][j].add(val); } } } } } if(T[0][n-1].contains(symbol)) return true; return false; } public static void main(String args[] ) throws Exception { int[] stringNew = {1, 1, 1, 1, 0}; // for String "bbbbac" int element = 3; /** * Here a -> 0 * b -> 1 * c -> 2 * * Table Equivalent Table * * abc \ * 0 1 2 * abba ------\ 0 1 1 0 * bcba ------/ 1 2 1 0 * cacc / 2 0 2 2 */ int matrix[][] = {{1, 1, 0},{2, 1, 0},{0, 2, 2}}; //multiplication table System.out.println(func(matrix, stringNew, stringNew.length, 0)); } }