# 使括号有效的最少添加
给定一个由`(`和`)`括号组成的字符串`S`，我们需要添加最少的括号`(`或是`)`，可以在任何位置，以使得到的括号字符串有效。  
从形式上讲，只有满足下面几点之一，括号字符串才是有效的：  
* 它是一个空字符串。
* 它可以被写成`AB`，即`A`与`B`连接, 其中`A`和`B`都是有效字符串。
* 它可以被写作`(A)`，其中`A`是有效字符串。
给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。


## 示例

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

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

```
输入："()"
输出：0
```

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


## 题解

```javascript
/**
 * @param {string} S
 * @return {number}
 */
var minAddToMakeValid = function(s) {
    var left=0, right=0;
    Array.prototype.forEach.call(s, v => {
        if(v === "("){
            ++left;
        }else{
            if(left > 0) --left;
            else ++right;
        }
    })
    return left+right;
};
```

## 思路
直接遍历一遍，遍历过程中统计好左括号的数量，然后根据遇到右括号的情况来判断是否需要补充右括号，并统计左右括号多余的数量，匹配部分则直接减掉，首先定义左括号多余的括号数量`left`以及右括号多余的括号数量`right`，遍历过程中如果遇到左括号，则认为多余左括号`+1`，如果遇到右括号，首先判断是否有多余左括号，如果有多余左括号就作为左括号的匹配，将多余左括号`-1`，如果已经没有左括号，那么认为有多余右括号，则将多余右括号`+1`，最后返回多余左括号与多余右括号的数量，即需要补充的右括号与左括号的数量即可。


## 每日一题

```
https://github.com/WindrunnerMax/EveryDay
```

## 参考

```
https://leetcode-cn.com/problems/minimum-add-to-make-parentheses-valid
```