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

2023-06-21 13:57:03 68

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

将计数设置为计数/2

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

返回计数

打印结果。

示例

#include 
using namespace std;
int parentheses(string paran[], int size){
   int count = 0;
   unordered_map 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:
"<输出结果
如果我们运行上面的代码，它将生成以下输出-
Count of pairs of parentheses sequences such that parentheses are balanced are: 1

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

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

示例

热门推荐

随机推荐