计算使所有平衡括号子序列为空所需的配对移除次数

---

C 编译器将字符串视为字符数组，因此可以根据字符的位置轻松地移除字符串中的字符。需要检查字符串的第一个和最后一个位置是否存在括号，并将其移除。可以将字符串复制到另一个变量中并显示。

C 中有许多预定义函数可以有效地用于操作字符串。借助这些函数，可以轻松地在 C 中移除字符串开头或结尾的字符。

移除字符串开头和结尾的括号

括号是输入字符串的一部分，是一个单字符，可以通过遵循以下逻辑和算法将其从字符串中移除。

字符是我们在键盘上看到的任何字母数字键，它存储在 C 中的字符变量中。

() 在 c 中称为括号。我们需要在用户输入的字符串中识别此字符，并需要将其从字符串中移除。

数组是一个变量，它具有许多由单个名称和连续编号寻址的内存位置，而字符串是字符数组。

在许多情况下，我们需要从字符串中移除括号，例如在解决正则表达式时。

语法

函数 countRemoval 以字符串 str 作为输入，并返回一个整数值，该值表示使字符串中所有平衡括号子序列为空所需的配对移除次数。该函数使用变量 count 来跟踪所需的移除次数，最初设置为 0。它还使用变量 balance 来跟踪字符串中左括号和右括号之间的平衡。然后，该函数遍历字符串的长度并检查每个索引处的字符。如果字符是左括号，则 balance 加 1，如果字符是右括号，则 balance 减 1。如果 balance 变成负数，则表示存在多余的右括号，移除次数加 1，并将 balance 重置为 0。循环结束后，count 会更新为包含剩余 balance 除以 2 的结果，作为使字符串中所有平衡括号子序列为空所需的移除次数。

int countRemoval(string str) {
   int count = 0;
   int balance = 0;
   for (int i = 0; i < str.length(); i++) {
      if (str[i] == '(') {
         balance++;
      } else {
         balance--;
      }
      if (balance < 0) {
         count++;
         balance = 0;
      }
   }
   count += balance / 2;
   return count;
} 

算法

• 步骤 1 − 声明 str1、str2，初始化为空。

• 步骤 2 − 声明整数变量 len、n、i

• 步骤 3 − 从控制台接收 str1

• 步骤 4 − 检查第一个字符是否为 (

• 步骤 5 − 如果是，则 n = 1

• 步骤 6 − 当 n < 输入字符串长度 len 时，将 str1 中的每个字符复制到 str2 中

• 步骤 7 − 检查 str2 的最后一个字符是否为 )。

• 步骤 8 − 如果是，则将其替换为 \0。

• 步骤 9 − 打印 str2，其中包含输入字符串减去 ()。

方法

方法 1 − 暴力递归：在第一种方法中，我们使用暴力递归来查找所有可能的子序列，并检查它们是否平衡。如果子序列是平衡的，我们移除括号对并计算移除的括号对的数量。我们计算使字符串为空所需的最小配对移除次数。

方法 2 − 动态规划：第二种方法使用动态规划来优化解决方案。我们可以使用一个二维 DP 表来存储从索引 'i' 到 'j' 的子字符串所需的最小移除次数。我们遍历字符串并根据给定条件填充 DP 表。

方法 1 暴力递归

代码

在此代码中，我们检查所有可能的子序列组合，这会导致指数时间复杂度。对于较大的输入，此方法可能效率不高。

#include <iostream>
#include <string>
using namespace std;

int countRemovalsRecursion(const string &s, int index, int open) {
   if (index == s.size()) {
      return open;
   }

   if (s[index] == '(') {
      return countRemovalsRecursion(s, index + 1, open + 1);
   } else if (open > 0) {
      return countRemovalsRecursion(s, index + 1, open - 1);
   } else {
      return 1 + countRemovalsRecursion(s, index + 1, open);
   }
}

int main() {
   string s = "(()())(";
   cout << "Input string: " << s << endl;
   cout << "Minimum removals (Brute Force Recursion): " << countRemovalsRecursion(s, 0, 0) << endl;
   return 0;
}

输出

Input string: (()())(
Minimum removals (Brute Force Recursion): 1

方法 2

示例

此动态规划解决方案计算使所有平衡括号子序列为空所需的最小移除次数。它遍历字符串，使用一维 DP 表更新左括号的数量，并将最终的 DP 值作为最小移除次数返回。

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int countRemovalsDP(const string &s) {
   int n = s.size();
   vector<int> dp(n + 1, 0);

   for (int i = 0; i < n; ++i) {
      if (s[i] == '(') {
         dp[i + 1] = dp[i] + 1;
      } else {
         dp[i + 1] = max(dp[i] - 1, 0);
      }
   }
   return dp[n];
}

int main() {
   string s = "(()())()";
   cout << "Input string: " << s << endl;
   cout << "Minimum removals (Dynamic Programming): " << countRemovalsDP(s) << endl;
   return 0;
}

输出

Input string: (()())()
Minimum removals (Dynamic Programming): 0

结论

此程序利用了 C 的基本概念，例如字符和字符串数据类型之间的区别、字符串分隔符、如何初始化字符串和数组、数组的第一个字符是索引为 0 的位置以及最后一个字符必须为 null 的计算，以获得正确的输出。

程序通过实现 C 编程的基本简单概念实现了括号的移除。