javascript - 如何分析无限嵌套的公式？

Question

我有一个公式，其中只有与 \w{3,4} 匹配的元素。有四种运算符:+、+-、/(始终用括号括起来)、v 和普通括号: ( 和 )。

整个公式总是用括号括起来。我只需要能够嵌套到 4 层深度，但如果可能的话最好是无限深度。

以下是应匹配的有效公式的几个示例(xxxx 是 \w{3,4}):

• (xxxx)
• (xxxx/xxxx/xxxx)
• (xxxx+xxxx)
• (xxxx+-xxxx)
• ((xxxx/xxxx)+xxxx)
• (((xxxx/xxxx)+-xxxx)v(xxxx))
• ((xxxx/xxxx)+-(xxxx/xxxx)+xxxx)
• ((xxxx/xxxx)+-(((xxxx/xxxx)+-xxxx)/xxxx)+xxxx)
• ((((xxxx/xxxx)+-((xxxx/xxxx/xxxx)+-xxxx)/xxxx)+xxxx)v((xxxx/(xxxx/xxxx))+xxxx))

如您所见，基本上每个 xxxx 都可以被整个公式替换，并且它应该仍然有效。我不确定正则表达式是否适用于此处，因此我也愿意接受其他建议。

这是我的正则表达式，适用于深度 2，但对我来说似乎过于复杂:

^(?:\(?(?:\w{3,4}|\(\w{3,4}(?:\/\w{3,4})+\))(?:\+-?(?:\w{3,4}|\(\w{3,4}(?:\/\w{3,4})+\)))*\)?$|\({2}(?:\w{3,4}|\(\w{3,4}(?:\/\w{3,4})+\))(?:\+-?(?:\w{3,4}|\(\w{3,4}(?:\/\w{3,4})+\)))*\)v\((?:\w{3,4}|\(\w{3,4}(?:\/\w{3,4})+\))(?:\+-?(?:\w{3,4}|\(\w{3,4}(?:\/\w{3,4})+\)))*\){2})$

试验场:https://regex101.com/r/YGDENq/2

---

编辑:我也在使用解析器删除不必要的括号:

console.log(fixParenthesis('(((((xxxx/xxxx)+-(xxxx/xxxx)+xxxx))))'));

function fixParenthesis(string) {
    function parse(tokens, depth = 0) {
        let ast = [];

        while (tokens.length) {
            switch (tokens[0]) {
                case '(':
                    tokens.shift();
                    ast.push(parse(tokens, depth + 1));
                    break;
                case ')':
                    if (!depth)
                        throw new SyntaxError('mismatched )');
                    tokens.shift();
                    return ast;
                default:
                    ast.push(tokens.shift());
            }
        }

        if (depth) {
            throw new SyntaxError('mismatched (');
        }

        return ast;
    }

    function generate(el) {
        if (!Array.isArray(el))
            return el;

        while (el.length === 1 && Array.isArray(el[0]))
            el = el[0];

        return `(${el.map(generate).join('')})`;
    }

    return generate(parse(string.match(/\(|\)|[^()]+/g)));
}

它可以用来分析公式而不是 Regex 吗？

Answer 1

您可以从字符串中匹配和删除带有运算符的操作数，然后删除成对的()子字符串直到没有匹配，然后检查字符串是否为空。如果为空，则字符串有效，否则无效。

var s = "((abcd/abc)+-(ab1/abd3)+dfg3)";
// Preliminary checks:
if (/^[()\w+\/-]*$/.test(s)) { // Only allowed chars?
 if (!/\bvv\b|(?!\+-)[+\/-]{2,}|[+\/-]+v\b|\bv[+\/-]+/.test(s)) { // No repeating delimiters?
  var prev=s;
  var res = s.replace(/\+-?|[-\/v]|\b\w{3,4}\b/g, '');
  while(res != prev) {
    prev = res;
    res = res.replace(/\(\)/g, '');  
  }
  if (res.length > 0) {
     document.body.innerHTML= "Not valid";
  } else {
     document.body.innerHTML = "Valid";
  }
 }
}

/\+-?|[-\/v]|\w{3,4}/g 正则表达式匹配

• \+-? - +- 或 +
• | - 或者
• [-\/v] - -、/ 或 v
• | - 或者
• \w{3,4} - 三个或四个单词字符。

删除括号是通过 .replace(/\(\)/g, '') 在 while block 中完成的，其中新字符串与前一个字符串进行比较: 如果相同，则不再进行替换，我们可以继续检查字符串是否为空。