পরেনথেসিসের একটি সমতুল্য অভিব্যক্তি (balanced expression) হলো এমন অভিব্যক্তি যেখানে সব ধরনের পরেনথেসিস সঠিক ক্রমে জোড়ায় থাকে। অর্থাৎ, প্রতিটি ওপেনিং পরেনথেসিসের জন্য একটি ক্লোজিং পরেনথেসিস সঠিক ক্রমে থাকে, যেমন { }।
অভিব্যক্তি: {([][]{})({}[]{})}
আউটপুট: balanced
এখন এই সমস্যায়, দেওয়া ব্র্যাকেটের সংখ্যা থেকে সব সম্ভাব্য সমতুল্য অভিব্যক্তি তৈরি করতে হবে। শর্ত হলো দেওয়া পজিশনে অবশ্যই ওপেনিং ব্র্যাকেট '{' থাকবে।
এই সমস্যায়, একটি পূর্ণসংখ্যা n এবং ২n দৈর্ঘ্যের ব্র্যাকেট পজিশনের একটি অ্যারে দেওয়া থাকে। ২n দৈর্ঘ্যের সমতুল্য অভিব্যক্তির সংখ্যা বের করতে হবে যাতে চিহ্নিত পজিশনে ওপেনিং ব্র্যাকেট থাকে।
উদাহরণ:
Input : n = 2 , position [1, 0 , 0 , 0]. Output : 2 Explanation : সম্ভাব্য ফলাফল: {{}} , {}{}। অ্যালগরিদম
যে পজিশনে ১ আছে, সেখানে ওপেনিং ব্র্যাকেট থাকবে।
নিচের নিয়মে রিকারসিভ লুপ ব্যবহার করা হয়:
যদি (ওপেনিং ব্র্যাকেটের সংখ্যা - ক্লোজিং ব্র্যাকেটের সংখ্যা) > 0 হয়, তবে ০ রিটার্ন।
n পর্যন্ত লুপ করার পর যদি টোটাল ব্র্যাকেট পুশ-পপের পর ০ হয়, তবে ১ রিটার্ন (সমাধান পাওয়া গেলে)। অন্যথায় ০ রিটার্ন।
যদি অভিব্যক্তিতে ১ প্রি-অ্যাসাইন করা থাকে, তবে ইনডেক্স বাড়িয়ে এবং টোটাল ব্র্যাকেট বাড়িয়ে রিকারসিভ কল।
অন্যথায়, ইনডেক্সে ওপেনিং ব্র্যাকেট डालিয়ে রিকারসিভ কল এবং তারপর ক্লোজিং ব্র্যাকেট डालিয়ে টোটাল ব্র্যাকেট কমিয়ে পরবর্তী ইনডেক্সে যাওয়া।
প্রোগ্রাম
#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; } 