给定一个由 '(' 和 ')' 括号组成的字符串 S，我们需要添加最少的括号（ '(' 或是 ')'，可以在任何位置），以使得到的括号字符串有效。
从形式上讲，只有满足下面几点之一，括号字符串才是有效的：
- 它是一个空字符串，或者
- 它可以被写成
AB（A与B连接）, 其中A和B都是有效字符串，或者 - 它可以被写作
(A)，其中A是有效字符串。
给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。
示例 1：
输入："())" 输出：1
示例 2：
输入："((("
输出：3
示例 3：
输入："()" 输出：0
示例 4：
输入："()))(("
输出：4
提示：
S.length <= 1000S只包含'('和')'字符。
**难度**: Medium
**标签**: 栈、 贪心算法、
# -*- coding: utf-8 -*-
# @Author : LG
"""
执行用时：36 ms, 在所有 Python3 提交中击败了90.66% 的用户
内存消耗：13.5 MB, 在所有 Python3 提交中击败了5.64% 的用户
解题思路：
统计未匹配的左右括号。
具体实现见代码注释
"""
class Solution:
def minAddToMakeValid(self, S: str) -> int:
l, r = 0, 0 # 左括号，右括号未匹配数统计
for s in S:
if s == '(': # 如果是左括号，则左括号+1
l += 1
if s == ')': #
if l < 1: # 左括号匹配完后，未匹配的右括号+1
r += 1
else:
l -= 1 # 如果有多余的左括号, 则消耗一个左括号
return l+r # 返回未匹配的左括号和右括号的总和