Javascript-在字符串中添加缺少的括号

这里有一个简单的基于堆栈的方法。以下是完整的JSFiddle以及已确认的测试病例列表。

function pars(s) {
    var missedOpen = 0, stack = new Array();
    for (i = 0; i < s.length; i++) {
        if (s[i] == '(') {
            stack.push(s[i]);
        } else if (s[i] == ')') {
            if (!stack.pop())
                missedOpen++;
        }
    }
    return Array(missedOpen + 1).join('(') + s + Array(stack.length + 1).join(')');
}

已确认的测试案例：

// Target: Expected
var cases = {
    '()': '()',
    ')(': '()()',
    '(': '()',
    ')': '()',
    'This)(is))a((test)': '((This)(is))a((test))',
    '(A)': '(A)',
    ')A(': '()A()'
};

看到完整的JSFiddle在这里。

正如一条评论所指出的，这里有一个完全没有数组的版本。这应该是最有效的方法。所有测试用例都通过了。

function pars(s) {
    var missedOpen = 0, missedClosed = 0;
    for (i = 0; i < s.length; i++) {
        if (s[i] == '(') {
            missedClosed++;
        } else if (s[i] == ')') {
            if (missedClosed > 0)
                missedClosed--;
            else
                missedOpen++;
        }
    }
    return Array(missedOpen + 1).join('(') + s + Array(missedClosed + 1).join(')');
}

您需要不匹配的开始括号的数量和不匹配的结束括号的数量。这里有一个粗略的解决方案：

function pars(str) {
    var p = 0;
    var minp = 0;
    for (var i = 0; i < str.length; i++) {
        if (str[i] == "(") p++;
        if (str[i] == ")") {
            p--;
            if (p<minp) minp = p;
        }
    }
    for (i = 0; i > minp; i--) {
        str = "(" + str;
    }
    p = p - minp; // If we added any starting parenthesis, we need to end those as well.
    for (i = 0; i < p; i++) {
        str = str + ")";
    }
    return str;
}

这个似乎有效：

function pars(str){
var pars = [].reduce.call(str, function(acc, letter){
      if(letter === '(') { acc.right++;}
  
      else if(letter === ')') {
        if(acc.right) {acc.right--;} 
        else {acc.left++;}//no starting one
          
      }
      return acc;
   }, {left: 0, right: 0}), 
    left = pars.left, 
    right = pars.right;
  if(left) { str = new Array(left+1).join('(') + str;}
  if(right) { str += new Array(right+1).join(')');}
  return str
}
var str = ')))(((fdfd)fd)('
$("#out").html(str + " - " + pars(str))

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<div id="out"/>

这是一个非常脏的解决方案（由于repeat功能，暂时在Firefox中可用）：

function pars(str) {
    var t = str;
    var n;
    while ((n = t.replace(/'([^()]*')/g, "")) != t) {
        t = n;
    }
    var open = t.match(/')/g);
    var close = t.match(/'(/g);
    return "(".repeat(open.length) + str + ")".repeat(close.length);
}

基本上，它匹配所有对的()，然后计算(和)的数量，并相应地附加)和(。

干净的解决方案应该使用计数器来计算打开的不匹配括号的数量。它将丢弃并计数不匹配的)的数量。对于不匹配的(的数量，请按正常操作。这将是一个单程解决方案，而不是像上面那样的多次解决方案。

您可以在这里使用著名的基于堆栈的括号匹配算法的变体。

一般的想法是，当您看到一个左括号时，扫描代码并将其推到堆栈上，然后当您看到右括号时，从堆栈中弹出顶部值并继续。这将确保你有正确的平衡。

(123())
// ( - push -> ['(']
// 1 - nothing
// 2 - nothing
// 3 - nothing
// ( - push -> ['(', '(']
// ) - pop -> ['(']
// ) - pop -> []

然而，我们想稍微改变一下规则。

• 如果我们把一个结束的paren推到堆栈上，而堆栈是空的：我们需要在字符串的开头添加一个开始的paren
• 如果我们到达字符串的末尾，并且堆栈上仍然有打开的paren，那么我们需要关闭它们

所以代码看起来像这样：

function parse(str) {
  var stack = []
    out = str,
    idx = 0,
    chr = '';
  for(idx = 0; idx < str.length; idx++) {
    chr = str[idx];
    if(chr === '(') {
      stack.push(chr);
    }
    else if(chr === ')') {
      if(stack.length > 0) {
        stack.pop();
      } else {
        out = '(' + out;
      }
    }
  }
  for(idx = 0; idx < stack.length; idx++) {
    out = out + ')';
  }
  return out;
}

奖励：由于该算法基于迭代堆栈的特性，它通常会比RegEx替代方案更快。

只需扫描字符串，计算parens+1表示（，-1表示）。如果数字为负数，则表示您在开头缺少一个。如果完成后数字为正数，则这就是您需要在末尾添加的数量。

var addmissingparens = function(s){
    var n = 0;
    Array.prototype.forEach.call(s, function(c){
        if(c === '('){
            n += 1;
        }
        if(c === ')'){
            if(n === 0){
                s = '(' + s;
            }else{
                n -= 1;
            }
        }
    });
    for(; n>0; n-=1){
        s += ')';
    }
    return s;
};