javascript - Codewars - 平衡括号 - Javascript

Question

尝试解决this codewars challenge :

Your job is to fix the parentheses so that all opening and closing parentheses (brackets) have matching counterparts. You will do this by appending parenthesis to the beginning or end of the string. The result should be of minimum length. Don't add unnecessary parenthesis.

The input will be a string of varying length, only containing '(' and/or ')'.

For example:

Input: ")("
Output: "()()"

Input: "))))(()("
Output: "(((())))(()())"

我的想法是创建一个“堆栈”，然后当我们遇到“相反”括号时将该堆栈插入最终数组。

const fixParentheses = (str) => {
  let array = Array.from(str);
  let final = [];
  let stack = [];
  for (let j = 0; j < array.length; j++) {
    if (array[j] === ')' && array[j + 1] === ')'){
      stack.push(')');
    }
    if (array[j] === ')' && array[j + 1] === '(') {
      stack.push(')');
      stack.unshift('('.repeat(stack.length));
      stack = stack.join();
      stack = stack.replace(/[,]/gi, '');
      final.push(stack);
      stack = [];
    }
    if (array[j] === '(' && array[j + 1] === '(') {
      stack.push('(');
    }
    if (array[j] === '(' && array[j + 1] === ')') {
      stack.push('(');
      stack.push(')'.repeat(stack.length));
      stack = stack.join();
      stack = stack.replace(/[,]/gi, '');
      final.push(stack);
      stack = [];
    }
  }
return final.join('');
}
console.log(fixParentheses('))))(()('));

所需输出:'(((())))(()())'

问题在于这是平衡的，但顺序不正确。

我不知道如何解释我们看到 (()() 的情况，而又不会让函数变得过于复杂(事实上已经如此)。

此外，您能否向我解释一下为什么我目前必须将数组方法分隔在不同的行上？ IE。为什么会这样

stack.push('(');
stack.push(')').repeat(stack.length));
stack = stack.join();
stack = stack.replace(/[,]/gi, '');

不会产生错误，但是stack.push('(').push(')'.repeat(stack.length)).join().replace(/[,]/gi, '' ); 是吗？我想优化。

Answer 1

更简洁的替代方案:

1. 删除所有相邻匹配项的括号，即 "()"。
2. 重复此操作，直到不再有为止。这样您就只剩下不匹配的括号了。
3. 计算字符串中有多少个)。这是您需要在开头添加的 ( 数量。
4. 计算字符串中有多少个 (。这是您需要添加到末尾的 ) 数量。

const fixParentheses = (str) => {
  let orig = str;

  //Repeatedly remove all instances of "()" until there are none left
  while (str.includes("()"))
    str = str.replace(/\(\)/g, '');
    
  //Count the number of ")" and "(" left in the string
  let amtOpeningParensNeeded = (str.match(/\)/g) || []).length;
  let amtClosingParensNeeded = (str.match(/\(/g) || []).length;
  
  //Add that many "(" and ")" to the string, respectively
  return "(".repeat(amtOpeningParensNeeded) + orig + ")".repeat(amtClosingParensNeeded);
};

//You can ignore this, it's just a wrapper for demo/logging purposes
const test = input => { console.log(`Input: ${input}`); console.log(`Output: ${fixParentheses(input)}`)};

test(")(");
test("))))(()(");

<小时/>

Why do I have to separate my array methods into new lines? Why does stack.push('(').push(')'.repeat(stack.length)).join().replace(/[,]/gi, ''); throw an error?

您无法将其他数组方法链接到 .push()因为它不返回数组；它返回 integer representing the new length of the array .

就所有意图和目的而言，["apples","oranges"].push("banana").join() 与 3.join().