题目描述

给定一个由  '('  和  ')'  括号组成的字符串 S，我们需要添加最少的括号（ '('  或是  ')'，可以在任何位置），以使得到的括号字符串有效。

从形式上讲，只有满足下面几点之一，括号字符串才是有效的：

• 它是一个空字符串，或者
• 它可以被写成  AB （A  与  B  连接）, 其中  A 和  B  都是有效字符串，或者
• 它可以被写作  (A)，其中  A  是有效字符串。 给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。

示例 1：

输入： "())"
输出： 1

示例 2：

输入： "((("
输出： 3

示例 3：

输入： "()"
输出： 0

示例 4：

输入： "()))(("
输出： 4

提示：

1. S.length <= 1000
2. S 只包含 '(' 和 ')' 字符。

来源：LeetCode

思路

分析一下，相邻的且先左后右的一对括号，是最小的有效括号对。把这样的有效对，从S中剔除，可能会行程新的有效对，继续剔除，直到没有。则 S 剩下的括号数，就是需要添加括号与之配对的个数。
我们用一个栈来解决，依次将括号压入栈，若遇到右括号，则比较栈顶是否是左括号，是就弹出栈，并且这个右括号不入栈，这就是剔除。S 扫描一遍后，栈的长度即是所需括号数。

解法

/**
 * @param {string} S
 * @return {number}
 */
const minAddToMakeValid = S => {
  const stack = [];

  for (c of S) {
    if (c === ')' && stack[stack.length - 1] === '(') {
      stack.pop();
      continue;
    }

    stack.push(c);
  }

  return stack.length;
};