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