数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律用 C++ 统计括号序列对的数量，使其括号平衡
给定一个包含括号的字符串，任务是计算可以形成的括号序列对的数量，使得括号平衡。
当存在数量相等的前括号和后括号时，括号被认为是平衡的。使用一次的括号不能再次被考虑用于形成对。
输入 − 字符串 paran[] = { ")()())", "(", ")(", ")(", ")" }
输出 − 括号平衡的括号序列对的数量为：1
说明 − 我们将采用每个字符串集来更好地计算计数。让我们将第一个元素作为“)()())”，其中有 4 个后括号和 2 个前括号，因此我们将查找字符串中下一个正好包含 2 个后括号的元素以形成一个平衡的括号序列，该序列在字符串中不存在，因此我们将丢弃它并继续下一个。因此，具有相等前括号和后括号的有效对位于 (2, 5)，因此计数为 1。
输入 − 字符串 paran[] = { ")()())", "((", "(", ")(", ")(", ")"}
输出 − 括号平衡的括号序列对的数量为：1
说明 − 有效的平衡括号对位于 (1, 2) 和 (3, 6)。因此，计数为 2。
下面程序中使用的策略如下
输入字符串并使用 length() 函数计算字符串的长度，并将数据传递给函数以进行进一步处理。
使用临时变量 count 存储有效括号对，并创建类型为 unordered_map 的 um_1 和 um_2 变量。
从 0 开始到字符串大小启动另一个 FOR 循环
在循环内，将 str 设置为 paran[i]，即括号的第一个元素，并再次计算字符串的长度。
将临时变量作为 first 和 last 并将其初始化为 0
从 j 到 0 开始到字符串长度启动另一个 FOR 循环
在循环内，检查 IF str[j] = ‘(‘ 则将 first 加 1，否则检查 IF first = 1 则将 first 减 1，否则将 last 加 1。
现在检查 IF first 为 1 且 last 为 0，则设置 um_1[first]++，并检查 IF last 为 1 且 first 为 0，则设置 um_2[lst]++，如果 first 为 0 且 last 也为 0，则将 count 加 1。
将 count 设置为 count / 2
从 0 开始到 um_1 启动循环，并将 count 设置为 um_1.second 和 um_2.first 的最小值
返回 count
打印结果。
示例
#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
751 次查看
