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

Question

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

[6.6]让我们定义三个符号 a 的乘法运算（×）；乙； c 根据下表：

因此，a × a = b 、a × b = b 等

找到一种有效的算法来检查这些符号的字符串，例如

bbbbac

，并决定 是否可以以这种方式将字符串括起来 结果表达式的值为

a

。例如，在输入

bbbbac

时，您的算法应返回 yes，因为

((b(bb))(ba))c = a

。

这是我的方法：

将其映射到计算布尔括号数量的问题，如此处所示。在该问题中，您将获得以下形式的布尔表达式

T 或 F 和 T 异或 T

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

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

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

Answer 2

我们可以通过动态规划来解决这个问题伪算法可以在这里找到。

/**
* 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 3

特别是对于问题中给出的乘积规则，我尝试在输入中查找给出解决方案的模式，但很快发现在没有解决方案的输入中查找模式更容易。例如：

b*

或

c*

甚至

c*b*

不允许有解决方案。看看 3 个长的输入，然后是 4 个长的输入，然后是 5 个长的输入，我可以为没有解决方案的输入推导出这个正则表达式模式：

^(c*([ab]?a?a?b+)?|(aa|b|c*a)c*a|bac*(ab)?b*)$

因此，这里基本上存在三种替代模式：

c*([ab]?a?a?b+)?
(aa|b|c*a)c*a
bac*(ab)?b*

我针对最多 10 个字符的所有可能输入进行了测试，没有出现新的模式。

此正则表达式将在线性时间内测试任何输入。

分而治之

对于一般情况（以及测试上述正则表达式解决方案），您可以使用一种分而治之的方法与记忆化（动态编程）相结合。

您实际上可以存储带有括号的字符串，以获得给定范围的解决方案。

对于子范围，您不知道所需的结果是什么，您可以继续，直到找到任何可能结果的解决方案（然后停止），或者继续，直到检查完所有分区。因此，调用者将为每个可能的结果得到一个解决方案（非空、带括号的字符串），或者没有（空字符串）。

这是在交互式 JavaScript 片段中实现的想法（可以轻松采用不同的乘法矩阵）。输入内容，有的话立即出现解决方案。输入大小限制为 28 个字符，因为对于较长的输入，该过程需要花费太多时间才能愉快地使用。

该代码片段还包括基于正则表达式的检查：

const a = 0, b = 1, c = 2;

const mul = [
    [b, b, a],
    [c, b, a],
    [a, c, c]
];

function solve(str, outcome) {
    // Convert input letters to numbers (a -> 0, b -> 1, ...etc)
    const expr = Array.from(str.toLowerCase(), ch => ch.charCodeAt() - "a".charCodeAt());
    const memo = new Map;
    
    function recur(start, end) {
        let key = start * str.length + end; // unique identifier for the range (start, end)
        let solution = memo.get(key); // retrieve from memoization
        if (!solution) {  // Not memoized yet
            solution = Array(mul.length).fill("");  // Start by indicating it is not possible to get any outcome
            if (start + 1 === end) {  // base case with one value
                solution[expr[start]] = str[start];
            } else if (start + 2 === end) {  // base case with two values
                solution[mul[expr[start]][expr[start+1]]] = "(" + str.slice(start, end) + ")";
            } else {   // Case for which recursion will be used
                let unsolvedCount = mul.length;
                // Split expression at any possible point
                for (let split = start + 1; split < end; split++) {
                    const left = recur(start, split);
                    const right = recur(split, end);
                    for (const leftRes in mul) {
                        if (left[leftRes]) {  // For every possible solution at the left
                            for (const rightRes in mul) {
                                if (right[rightRes]) {  // ... and every possible solution at the right
                                    const product = mul[leftRes][rightRes]; // ... perform the product
                                    if (!solution[product]) {  // We didn't have this outcome yet
                                        solution[product] = "(" + left[leftRes] + right[rightRes] + ")";
                                        // Allow for quick exit when for all possible outcomes we have a solution
                                        unsolvedCount--;
                                        if (unsolvedCount === 0) return solution;
                                    }
                                }
                            }
                        }
                    }
                }
            }
            memo.set(key, solution); // Remember the work done for this range
        }
        return solution;
    }
    // Get the solution for the wanted outcome and remove the outermost parentheses, if any.
    // An empty string means there is no solution with that outcome
    return recur(0, expr.length)[outcome].replace(/^\(|\)$/g, "");
}

const regex = /^(c*([ab]?a?a?b+)?|(aa|b|c*a)c*a|bac*(ab)?b*)$/;

// I/O handling:

let input = document.querySelector("input");
let outputs = document.querySelectorAll("span");

input.addEventListener("input", refresh);

function refresh() {
    let str = input.value;
    if (!/^[abc]*$/.test(str)) {
        outputs[0].textContent = "Invalid input";
        outputs[1].textContent = "";
        return;
    }
    let solution = solve(str, a);
    outputs[0].textContent = solution || "No solution";
    let decision = !regex.test(str);
    outputs[1].textContent = decision ? "There is a solution" : "No solution";
}

Input: <input size="28" maxlength="28"><br>
Solution: <span></span><br>
Regex:  <span></span>