資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++平衡表示式，使得給定位置有左括號
括號的平衡表示式是指包含所有型別括號的配對，並且順序正確的表示式。這意味著每個左括號都有一個與其正確匹配的右括號，例如：{ }。
表示式 − {([][]{})({}[]{})}
輸出 − 平衡的
現在，在這個問題中，我們必須從給定的括號數量建立所有可能的平衡表示式。條件是給定位置必須有左括號。
在這個問題中，我們給定一個整數n和一個長度為2n的括號位置陣列，我們必須找到長度為2n的平衡表示式的數量，使得由左括號標記的位置將具有左括號'{'。
示例 −
Input : n = 2 , position [1, 0 , 0 , 0].
Output : 2
Explanation : All possible outcomes are : {{}} , {}{}.演算法
所有位置為1的都是左括號。
使用遞迴迴圈，使用以下規則：
如果（左括號數 - 右括號數）> 0，則返回0。
迴圈到n之後，如果push和pop之後的括號總數為0，則返回1，即獲得解。否則返回0。
如果表示式預先分配為1，則遞迴呼叫以增加索引並增加括號總數。
否則，透過在索引位置插入左括號，然後為其插入右括號，並減少括號總數並移動到下一個索引來遞迴呼叫函式。
程式
#include <bits/stdc++.h>
using namespace std;
int find(int index, int openbrk, int n, int expression[]){
if (openbrk < 0)
return 0;
if (index == n){
if (openbrk == 0)
return 1;
else
return 0;
}
if (expression[index] == 1) {
return find(index + 1, openbrk + 1, n, expression);
} else {
return find(index + 1, openbrk + 1, n, expression) + find(index + 1, openbrk - 1, n, expression);
}
}
int main() {
int n = 3;
int expression[6] = { 1, 0, 1, 0, 0, 0};
cout << find(0, 0, 2 * n, expression) <<endl;
return 0;
}輸出
3
更新於：2019年11月13日
178 次瀏覽
廣告