计算括号反转次数

2024 年 8 月 29 日 | 阅读 3 分钟

在此问题中，我们将给定一个包含 "(" 和 ")" 的字符串表达式。括号的放置方式可能无法使表达式平衡。我们需要翻转括号以使表达式平衡。最后，我们需要返回为了使表达式平衡而翻转括号的次数。

示例

Input: string = ")("
Output: 2
To make this expression balanced, we will need to reverse both brackets in order to make the expression balanced. The final expression will be "()".

Input: string = "((("
Output: No matter how many brackets we reverse, the expression cannot be turned into a balanced one.

Input: string = "(((("
Output: 2
We can solve this problem in multiple ways. However, we need at most two reversals to make the expression balanced.

Input: string = "(((())"
Output: 1
We need to reverse one bracket to turn the expression balanced

Input: string = ")(())((("
Output: 3
To make this expression balanced, we need to reverse the three brackets.

从上面的例子中，我们可以得出结论，只有当括号的总数为偶数时，表达式才能变成平衡表达式；同样，两种括号的数量，即 "(" 和 ")" 的数量也必须相等。

解决此问题的基本方法是查看每个括号并计算翻转括号的次数。我们可以递归地执行此操作，并跟踪使表达式平衡所需的最小翻转次数。

时间复杂度：使用此方法解决此问题的 O(2n) 时间复杂度。

空间复杂度：使用此方法解决此问题的 O(n) 空间复杂度。

我们可以看到这种方法非常低效。

一种有效的方法可以在 O(n) 时间内解决此问题。这种方法的核心思想是首先删除表达式中所有平衡的部分。例如，我们将 "}{{}}{{" 转换为 "}{{". 当我们仔细观察时，我们可以注意到，如果我们删除平衡的部分，我们将始终剩下形如 }}…}{{…{ 的字符串。表达式遵循 0 个或多个闭括号后跟 0 个或多个开括号。

现在我们可以轻松计算需要多少次翻转才能将表达式转换为平衡表达式。令 n 为闭括号的数量，m 为开括号的数量。根据此，我们将需要 [n / 2] + [m / 2] 次翻转。因此，我们将需要 2 次翻转。

下面是上述想法的实现

代码

# Python program to return the minimum count of the reversals required to make the given expression of brackets balanced.

# Defining the function that will take the string of brackets and return the number of reversals required to make it balanced.
# If the expression cannot be turned into a balanced expression, then it will return -1

def countReversals(string):

  l = len(string)

  # Firstly check if the length of the given string is even or not
  # If not, that means the expression cannot be balanced, hence return -1
  if (l % 2) != 0:
    return -1

  # Now, we will run a loop to store the unbalanced sections of the given expression
  stack = []
  for i in range(l):
    if (string[i] == ')' and len(stack)):

      if (stack[0] == '('):
        stack.pop(0)
      else:
        stack.insert(0, string[i])
    else:
      stack.insert(0, string[i])

  # Counting the number of brackets that are unbalanced
  unbalanced = len(stack)

  # counting the number of opening brackets present at the end of the unbalanced stack
  n = 0
  while (len(stack)and stack[0] == '('):
    stack.pop(0)
    n += 1

  # The number of reversals required to balance the expression will be the ceiling value of m / 2 plus the ceiling value of n / 2
  # Which can be simplified to the expression (m + n) / 2 + n % 2
  # Where m + n must be even
  return (unbalanced // 2 + n % 2)

# Calling the expression and passing the string to it
string = "(((())"
print("The minimum number of reversals required are: ", countReversals(string.strip()))

输出

The minimum number of reversals required are: 1

时间复杂度：此程序的 O(n) 时间复杂度。

空间复杂度：此程序将占用 O(n) 的空间复杂度。

下一主题排序颜色问题

计算括号反转次数

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Python 问题

计算括号反转次数

相关帖子

如何在 Python 中初始化列表

Python vs Scala

Python 中的鸭子类型是什么

Python 中的 Monkey Patching

Python 中的分类变量

Python 脚本中的暂停

如何在 Python 中打印图案

Python 项目 - 使用深度学习进行乳腺癌分类

Python 3 中的多线程

如何通过 Python 将 current_timestamp 插入 Postgres

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器