使用Python查找平衡括号字符串的最小插入次数

假设我们有一个包含左右括号'(‘和’)’的字符串s。当满足以下条件时，我们可以称之为一个平衡的括号字符串 −

任何一个左括号'(‘都有对应的两个连续的右括号’))’。
一个左括号'(‘必须在对应的两个连续的右括号’))’之前。

因此，例如，”())”，”())(())))”是平衡的，但”)()”，”()))”不是。如果我们有这样的字符串，我们必须计算插入的括号（开放或关闭）的数量，在使字符串平衡的情况下。

因此，如果输入为s=”(())))))”，则输出将为1，因为如果我们将其分开，我们可以得到”(()) ))))”，因此我们需要一个左括号，使字符串”(())()))”变得平衡。

要解决这个问题，我们将按照以下步骤进行 −

o:=0，n:=s的大小
ret:=0，i:=0
while i< n，do
- 如果s[i]与'(‘相同，则
o:=o+1
- 否则，
  - 如果i+1 < n且s[i + 1]与’)’相同，则
  - 如果o为0，则
    - ret:= ret+1
  - 否则，
o:=o-1
- i:=i+1
- 否则，
  - ret:= ret+1
  - 如果o为0，则
  - ret:=ret+1
  - 否则，
o:=o-1
- i:=i+1
return ret+2*o

下面是一个更好的理解实现的示例

示例

def solve(s):
  o = 0
  n = len(s)
  ret = 0
  i = 0
  while i < n:
    if s[i] == '(':
      o += 1
    else:
      if i + 1 < n and s[i + 1] == ')':
        if not o:
          ret += 1
        else:
          o -= 1
          i += 1
      else:
        ret += 1
        if not o:
          ret += 1
        else:
          o -= 1
    i += 1
  return ret + 2 * o
s = "(())))))"
print(solve(s))