Заключение строки в скобки, чтобы выражение приняло заданное значение

Question

Следующая проблема из главы «Динамическое программирование» Вазирани и др.al.

---

[6.6] Определим операцию умножения (×) для трех символов a;б;c согласно следующей таблице:

Следовательно, a × a = b, a × b = b и т. д.

Найдите эффективный алгоритм, который проверяет aстрока этих символов, скажем, 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

Мы можем решить эту проблему с помощью динамического программирования. псевдоалгоритм можно найти здесь.

/**
* 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
     *      * a b c         \      * 0 1 2
     *      a b b a    ------\     0 1 1 0
     *      b c b a    ------/     1 2 1 0
     *      c a c c         /      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));
 }
}

Answer 2

Да, ваш подход должен быть похож на проблему, которую вы упомянули. В общем случае, если есть 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;
}

Обратите внимание, что это не проверенный и полный исходный код.