C++-এ প্যarethেসিস (Parentheses) متعادل করার খরচ (Cost to Balance Parentheses)

এই টিউটোরিয়ালে, একটি ব্র্যাকেট সিকোয়েন্স দেওয়া থাকে। ব্র্যাকেটগুলোর পজিশন একে একে শিফট করে সেগুলো متعادل (balanced) করার খরচ বের করতে হবে। متعادل করা না গেলে -1 ফেরত দিন।

পদ্ধতি

খোলা '(' এবং বন্ধ ')' ব্র্যাকেটের সংখ্যা সমান নয়লে -1 ফেরত দিন
প্রিফিক্স সম ব্যবহার করুন: '(' = +1, ')' = -1
প্রিফিক্স সম নেগেটিভ হলে তার 절댓값 যোগ করুন (খরচ)

C++ প্রোগ্রাম উদাহরণ

#include <bits/stdc++.h>
using namespace std;

int costToBalance(string s) {
    if (s.length() == 0) return 0;
    
    int o = 0, c = 0;
    for (char ch : s) {
        if (ch == '(') o++;
        if (ch == ')') c++;
    }
    if (o != c) return -1;
    
    int ans = 0;
    vector<int> a(s.size());
    a[0] = (s[0] == '(') ? 1 : -1;
    if (a[0] < 0) ans += abs(a[0]);
    
    for (int i = 1; i < s.size(); i++) {
        a[i] = (s[i] == '(') ? a[i-1] + 1 : a[i-1] - 1;
        if (a[i] < 0) ans += abs(a[i]);
    }
    return ans;
}

int main() {
    string s = ")))(((";
    cout << costToBalance(s) << endl; // 9
    s = "))((";
    cout << costToBalance(s) << endl; // 4
    return 0;
}

আউটপুট

9
4