改进 abc[d[e,f],gh] 模式算法中的组合

Question

我写了一个算法，但它不足之处在于没有处理[,abc]这种情况（请见下面的字符串变化和条件），我想知道如何改进它以涵盖这些情况： 给定： 描述字符串变化的Pattern：abc[de[f,g],hk]。

abcdef
abcdeg
abchk

模式由"数组"和跟随其后的字符串组成：abc[...]和字符串adj,kg,q

另一个可能更复杂的示例：utvk[fvu,gn[u,k,r],nl,q[t[ij,lo[z,x]],bm]]。

条件

1. 字符串本身只能包含字母和数字。不能是abc[h\,k,b]或abc[h\[k,b]，这将给出abch,k或abch[k。
2. "数组"始终不为空，并且至少有2个元素。
3. 可以是任何顺序的"数组"或"仅字符串"值，即：abc[a,b[c,d]]或abc[a[b,c],d]。顺序从左到右严格，不能从模式abc[d,e]中得到组合eabc或dabc。
4. abc[d,e]不会产生abcde或abced字符串，只能产生abcd和abce。
5. 模式始终以带有数组的字符串开始：something[...]。
6. 可以有没有数组的字符串：abc[a,bc[d,f]]，但不允许数组没有字符串：abc[a,[d,f]]。
7. 可以是空字符串，即：a[,b]，它给出a和ab

我的解决方案

function getStrings(pat) {
    if(pat.indexOf('[') == -1)
    return pat;

        String.prototype.insert = function(index, string) {
        if (index > 0) {
            return this.substring(0, index) + string + this.substr(index);
        }
    
        return string + this;
        };
    
        function getArray(str, start, isSource = false) {
        if (start < 0) return null;
    
        var n = 0;
        var ret = "";
        var i = start;
    
        for (; i < str.length; i++) {
            if (str[i] == "[") n++;
            else if (str[i] == "]") n--;
    
            if (n == 0) break;
        }
    
        var ret = {
            str: "",
            arr: "",
            end: 0,
        };
        ret.arr = str.slice(start, i) + "]";
        ret.end = i;
    
        start--;
        var end = start;
        for (
            ;
            start > 0 &&
            str[start] != "," &&
            str[start] != "]" &&
            str[start] != "[";
            start--
        ) {}
    
        if(!isSource)
        start++;
        end++;
    
        ret.str = str.slice(start, end);
    
        return ret;
        }
    
        function getElement(source, start) {
        var ret = [];
        start++;
    
        for (
            ;
            start < source.length && source[start] != "," && source[start] != "]";
            start++
        )
            ret[ret.length] = source[start];
    
        return ret;
        }
    
        var source = getArray(pat, pat.indexOf("["), true); // parsing
    
        var ar = source.arr;
    
        source.arrs = getArrays(source); // parsing
        source.source = true;
        
    
        var fi = "";
        var temp_out = [];
        var tol = 0;
    
        return getVariations(source); // getting variations of parsed
    
    
        function getVariations(source) {
        if (source.arrs == undefined) {
        } else
            for (var i = 0; i < source.arrs.length; i++) {
            if (source.source) fi = source.str;
    
            if (!source.arrs[i].arrs) {
                temp_out[tol] = fi + source.arrs[i].str;
                tol++;
            } else {
                var lafi = fi;
                fi += source.arrs[i].str;
    
                getVariations(source.arrs[i]);
                
                if(i != source.arrs.length - 1)
                fi = lafi;
            }
    
            if (source.source && i == source.arrs.length - 1) {
                var temp = temp_out;
                temp_out = [];
                tol = 0;
                return temp;
            }
            }
        }
    
        function getArrays(source) {
        var la = 1;
        var start = 0;
        var arrs = [];
    
        if (!source.arr) return;
    
        while (start != -1) {
            start = source.arr.indexOf("[", la);
            var qstart = source.arr.indexOf(",", la);
            if(source.arr[la] == ',')
            qstart = source.arr.indexOf(",", la+1);
    
            var pu = false;
    
    
            if(qstart != la && qstart != -1 && qstart < start && start != -1)
            {
            pu = true;
            var str = source.arr;
            var buf = [];
            qstart--;
            var i = -1;
    
            for(i = qstart; i > 0 && str[i] != '[' && str[i] != ','; i--)
            {}
            i++;
    
            for(; i < str.length && str[i]!= ','; i++)
            {
                buf[buf.length] = str[i];
            }
    
            if(buf.length == 0)
            {
                la = start;
                alert("1!")
            }
            else
            {
                
                buf = buf.join('');
                arrs[arrs.length] = {str:buf};
                la += buf.length+1;
            }
            }
            else
            if (start != -1) {
            arrs[arrs.length] = getArray(source.arr, start);
            la = arrs[arrs.length - 1].end + 1;
            } else {
            
            start = source.arr.indexOf(",", la);
            if (start != -1) {
                var ret = getElement(source.arr, start);
                arrs[arrs.length] = ret;
                la += ret.length;
            }
            }
        }
    
    
        for (var i = 0; i < arrs.length; i++)
            if (typeof arrs[i] != "string" && arrs[i].arr) {
            arrs[i].arrs = getArrays(arrs[i]);
            var st = arrs[i].arr;
    
            if (occ(arrs[i].arr, "[") == 1 && occ(arrs[i].arr, "]") == 1) {
                st = st.replaceAll("[", '["');
                st = st.replaceAll("]", '"]');
                st = st.replaceAll(",", '","');
                st = JSON.parse(st);
    
                for (var j = 0; j < st.length; j++) st[j] = { str: st[j] };
                arrs[i].arrs = st;
            }
            } else if (typeof arrs[i] == "string") {
            arrs[i] = { str: arrs[i] };
            }
    
        RecursArrs(arrs);
    
        return arrs;
        }
    
        function RecursArrs(arrs) {
        for (var i = 0; i < arrs.length; i++) {
            if (!arrs[i].source)
            if (arrs[i].arr) {
                delete arrs[i].arr;
                delete arrs[i].end;
            }
            if (!arrs[i].str) {
                try{
            arrs[i] = { str: arrs[i].join("") };
                }catch(er)
                {
                    arrs[i] = {str:''};
                }
            if (i && arrs[i - 1].str == arrs[i].str) {
                arrs.splice(i, 1);
                i--;
            }
            } else if (arrs[i].arrs) RecursArrs(arrs[i].arrs);
        }
        }
    
        function occ(string, word) {
        return string.split(word).length - 1;
        }
    
}

// getStrings('IE5E[COR[R[,G[A,E,I]],S,T,U,V,W,X,Y,Z],EORRG[I,M]]')

- Ngdgvcb

---

@trincot 更新了。 - Ngdgvcb

@trincot，我其实没有注意到这一点，但这是我从工作中获得的真正模式。我认为在这种情况下应该跳过它，即将其视为没有 [,... 的东西。可能只需在开始时执行 pat = pat.replaceAll('[,','[').replaceAll(',]',']').replaceAll(',,',',') 即可。 - Ngdgvcb

你认为你的算法在客观指标方面有哪些不足之处？你是否担心运行时间、可能失败的边缘情况数量或代码行数？ - TylerH

@TylerH，抱歉我的英语很糟糕，在第三次重读您的评论后，我还是没看懂。我写的算法可能比其他人的更糟糕，我没有说它很好，但它是我的，而且很重要。 - Ngdgvcb

@Ngdgvcb 好的，让我再试一次。为什么你觉得你的算法“可能比其他人的还要差”？Stack Overflow不是用来发表意见或直觉的，它是用来解答客观问题和疑难杂症的。 - TylerH

Answer 1

我们可以采用一种从内到外的方式来完成这个过程。如果我们将最内层的组（例如'de[fg]'）替换为它的展开形式'def, deg'，并一直递归，直到没有剩余的组为止，那么我们就会创建一个由逗号分隔的字符串列表，我们可以简单地拆分这个列表并返回结果。

const _expand = (
  s, 
  match = s .match (/(.*?)(\w*)\[([^\[\]]+)\](.*)/), 
  [_, a, b, c, d] = match || []
) => match ? _expand (a + c .split (',') .map (x => b + x) .join (',') + d) : s

const expand = (s) => _expand (s) .split (',')

console .log (expand ('abc[de[f,g],hk]'))
console .log (expand ('utvk[fvu,gn[u,k,r],nl,q[t[ij,lo[z,x]],bm]]'))

.as-console-wrapper {max-height: 100% !important; top: 0}

我们的主递归函数——_expand——使用一个正则表达式提取第一个组，并将其分解成组成部分，通过在数组部分上映射来重新组合。然后我们的公共函数expand仅调用递归函数并将结果拆分为一个数组。

例如，对于字符串'utvk[fvu,gn[u,k,r],nl,q[t[ij,lo[z,x]],bm]]'，递归调用将如何处理：

'utvk[fvu,gn[u,k,r],nl,q[t[ij,lo[z,x]],bm]]'    //-->
//        ^^^^^^^^^
'utvk[fvu,gnu,gnk,gnr,nl,q[t[ij,lo[z,x]],bm]]'  //-->
//                              ^^^^^^^  
'utvk[fvu,gnu,gnk,gnr,nl,q[t[ij,loz,lox],bm]]'  //-->
//                         ^^^^^^^^^^^^^^^^^
'utvk[fvu,gnu,gnk,gnr,nl,q[tij,tloz,tlox,bm]]'  //-->
//                       ^^^^^^^^^^^^^^^^^^^
'utvk[fvu,gnu,gnk,gnr,nl,qtij,qtloz,qtlox,qbm]' //-->
//   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
'utvkfvu,utvkgnu,utvkgnk,utvkgnr,utvknl,utvkqtij,utvkqtloz,utvkqtlox,utvkqbm'

更新：正则表达式的解释：

这里使用的正则表达式可以分为六个部分：

• (.*?)：捕获（非贪婪）一组初始字符，存储为a
• (\w*)：捕获开括号前的字母，存储为b
• \[：捕获一个开括号（[）
• ([^\[\]]+)：捕获除了括号（[或]）以外的所有内容，存储为c
• \]：捕获一个闭括号（]）
• (.*)：捕获闭括号之后的所有内容，存储为d

目的是让括号内的组不包含其他括号。一个例子可能是这样的：

    utvk[fvu,gn[u,k,r],nl,q[t[ij,lo[z,x]],bm]]
   `----+---'\/|`-+-'|`----------+-----------'
        \     | \  \  \__         \
         |    \  \_ \__  \____     \
a:     (.*?)   \_  \_  \       \    \
       ~~~~~     |   \  \__     \    \
b:             (\w*)  |    \     \    \
               ~~~~~  |     \     \    \
[:                    \[     |     \    \
                      ~~     |      \    \
c:                      ([^\[\]]+)   \    \
                        ~~~~~~~~~~   |     |
]:                                   \]    |
                                     ~~    |
d:                                        (.*)
                                          ~~~~

- Scott Sauyet

---

谢谢，我认为我需要很多时间才能理解您提供的正则表达式模式。 - Ngdgvcb

已更新正则表达式的解释。希望能有所帮助。 - Scott Sauyet

总是对你的代码经济性印象深刻！快速问题：使用预先计算的参数定义 _expand 的方式是否比传统的在函数体中包含这些计算有益？还是仅仅是个人口味的问题？ - Trentium

@Trentium：这是个人口味问题。我更喜欢尽可能多地使用表达式而不是语句来工作。默认参数使这更简单。你也可以返回一个IIFE或使用call助手。默认参数存在潜在的缺点，但这不适用于像这样的内部函数。 - Scott Sauyet

@ScottSauyet 看起来，如果您看一下我的普通回答，我们可以摆脱递归！ - vincent

Answer 2

我会使用正则表达式将输入内容分解成标记。在这种情况下，我选择采用（字母、分隔符）对的形式，其中分隔符可以是"["，"]"或","之一。字母部分可以为空。

然后我会像你一样使用递归函数，不过我会使用递归生成器函数。

以下是推荐的实现方式：

function* getStrings(pattern) {
    const tokens = pattern.matchAll(/([^[\],]*)([[\],])?/g);
    
    function* dfs(recur=false) {
        let expectToken = true;
        while (true) {
            const [, token, delim] = tokens.next().value;
            if (delim === "[") {
                for (const deep of dfs(true)) yield token + deep;
            } else {
                if (token || expectToken) yield token;
                if (delim === "]" && !recur) throw "Invalid pattern: too many `]`";
                if (!delim && recur) throw "Invalid pattern: missing `]`";
                if (delim !== ",") return;
            }
            expectToken = delim !== "["; // After [...] we don't expect a letter
        }
    }
    yield* dfs();
}


const input = 'IE5E[COR[R[,G[A,E,I]],S,T,U,V,W,X,Y,Z],EORRG[I,M]]';
for (const s of getStrings(input))
    console.log(s);

这种实现应该根据给定的限制匹配模式，但也允许以下情况:

• "数组"可以没有字母前缀就开始。因此，[a,b]是被允许的，并且会产生与a,b相同的输出。
• "数组"后面可以紧接着字母或新的"数组"，但是将被解释为它们之间用逗号隔开。因此，x[a,b]c将被解释为x[a,b],c
• "数组"可以为空。在这种情况下，忽略该数组。因此，x[]与x相同。

有一些基本的错误检查：当括号不平衡时将生成一个错误。

- trincot

---

谢谢，星号代表什么？ - Ngdgvcb

function* 是生成器函数的语法，因此它可以使用 yield。yield* 是从可迭代对象中产出所有值的快捷方式。 - trincot

我进行的性能测试将此答案放置在其他所有答案之间，速度快了20到130倍（@Ngdgvcb）。 - גלעד ברקן

Answer 3

不使用递归的Vanilla解决方案：

const expander = /([^,[\]]*?)\[([^[\]]*?)]/;

const parse = (fields) => {
  let result = fields;
  while (result.match(expander)) {
    result = result.replace(expander, (m, p1, p2) => p2.split(',').map((e) => `${p1}${e}`).join(','));
  }
  return result.split(',');
};

console.log(parse('abc[de[f,g],hk]'));
// => [ 'abcdef', 'abcdeg', 'abchk' ]
console.log(parse('utvk[fvu,gn[u,k,r],nl,q[t[ij,lo[z,x]],bm]]'));
// => [ 'utvkfvu', 'utvkgnu', 'utvkgnk', 'utvkgnr', 'utvknl', 'utvkqtij', 'utvkqtloz', 'utvkqtlox', 'utvkqbm' ]

.as-console-wrapper {max-height: 100% !important; top: 0}

基本上，我只是从object-fields中获取了代码，可以按照以下方式使用：

// const objectFields = require('object-fields');

const parse = (input) => objectFields.split(input.replace(/\[/g, '(').replace(/]/g, ')')).map((e) => e.replace(/\./g, ''));

console.log(parse('abc[de[f,g],hk]'));
// => [ 'abcdef', 'abcdeg', 'abchk' ]
console.log(parse('utvk[fvu,gn[u,k,r],nl,q[t[ij,lo[z,x]],bm]]'));
// => [ 'utvkfvu', 'utvkgnu', 'utvkgnk', 'utvkgnr', 'utvknl', 'utvkqtij', 'utvkqtloz', 'utvkqtlox', 'utvkqbm' ]

.as-console-wrapper {max-height: 100% !important; top: 0}

<script src="https://bundle.run/object-fields@3.0.1"></script>

Disclaimer: I'm the author of object-fields

- vincent

---

哦，你的代码比其他人的更小巧！非常酷。 - Ngdgvcb

虽然我完全没有理由避免递归——除非有性能或缩放问题——但这是一个非常好的版本。而且我学到了一些关于正则表达式的知识！ - Scott Sauyet

@ScottSauyet 哈哈，我痴迷于非递归实现！从你的回答中我也学到了一些东西，哈哈。 - vincent

Answer 4

让我们用文字来描述一个算法。我们定义word为一组连续的没有逗号或括号的字母，也可以是一个空字符串。那么，思考这个过程的一种方式是将其视为具有两种类型条目的堆栈：

1. 一个word。
2. 一个开放的括号，[。

当我们遍历该字符串时，

（1）将单词和开放括号压入堆栈，而不是逗号。

（2a）当我们到达闭合括号]时，我们开始一个列表，并持续弹出堆栈，将单词添加到该列表中，直到我们从堆栈中弹出一个开放括号。然后，我们（2b）弹出堆栈中的下一个条目，即当前列表的前缀，（2c）将列表中的每个条目与前缀附加到堆栈上。

最后，返回堆栈。

这是上述算法的实现。

function f(s) {
  if (s.length == 0) {
    return [];
  }
  const stack = [""];
  let i = 0;
  while (i < s.length) {
    if (s[i] == "[") {
      i += 1;
      stack.push("[", "");
    } else if (s[i] == "]") {
      i += 1;
      const suffixes = [];
      while (true) {
        const word = stack.pop();
        if (word == "[") {
          const prefix = stack.pop();
          for (let j = suffixes.length - 1; j >= 0; j--) {
            stack.push(prefix + suffixes[j]);
          }
          break;
        } else {
          suffixes.push(word);
        }
      }
    } else if (s[i] == ",") {
      i += 1;
      stack.push("");
    } else {
      stack[stack.length - 1] += s[i];
      i += 1;
    }
  }
  return stack;
}

// Output

var s = "a[bp,c[,d]],b[yx,]"

console.log(s);
for (const w of f(s)) {
  console.log(w);
}

console.log("");

s = "abc[de[f,g],hk]"

console.log(s);
for (const w of f(s)) {
  console.log(w);
}

- גלעד ברקן

---

我本来想在这个模型上写另一种解决方案，但被分心了。谢谢你发布它。虽然代码比某些解决方案多得多，但这很可能是到目前为止发布的最有效的解决方案。 - Scott Sauyet

@ScottSauyet，实际上，根据我在线基准测试的结果，它似乎远远落后于trincot的答案（我在那里发表了评论）。 - גלעד ברקן

@ScottSauyet（尽管测试只针对一个短字符串） - גלעד ברקן

哈！我忘记了Trincot的答案，因为我已经考虑过我的和Vincent的两个解决方案，以及像你的基于堆栈的解决方案。我需要更仔细地看一下这个生成器版本。 - Scott Sauyet

真的吗？我肯定认为这是最快的。正则表达式往往很慢，但在该答案中只有一个执行。 - vincent

Answer 5

这里是一个不使用递归的解决方案，使用 object-scan 库。

这个解决方案可能更多地是学术性的兴趣，因为它使用了库内部的机制，我写它是为了满足我的好奇心，看看是否可以用这种方式完成。同时也是给 @ScottSauyet 的难题 - 回报他花费一段时间才想出答案 =)

无论如何，享受吧！

.as-console-wrapper {max-height: 100% !important; top: 0}

<script type="module">
import objectScan from 'https://cdn.jsdelivr.net/npm/object-scan@18.4.0/lib/index.min.js';
import { compile } from 'https://cdn.jsdelivr.net/npm/object-scan@18.4.0/lib/core/compiler.js';

const parse = (input) => {
  const compiled = compile([input.replace(/\[/g, '.{').replace(/]/g, '}')], {});
  return objectScan(['++{children[*]}.value'], {
    filterFn: ({ parent }) => parent.children.length === 0,
    rtn: ({ parents }) => parents.filter((e) => !Array.isArray(e)).map(({ value }) => value).reverse().slice(1).join('')
  })(compiled);
};

console.log(parse('abc[de[f,g],hk]'));
// => [ 'abcdef', 'abcdeg', 'abchk' ]
console.log(parse('utvk[fvu,gn[u,k,r],nl,q[t[ij,lo[z,x]],bm]]'));
// => [ 'utvkfvu', 'utvkgnu', 'utvkgnk', 'utvkgnr', 'utvknl', 'utvkqtij', 'utvkqtloz', 'utvkqtlox', 'utvkqbm' ]
</script>

免责声明：本人是object-scan的作者。

- vincent

---

我一直在关注object-scan，所以这并不是什么难题；但它仍然很有趣，而且总是值得看到许多不同的选择。我认为这个版本与我的递归版本或你的类似while循环版本相比没有任何优势，但仍然很棒。 - Scott Sauyet

@ScottSauyet 哈哈，我试过了！但很好你能理解它！我担心没有人能够理解。 - vincent