資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
