นิพจน์ที่สมดุลของวงเล็บคือนิพจน์ที่มีคู่ของวงเล็บทั้งหมดเข้าด้วยกันในลำดับที่ถูกต้อง ซึ่งหมายความว่าสำหรับวงเล็บเปิดทุกอัน จะมีวงเล็บปิดในวงเล็บที่เหมาะสม เช่น { }.
นิพจน์ − {([][]{})({}[]{})}
ผลผลิต − สมดุล
ในปัญหานี้ เราต้องสร้างนิพจน์ที่สมดุลที่เป็นไปได้ทั้งหมดจากจำนวนวงเล็บที่กำหนด เงื่อนไขคือตำแหน่งที่กำหนดมีวงเล็บเปิด
ในปัญหานี้ เราได้รับจำนวนเต็ม n และอาร์เรย์ของตำแหน่งของวงเล็บที่มีความยาว 2n และเราต้องค้นหาจำนวนนิพจน์ที่สมดุลของความยาว 2n ในลักษณะที่ตำแหน่งที่ทำเครื่องหมายโดยวงเล็บเปิดจะมีวงเล็บเปิด ' {'.
ตัวอย่าง −
Input : n = 2 , position [1, 0 , 0 , 0].
Output : 2
Explanation : All possible outcomes are : {{}} , {}{}. อัลกอริทึม
-
ทุกตำแหน่งที่มีหนึ่งเป็นวงเล็บเปิด
-
ใช้การวนซ้ำโดยใช้กฎต่อไปนี้
-
ถ้า ( จำนวนวงเล็บเปิด - จำนวนวงเล็บปิด )> 0 ให้คืนค่า 0
-
หลังจากวนซ้ำจนถึง n และหากวงเล็บทั้งหมดหลังจากกดและป๊อปเป็น 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;
} 