题目：
给定一个由 ’(‘ 和 ’)‘ 括号组成的字符串 S，我们需要添加最少的括号（ ‘(‘ 或是 ’)‘，可以在任何位置），以使得到的括号字符串有效。
从形式上讲，只有满足下面几点之一，括号字符串才是有效的：
- 它是一个空字符串，或者
- 它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
- 它可以被写作 (A)，其中 A 是有效字符串。
- 给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。
示例 1：
输入："())" 输出：1示例 2：
输入："(((" 输出：3示例 3：
输入："()" 输出：0示例 4：
输入："()))((" 输出：4
来源：力扣（LeetCode）第921题
链接：https://leetcode-cn.com/problems/minimum-add-to-make-parentheses-valid
题目解析：
这题不是很难，比较容易就能想到，只要使用栈就能做出。在这里不讨论栈的方法，而是官方给出的一种更加巧妙和特别的方法，平衡法。
解题思路：
维护两个变量ans(answer)和bal(balance)，ans是正常的结果，而bal则是题目可能发生的一种特殊情况。比如”)))(((“这种情况。这个答案应该是六，而不是0，因为右括号在前面，而左括号在后面，这就导致他们无法作为一对有效的括号。如果我们不用bal这个变量的话，应该是这样子的。
先遍历整个字符串，如果是左括号的话，ans加一，如果是右括号的话，ans减一。看似这样做没什么毛病，但是就像我刚才举得例子，当右括号在左括号的前面或者又括号比左括号多，都会出问题，那怎么办呢？这时，我们bal变量就能派上用场。（可能有人会说用个绝对值就行了，同样是上面那个例子，你会发现用绝对值还是不行！！！！）
还是刚才的思路，只是我们思考一下，如果右括号在前面或者右括号比左括号多的话，会导致ans的值为负数（出现了一次负数也是负数，不管它后面会不会变为正数）。一旦变成了负数（其实就是ans为-1，因为ans只有+1或-1的操作），那那个右括号一定是需要添加的括号，因为他一定是无效的括号。ans存的应该是需要添加的左括号和有效的两个括号，由于有效的两个括号一加一减没了，所以本质上就是存的无效左括号的次数，所以我们要把无效右括号的次数存在bal里面，同时为了不让右括号的-1导致左括号的次数不对，所以当ans值为-1时，bal要加一，同时ans也要加一，即相当于把ans的负数放在bal中。最后，我们只要将ans和bal相加即可得出答案。
简单理解：
维护ans和bal两个变量，ans存的是无效的左括号，同时当左括号的后面找到右括号后，左括号变为有效，那么ans就减一，如果右括号太多，左括号都是有效的，那么就有了无效的右括号，把他存在bal里面，同时将它离开ans，也就是ans+1（因为右括号是-1，+1相当于ans-（-1）），这样子一左一右即可以使两边平衡，最后的答案只要把ans和bal（无效左括号和无效右括号）加起来就行了。
Talk is cheap, show me the code.
平衡法：
class Solution(object):
def minAddToMakeValid(self, S):
ans = bal = 0
for char in S:
if char == '(':
ans += 1
else:
ans -= 1
if ans < 0:
ans += 1
bal += 1
return ans + bal
顺便再附上栈的方法：
class Solution:
def minAddToMakeValid(self, S: str) -> int:
validStack = []
for char in S:
if char == ')' and validStack and validStack[-1] == "(":
validStack.pop()
else:
validStack.append(char)
return len(validStack)
复杂度分析：
平衡法 - 时间复杂度：O(n) n为S的长度（代码中的S） - 空间复杂度：O(1)
总结：
平衡法，我理解为把一个答案分成两类，就比如题目中把无效的括号分为无效左括号和无效右括号，分别求它们的答案，再把它们加在一起，有点像分治算法。