Leetcode 921 Minimum Add to Make Parentheses Valid

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

从形式上讲，只有满足下面几点之一，括号字符串才是有效的：
它是一个空字符串，或者
它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
它可以被写作 (A)，其中 A 是有效字符串。
给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。

示例 1：
输入：”())”
输出：1
示例 2：
输入：”(((“
输出：3
示例 3：
输入：”()”
输出：0
示例 4：
输入：”()))((“
输出：4

提示：
· S.length <= 1000
· 只包含 ‘(‘ 和 ‘)’ 字符。

题意分析：
向给定字符串中任意位置添加左括号或者右括号，使整个字符串合法！

思路分析：
碰到这种后面的元素需要和前面的元素进行匹配的问题，通常是要用到栈这个数据结构的。
这类问题主要包括：括号是否合法(右括号匹配左括号)、加减乘除运算(运算符右边的数匹配运算符左边的数)等

对于这道题，我们将所有的左括号入栈，遍历到右括号就使左括号出栈，若当前栈为空，说明这个右括号是不合法的。
若遍历过程结束，栈内仍有多余的左括号，说明这些左括号是不合法的

# 24ms
class Solution(object):
    def minAddToMakeValid(self, S):
        stack = []
        res = 0
        for ss in S:
            if ss == '(':
                stack.append(ss)
            else:
                if not stack: 
                    res += 1
                else:
                    stack.pop()
        return res + len(stack)