计算括号序列对，以便括号在 C++ 中平衡

  • Z时代
  • 2024-01-10
  • 分类：综合

我们得到一个包含括号的字符串，任务是计算可以形成的括号序列对的计数，以便括号是平衡的。

当左括号和右括号的数量相等时，括号被称为是平衡的。不能考虑两次使用一次的括号来形成对。

输入- 字符串参数[] = { ")()())", "(", ")(", ")(", ")" }

输出- 使括号平衡的括号序列对数为：1

说明- 我们将采用每组字符串来更好地计算计数。让我们将第一个元素作为“)()())”，其中有 4 个右括号和 2 个左括号，因此我们将在字符串中查找恰好包含 2 个右括号的下一个元素，以形成一个平衡的括号序列，它不是在字符串中，因此我们将丢弃它并进行下一步。因此，具有相等左括号和右括号的有效对在 (2, 5) 处，因此计数为 1。

输入- string paran[] = { ")()())", "((", "(", ")(", ")(", ")"}

输出- 使括号平衡的括号序列对数为：1

说明- 有效的平衡括号对在 (1, 2) 和 (3, 6) 处。因此计数为 2。

下面程序中使用的方法如下

  • 输入字符串并使用length()函数计算字符串的长度，并将数据传递给函数进行进一步处理。

  • 取一个临时变量 count 来存储有效的括号对，并创建 unordered_map 类型的 um_1 和 um_2 变量。

  • 从 0 开始另一个循环 FOR 直到字符串的大小

  • 在循环内，将 str 设置为 paran[i] 即括号的第一个元素，然后再次计算字符串的长度。

  • 取一个临时变量作为第一个和最后一个，并用 0 初始化它们

  • 从 j 到 0 开始另一个循环 FOR 直到字符串的长度

  • 在循环内，检查 IF str[j] = '(' 然后将第一个增加 1 ELSE 检查 IF first = 1 然后将第一个减少 1 ELSE 将最后一个增加 1。

  • 现在检查 IF first 是 1 并且 last 是 0 然后设置 um_1[first]++ 并检查 IF last 是 1 并且 first 是 0 然后设置 um_2[lst]++ 并且 IF first 是 0 并且 last 也是 0 然后增加计数由 1。

  • 将计数设置为计数 / 2

  • 从 0 到 um_1 开始循环并将计数设置为 um_1.second 和 um_2.first 的最小值

  • 返回计数

  • 打印结果。

示例

#include <bits/stdc++.h>
using namespace std;
int parentheses(string paran[], int size){
   int count = 0;
   unordered_map<int, int> um_1, um_2;
   for (int i = 0; i < size; i++){
      string str = paran[i];
      int len = str.length();
      int first = 0;
      int last = 0;
      for (int j = 0; j < len; j++){
         if (str[j] == '('){
            first++;
         }
         else{
            if (first==1){
               first--;
            }
            else{
               last++;
            }
         }
      }
      if(first==1 && last!=1){
         um_1[first]++;
      }
      if (last==1 && first!=1){
         um_2[last]++;
      }
      if(first!=1 && last!=1){
         count++;
      }
   }
   count = count / 2;
   for (auto it : um_1){
      count += min(it.second, um_2[it.first]);
   }
   return count;
}
int main(){
   string paran[] = { ")()())", "(", ")(", ")(", ")"};
   int size = sizeof(paran) / sizeof(paran[0]);
   cout<<"Count of pairs of parentheses sequences such that parentheses are balanced are:
"<<parentheses(paran, size);
}
输出结果

如果我们运行上面的代码，它将生成以下输出 -

Count of pairs of parentheses sequences such that parentheses are balanced are: 1

以上是 计算括号序列对，以便括号在 C++ 中平衡 的全部内容， 来源链接： utcz.com/z/345868.html

回到顶部