难度: Medium
只有满足下面几点之一，括号字符串才是有效的：
AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者(A)，其中 A 是有效字符串。给定一个括号字符串 s ，在每一次操作中，你都可以在字符串的任何位置插入一个括号
s = "()))" ，你可以插入一个开始括号为 "(()))" 或结束括号为 "())))" 。返回 为使结果字符串 s 有效而必须添加的最少括号数。
示例 1：
输入：s = "())" 输出：1
示例 2：
输入：s = "((("
输出：3
提示：
1 <= s.length <= 1000s 只包含 '(' 和 ')' 字符。运行时间: 19 ms
内存: 16.1 MB
class Solution:
def minAddToMakeValid(self, s: str) -> int:
stack = []
for ch in s:
if ch == ')' and len(stack)!= 0 and stack[-1] == '(':
stack.pop()
else:
stack.append(ch)
return len(stack)
本题解采用栈来处理括号匹配问题，从而计算使括号字符串有效所需的最少括号数。遍历给定字符串s中的每个字符，使用栈来跟踪未匹配的括号。对于每个遇到的'('，将其推入栈中。对于每个遇到的')'，首先检查栈是否为空或栈顶元素是否不是'('，若是，则将')'推入栈；若不是，则从栈中弹出一个'('，表示匹配成功。最终栈中剩余的元素数量即为需要添加的括号数，因为这些是未能匹配的括号。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def minAddToMakeValid(self, s: str) -> int:
stack = [] # 使用栈来跟踪未匹配的括号
for ch in s:
# 如果当前字符是')'且栈非空且栈顶元素是'(', 则弹出栈顶元素，表示匹配成功
if ch == ')' and len(stack)!= 0 and stack[-1] == '(':
stack.pop()
else:
# 否则，将当前字符推入栈中
stack.append(ch)
# 栈中剩余的元素数量即为需要添加的括号数
return len(stack)
栈是解决括号匹配问题的理想选择，因为它能够有效地处理最近未匹配的括号，并且支持后进先出（LIFO）的操作方式，这是处理嵌套结构的关键。当遇到一个右括号时，最近的左括号应该与之匹配，这正是栈结构所擅长的。虽然也可以使用其他数据结构，如队列或列表来模拟这个过程，但他们要么不支持高效的后进先出操作，要么操作复杂度较高，不如栈直观或高效。
当遇到连续多个 ')' 字符时，算法会逐个检查每个 ')'。对于每个 ')'，如果当前栈非空且栈顶元素是 '('，则栈顶的 '(' 会被弹出，表示一对括号成功匹配。如果栈为空或栈顶不是 '('，则当前的 ')' 会被推入栈中，表示这个 ')' 目前未能找到匹配的 '('。这样处理连续的 ')' 会导致栈中累积多个未匹配的 ')'，这些都需要在最后统计未匹配括号的数量时考虑。
这个条件是必需的，因为它防止在栈为空的情况下执行 pop 操作，这会导致错误。当栈为空且遇到 ')' 时，说明没有之前的 '(' 可以与之匹配，因此必须将 ')' 直接添加到栈中，表示这个 ')' 是未匹配的。如果没有这个条件，尝试弹出空栈将会引发错误。
是的，这里包括了所有情况。如果输入字符串全部是 '('，那么这些 '(' 都将被推入栈中并留在栈里，因为没有 ')' 来与之匹配。如果全部是 ')'，则每一个 ')' 都将被推入栈中，因为没有 '(' 来匹配。在这两种情况下，栈中剩余元素的数量（无论是 '(' 还是 ')'）都正是为了使字符串有效而需要添加的括号数量。